рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Геометрическая интерпретация решения ЗЛП.

Реферат Курсовая Конспект

Выберите учебное заведение

Геометрическая интерпретация решения ЗЛП.

Геометрическая интерпретация решения ЗЛП. - раздел Образование, Курс лекций Основные понятия и определения Графический Метод Решения Злп Состоит Из Следующих Этапов: На ...

Графический метод решения ЗЛП состоит из следующих этапов:

На координатной плоскости Х₁ОХ₂строится область допустимых решений (ОДР). Она представляет собой многоугольник, стороны которого лежат на прямых, получаемых из системы ограничений задачи.
Строится вектор нормали q = (С₁,С₂) целевой функции (он указывает на направление возрастания целевой функции).
Строятся нижние и верхние опорные прямые, т.е. крайние линии уровня целевой функции, имеющие общие точки с ОДР. (Путем параллельного перемещения опорной прямой в направлении вектора нормали q).
Определяются координаты экстремальных точек и вычисляются значения целевой функции в них.

Пример 2.3

Решить графическим методом следующую задачу:

х₁ + 3х₂≤ 21

3х₁ + 2х₂≤ 21

3х₁ + х₂ ≤ 18

х₁; х₂≥ 0

Определить при каких х₁и х₂ функция F = 30х₁ +60х₂→ max

Решение.

Область допустимых решений построим следующим образом. Постоим прямые с уравнениями

Х₁

Х₂

1) х₁ + 3х₂= 21

Х₁

Х₂ 10,5

2) 3х₁ + 2х₂= 21

Х₁

Х₂

3) 3х₁ + х₂ = 18

4) х₁= 0

5) х₂ = 0

Прямые пронумерованы, а рядом с соответствующим уравнением приведены координаты двух точек, через которые проходят прямые.

В результате получим выпуклый пятиугольник ОАВСD.

2. Строим нормальный вектор q = (30;60)/ 3, уменьшив значение координат в 3 раза. Прямая с уравнением 30 х₁ + 60 х₂= 0 представляет собой «нулевую» линию уровня целевой функции. Эта прямая проходит через начало координат и перпендикулярна нормальному вектору q. Передвигаем эту прямую параллельно себе по вектору q и фиксируем ее крайнее положение (т.В).

3. Определим координаты точки В, которая принадлежит прямым 1) и 2).

Составляется система уравнений:

х₁ + 3х₂= 21 х₁ = 3; х₂ = 6

3х₁ + 2х₂= 21

Тогда F _max=30∙3 + 60∙6 = 450

При минимизации F = 30 х₁ + 60 х₂ линию уровня необходимо смещать параллельно самой себе в направлении противоположном вектору q. Минимум функции достигается в точке О(0;0).

Тогда F _min= 0.

К достоинствам геометрического метода решения ЗЛП относятся:

- наглядность;

- быстрота и легкость нахождения ответа.

К недостаткам геометрического метода относятся:

- возможны «технические» погрешности при приближенном построении графиков;

- многие величины, имеющие четкий экономический смысл (остатки ресурсов производства, избыток питательных веществ и т.п.) не выявляются;

- этот метод легко применим, когда число переменных в стандартной задаче не превышает двух.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Курс лекций Основные понятия и определения

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ... МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... Г С БОРОВСКИЙ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Геометрическая интерпретация решения ЗЛП.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Место и роль методов оптимизации при моделировании и решении прикладных задач.
Исследование операций – научная дисциплина, занимающаяся разработкой и практическим применением методов эффективного управления различными организационными системами.

Общая постановка задачи линейного программирования.
Обозначим Хj (j = 1,2, … , n) –число единиц продукции Pj; bi (i = 1,2,…, m) запас ресурса Si; aij – число единиц ресурса S

Решение.
X1, X2– число единиц видов изделий соответственно А и В. № п/п Алгоритм Конкретное соответствие данной задаче

Отыскание опорного и оптимального решения ЗЛП с использованием табличного алгоритма с заменой базисных переменных.
Алгоритм составления симплексных таблиц (СТ), рассмотрим на примере решения задачи отыскания max. Пример 2.6 Линейная функция: F=2x1+3x

Выполнить самостоятельно.
В соответствии с индивидуальным заданием №1 решить задачу максимизации с использованием симплексных таблиц. Вариант задания выбирается по номеру зачетной книжки: -предпоследняя цифра - № с

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ №1
0,1,2 3,4,5,6 7,8,9 f(x)=3x1-2x2; 2x1+x2

Постановка задачи целочисленного программирования (ЗЦП)
ЗЦЛП формируется следующим образом: Найти такое решение (план) Х=(х1х2… хn), при котором линейная ф-ция: n Z=∑cj

Метод отсечения (метод Гомори).
Сначала задача решается без условия целочисленности, если полученный план целочисленный, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующ

Алгоритм решения ЗЛЦП
1.Симплексным методом решить задачу без учета условия целочисленности, если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования.

Метод множителей Лагранжа.
Другой способ определения условного экстремума осуществляется с построения вспомогательной функции Лагранжа, которая достигает max для тех же х1,х2,…,хn, что и целе

Методы определения экстремума унимодальной функции.
Унимодальная функция – функция, в интервале исследования имеющая только один экстремум. А) Методы определения экстремума функции одной переменной.

Методы определения локального экстремума функции нескольких переменных
а) Метод Гаусса – Зейделя Метод поочередного изменения параметров (переменных), или метод покоординатного спуска (подъема). Суть метода: поочеред

Алгоритм метода
Случайно выбираемся точка с некоторыми координатами. Затем по формуле (1) рассчитывается следующая точка. Алгоритм остана