Геометрический метод решения задач Л.П

Рассмотрим задачу Л.П. в стандартной форме с двумя переменными.

· Множество допустимых решений задачи Л.П. представляет собой выпуклый многоугольник (или выпуклую многогранную область), а оптимальное решение задачи находится, по крайней мере, в одной их угловых точек этого многоугольника решений.

Значит, задачу Л.П. можно сформулировать так: среди всех точек области D найти ту, которая обращает в max или min целевую функцию Z.

Для нахождения экстремального значения целевой функции при геометрическом методе решения используют на плоскости х₁Ох₂ вектор, который обозначается .Этот вектор показывает направление наискорейшего изменения целевой функции. Координаты вектора являются коэффициентами целевой функции Z, т.е. .

Алгоритм решения задачи:

1) найти область допустимых решений системы ограничений задачи;

2) строим радиус - вектор

3) проводим линию уровня l ₀, которая перпендикулярна ;

4)

линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум. Решением задачи на min является первая точка, в которой прямая l₀ встречается с областью D при перемещении l₀ в положительном направлении вектора .

При построении может получиться многоугольник, который неограничен снизу, тогда задача на min решения не имеет; если неограничен сверху, то задача решений не имеет на максимум.

5) Находим координаты точки экстремума и значение целевой функции в ней.

Замечания:

1) если окажется, что прямая l₀ при перемещении параллельна одной из сторон многоугольника, то в таком случае, экстремум достигается во всех точках соответствующей стороны, а задача будет иметь бесчисленное множество решений, в таком случае говорят, что задача имеет альтернативный оптимум;

2) аналогично можно показать решение задачи Л.П. в случае с тремя переменными.

Пример: Для изготовления 2-х видов продуктов Р₁ и Р₂ используется четыре вида сырья S₁, S₂, S₃, S₄. Запасы сырья, технологические коэффициенты (затраты сырья на производство единицы продукции) приведены в таблице.

Виды сырья	Технологические коэффициенты	Запасы
Р1	Р2
S1
S2
S3
S4

Необходимо составить план выпуска продукции, обеспечивающий максимальную прибыль, если прибыль от продажи продукции вида P₁=2 у.е., а Р₂=3 у.е.

Решение:

Обозначим x₁ - количество единиц продукции вида Р₁, которое необходимо выпустить предприятию;

х₂ - количество единиц продукции вида Р₂.

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

Z = 2x₁+3x₂ → max

- экономико – математическая модель задачи.

Решим задачу графически.

l₁:x₁+3х₂=18

х1
х2

l₂:2x₁+х₂=16

х1
х2

l₃:x₂=5 (l параллельна ОХ₁)

l₄:x₁=7 (l параллельна ОХ₂)

l₅:x₁=0 (ОХ₂)

l₆:x₂=0 (ОХ₁)

Вывод: план выпуска продукции вида Р₁ составляет 6 единиц; вида Р₂ - 4 единицы. При этом максимальная прибыль составит 24 у.д.е.

Дата добавления: 2014-11-08