Особые случаи графического метода

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

Рисунок 1

При перемещении прямой с1x+с2y=d «вход» или «выход» (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с1х +с2у=d.

В этом случае точек «выхода» («входа») бесчисленное множество, а именно – любая точка отрезка АВ. Это означает, что целевая функция принимает максимальное(минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D.

Если область допустимых решений является незамкнутым выпуклым многоугольником в направлении оптимизации целевой функции, то целевая функция будет неограниченной, и ЗЛП не будет иметь решений, т.е. максимальное (минимальное) значение функции не достигается никогда.

Рисунок 2

Рассмотрим на примере функции f(x) =3x1+3x2→ max

При ограничениях

2x2-x2≥1 (1)

X1-2x2≤2 (2)

X1,2≥0.

Решение: Задача не имеет решения, так как ЦФ не ограничена сверху на ОДР. (рис. 2)

Задача

о планировании выпуска продукции пошивоч­ному предприятию. (Задача о костюмах).

Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Tребуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского - 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Модель задачи.

Введем следующие обозначения: х₁ - число женских костюмов; x₂ - число мужских костюмов.

Прибыль от реализации женских костюмов составляет 10х₁, а от реализации мужских 20х₂, т.е. необходимо максимизировать целевую функцию

f(x) = 10´ х₁ + 20´ х₂ -> max.

Ограничения задачи имеют вид:

х₁ + х₂ £ 150

2 х₁ + 0.5 х₂ £ 240

х₁ + 3.5 х₂ £ 350

х₂³ 60

х₁ ³ 0

Первое ограничение по труду х₁ + х₂ £ 150. Прямая х₁ + х₂ = 150 проходит через точки (150, 0) и (0, 150).

Рис. 2. Решением первого неравенства является нижняя полуплоскость.

Второе ограничение по лавсану 2 х₁ + 0.5 х₂ £ 240. Прямая 2 х₁ + 0.5 х₂ = 240 проходит через точки (120, 0) и (0, 480). Третье ограничение по шерсти х₁ + 3.5 х₂ £ 350. Добавим четвертое ограничение по количеству мужских костюмов х2 ³ 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х2 = 60. На рис.3. заштрихована область допустимых решений.

Рис. 3. Заштрихована область допустимых решений.

Для определения направления движения к оп­тимуму построим вектор-градиент Ñ, координаты которого являются частными производными целевой функции, т.е. = (10;20).

Что бы построить этот вектор, нужно соединить точку (10;20) с началом координат. При макси­мизации целевой функции необходимо двигаться в направ­лении вектора-градиента, а при минимизации — в противо­положном направлении. Для удобства можно строить век­тор, пропорциональный вектору Ñ. Так, на рис. 2.1.6. изобра­жен вектор градиент (30;60).

В нашем случае движение линии уровня будем осущест­влять до ее выхода из области допустимых решений. в крайней, угловой точке достигается максимум целевой функции. Для нахождения координат этой точки достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума: х₁ + 3.5 х₂ = 350

х₁ + х₂ = 150.

Отсюда лег­ко записать решение исходной ЗЛП: max f(x) = 2300 и дости­гается при x₁=70 и x₂=80 (рис. 4.)

Рис.4. Максимум целевой функции достигается в точке (70, 80).

Задача 2. Для изготовления двух видов продукции А₁ и А₂ используют три вида ресурсов S₁, S₂, S₃, запасы которых составляют 18, 16 и 5 усл.ед. Расход ресурсов на 1 ед. продукции приведен в таблице:

Виды ресурсов	Запасы ресурсов	Расходы ресурсов на 1 изд.
		А1	А2
S1	18	1	3
S2	16	2	1
S3	5	-	1
	Прибыль	2 руб.	3 руб.

Необходимо составить такой план производства продукции, который обеспечит наибольшую прибыль от ее реализации.

Составим экономико-математическую модель (ЭММ) задачи.

Пусть надо выпустить изделий A₁ - x₁ шт., а изделий А₂ - x₂ шт. Тогда прибыль F = 2x₁ + 3x₂ Þ max

x1 + 3x2 £	18
2x1 + x2 £	16
x2 £	5
x1 ³ 0,	x2 ³ 0