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

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

Рисунок 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)

3.Задача

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

Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 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₃, запасы которых составляют  и  усл.ед. Расход ресурсов на  ед. продукции приведен в таблице:

Виды ресурсов	Запасы ресурсов	Расходы ресурсов на 1 изд.
		А1	А2
S1			
S2			
S3			
	Прибыль	 руб.	 руб.

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

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

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

xx	
xx	
x	
x	x

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

	xx
	xx 
	к.т. <в) – входит
2)	2xx
	2xx 
	к.т.  <в) – входит
3)	x
	xxниже прямой
4)	x1правее ОX
5)	x2выше ОX1
Линия уровня		F xx F 
		xx 
		q указывает направление возрастания F.

max F достигается вт. С

т.С	xx 		xx 		 x 	
	xx 		xx 		xx 
	x 
	x

Таким образом, необходимо выпустить x_шт. изделий А₁, x₂шт. изделий А₂, чтобы получить max F ден.ед.

Список использованной литературы

1. Теория игр и экономическое поведение, фон Нейман Дж., Моргенштерн О., изд-во Наука, 1970

2. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр: Учеб. пособие для ун-тов - М.: Высш. шк., Книжный дом «Университет», 1998

3. Дубина И. Н. Основы теории экономических игр: учебное пособие.- М.: КНОРУС, 2010

4. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов/Под ред. И.В.Орлова

5. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2004. – 144 с