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

⇐ Предыдущая 1 2 345 6 7 8 9 Следующая ⇒

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

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

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

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

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

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

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

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

линию уровня перемещаем по направлению вектора

для задач на максимум и в направлении, противоположном

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

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

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

Замечания:

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

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

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

Виды сырья	Технологические коэффициенты	Запасы
Р₁	Р₂
S₁
S₂
S₃
S₄

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

Решение:

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

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

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

Z = 2x₁+3x₂→ max

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

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

l₁:x₁+3х₂=18

х₁
х₂

l₂:2x₁+х₂=16

х₁
х₂

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

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

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

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

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

⇐ Предыдущая 1 2 345 6 7 8 9 Следующая ⇒

Поделиться с друзьями:

Дата добавления: 2014-11-08; Просмотров: 626; Нарушение авторских прав?; Мы поможем в написании вашей работы!

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

studopediasu.com - Студопедия (2013 - 2026) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление

Генерация страницы за: 2.076 сек.