Posobie1

Шаг 4—5. Перемещаем L0 по направлению вектора С до линии уровня, которая являлась бы границей полуплоскости, целиком содержащей ОДР. Однако закончить указанное перемещение невозможно. Из рис. 11 видно, что какую бы линию уровня в направлении вектора нормали ни провести (штрихованные прямые на чертеже), любая из них пересекает ОДР. Следовательно, Lmax= +∞. Это означает, что задача на максимум неразрешима.

				x2
			10						L0–				L0
			8
			6
			4
2x1 5x2			10
			2				B									A				D								x1 3x2			3
–2				O	2							4					6			8					10						x1
x1 x2 1															С

Рис. 11. Неограниченность ОДР и целевой функции

2. Теперь найдем значения переменных, при которых целевая функция минимизируется. Шаги 1—3 точно те же, что и при решении максимизационной задачи.

Шаг 4. Перемещаем линию уровня L0 в направлении, противополож-

ном вектору С , до линии, являющейся границей полуплоскости, целиком содержащей ОДР. Такой линией является прямая L0–, проходящая через точку В. Следовательно, Lmin = L(B).

Шаг 5. Координаты точки В определяются как пересечение прямых

2x1 + 5x2 = 10 и –x1 + x2 = 1: x1=5/7 и x2=12/7. Значит, Lmin = 5,2 · 5/7 –

– 12/7 = 2.

31

3. Применение графического метода при решении транспортной задачи

Дадим подробную иллюстративную характеристику схемы алгоритма применительно к конкретной транспортной задаче. Это позволит не приводить последующее ее формальное описание.

Пример 4. а) Найти значения переменных, при которых функция

L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 принимает экстремальные значения при условии, что:

x11 + x12 + x13 = 110, x21 + x22 + x23 = 100, x11 + x21 = 60,

x12 + x22 = 80, x13 + x23 = 70,

x11 0, x12 0, x13 0, x21 0, x22 0, x23 0.

б) Интерпретируя переменные и константы, входящие в указанные математические модели, в соответствии с вариантами примера 1 из § 1, дать экономическую характеристику полученных решений.

Решение. а) Введем новые переменные u1, u2, положив u1 = x11, u2 = x12, и выразим через них остальные. Получим x13 = – u1 – u2 + 110, x21 = – u1 + 60,

x22 = – u2 + 80, x23 = 70 – x13 = 70 – (– u1 – u2 + 110) = u1 + u2 – 40. Соответственно L(X) = L(U) = 4u1 + 8u2 + 9(– u1–u2 +110) + 7(– u1 + 60) + 3(– u2 + 80) + + 5(u1 + u2 – 40) = –7u1 + u2 + 1 450.

Тогда с учетом неотрицательности переменных xij для i, j= 1, 2, 3, формулировка исходной задачи приобретает следующий вид:

L(U) = –7u1 + u2 + 1 450 max (min)

u1			u2		110 0,
		u1		60 0,
		u2		80 0,
	u	1	u	2	40 0,

u1 0, u2 0.

Для решения задачи с такой формулировкой применим графический метод. Введем на плоскости прямоугольную систему координат Ou1u2 и построим ОДР данной задачи аналогично тому, как это было сделано в примере 1. Ограничительные условия определяют на плоскости многоугольник ABDEFG (рис. 12), вершины которого имеют соответственно координаты: (0; 40), (0; 80), (30; 80), (60; 50), (60; 0), (40; 0). Строим век-

тор С (–7; 1). Проводим линию уровня L0. Она задается уравнением 7u1 + + u2 + 1 450=const. На рис. 12 построена линия уровня, соответствующая значению 1 450. Сначала найдем значения переменных u1, u2, при кото-

32

рых целевая функция принимает минимальное значение. Поэтому пере-

мещаем L0 в направлении, противоположном вектору С . Точкой выхода из ABDEFG является точка F. Следовательно, наименьшее значение

функции L(U) на ОДР достигается при u1 = 60, u2 = 0. Поэтому Lmin= –7·60 + + 0 + 1 450 = 1 030. Теперь найдем значения переменных u1, u2, при кото-

рых функция L(U) принимает максимальное значение. Перемещаем L0 по

направлению вектора С . При таком перемещении точкой выхода из шестиугольника ABDEFG является точка B(0; 80). Следовательно, Lmax= L(B) = = –7·0 + 80 + 1 450 = 1 530.

u2		u1 u2 110 0
100				u1 60 0
u2 80 0	B	D
80
60
u1 u2 40 0	A			E
40
20
С
			G	F
-20	O	20	40	60	80	100	u1
L0+					L0–
L0
Рис. 12. ОДР и целевая функция транспортной задачи

Таким образом,

Lmin= 1 030 при x11 = 60, x12 = 0, x13 = 50, x21 = 0, x22 = 80, x23 = 20; Lmax= 1 530 при x11 = 0, x12 = 80, x13 = 30, x21 = 60, x22 = 0, x23 = 40.

б) Сначала рассмотрим случай, когда в качестве критерия экономической эффективности выступает минимум указанной величины.

33

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

		60		0	50
Х опт =							,
			0	80	20

экономическая интерпретация которой, благодаря рис. 1, весьма прозрачна. При таком плане перевозок затраты будут минимальны, а именно

1 030.

Теперь рассмотрим случай, когда в качестве критерия экономической эффективности выступает максимум указанной величины:

Полученный в подпункте а ответ соответствует для варианта 2 оптимальному плану временнóй загрузки станков по выполнению каждой операции. Его также (как и для варианта 1) удобно записать в виде матрицы

		0		80	30
Х опт =
			60	0	40	.

Экономическая интерпретация полученной матрицы такова:

на первом станке имеет смысл выполнять вторую и третью операции продолжительностью 80 и 30 часов соответственно;

на втором — первую и третью операции продолжительностью 60

и40 часов соответственно.

При таком плане будет обработано наибольшее количество деталей, а именно 1 530.

Отметим одну немаловажную деталь. Иногда ЛПР, наряду с оптимальным планом, интересует такой план временнóй загрузки станков, при котором будет обрабатываться наименьшее количество деталей. Как правило, это происходит в том случае, когда по тем или иным причинам осуществить оптимальный план не удается. Поэтому приходится варьировать временнýю загрузку станков и, естественно, при этом нужно постараться исключить такой вариант, при котором будет обрабатываться наименьшее количество деталей. Для данной задачи таким вариантом является план, матрица которого имеет следующий вид:

60		0	50
				.
	0	80	20

При указанной временнóй загрузке станков будет обработано минимальное количество деталей, а именно, 1 030 (разница с оптимальным планом в 500(!) деталей). (Проведите аналогичное исследование для варианта 1, а именно, укажите такой план перевозок, при котором транспортные расходы будут наибольшими.)

34

4. Решение ЗЛП с тремя переменными

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

Напомним, что поверхностью уровня функции f(x1, x2, x3) называется множество всех точек пространства R3, в которых функция принимает некоторое постоянное значение. Согласно этому определению, для целевой функции L(X) = c1x1 + c2x2 + c3x3 + c произвольная поверхность уров-

ня L0 — это плоскость с вектором нормали С (c1, c2, c3). Рассмотрим применение алгоритма на конкретном примере.

Пример 5. Найти значения переменных x1, x2, x3, при которых функция L(X) = 3x1 – x2 + 2x3 принимает экстремальные значения при условии, что:

x3 4,

x1 2x2 x3 5, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

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

Ox1x2x3.

1. Начнем с решения максимизационной задачи. Шаг 1. Находим ОДР.

Построим граничные плоскости x3 = 4 и x1 + 2x2 + x3 = 5. Первая плоскость проходит через точку (0; 0; 4) параллельно плоскости Ox1x2. Уравнение второй плоскости представим уравнением в отрезках:

x1		x2	+	x3	1	(это возможно сделать в силу того, что плоскость
5		5 / 2	5

не проходит через начало координат). Следовательно, означенная плос-

кость пересекает оси координат в точках (5; 0; 0), (0; 52 ; 0) и (0; 0; 5).

Теперь определим соответствующие полупространства. Подставляем координаты точки (0; 0; 0) в неравенство x3 4. Они ему удовлетворяют. Следовательно, выбираем полупространство, содержащее указанную точку. Для определения полупространства, задаваемого неравенством x1 + + 2x2 + x3 5 , подставляем координаты той же самой точки. Они удовле-

35

творяют и ему. Следовательно, выбираем полупространство, также содержащее начало координат.

С учетом условий x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 находим пересечение полупространств. Им является изображенный на рис. 13 многогранник AOBA1O1B1. Полученный многогранник и есть искомая ОДР.

x3

A1

O1

B1

4

L0

С

B

–6

O

2

4 x2

A

x1

Рис. 13. ОДР и целевая функция в задаче с тремя переменными

Шаг 2. Строим вектор С (3; –1; 2).

Шаг 3. Проводим поверхность уровня L0. Поверхность уровня задается уравнением 3x1 – x2 + 2x3 = с (с = const). Положим с = 6 и запишем для

данного				значения с уравнение			поверхности уровня в отрезках:
	x1		x2	+	x3	1 . Следовательно,	L0 пересекает оси координат в точках
2			6	3

(2; 0; 0), (0; –6; 0) и (0; 0; 3). По этим точкам и построим выбранную поверхность уровня (рис. 13).

Шаги 4, 5. Перемещаем L0 по направлению вектора С . Точкой выхода из ОДР является точка A (рис. 14).

Следовательно, целевая функция имеет максимальное значение в этой

точке: Lmax = L(A) = 3 · 5 – 0 + 2 · 0 = 15.

2. Решим минимизационноу задачу. Шаги 1—3 те же, что и при решении соответствующей максимизационной задачи.

36

x3

A1

O1

B1

4

С

B

–15

–6

O

2

4 x2

A

x1

Рис. 14. Оптимальное положение целевой функции

Шаги 4, 5. Перемещаем L0 в направлении, противоположном вектору С . В этом случае точкой выхода из ОДР является точка B (рис. 14).

5 5

Следовательно, Lmin= L(B) = 3 · 0 – 2 + 2 · 0 = – 2 .

5. Применение графического метода при решении экономических задач

Задача 1 (Выбор оптимального рациона питания). Детская молочная кухня в суточный рацион питания для одного трехмесячного ребенка включает два продукта питания: смесь № 5 и В-рис, причем смеси № 5 должно войти в дневной рацион не более 400 г. Стоимость 100 г смеси № 5 составляет 0,7 руб., В-риса — 0,9 руб. Содержание питательных веществ в 100 г продукта, минимальные нормы потребления указаны в таблице 3. Определить оптимальный рацион питания, стоимость которого будет наименьшей.

			Таблица 3
Питательные	Минимальная норма	Содержание питательных
		веществ в 100 г продукта
вещества	потребления, г
		Смесь № 5	В-рис
Белки	14,0	2,8	3,2
Углеводы	32,9	4,7	8,3

37

Решение. Обозначим x1 — суточный объем потребления смеси № 5, кг; x2 — суточный объем потребления В-риса, кг.

Составим математическую модель задачи. Целевая функция будет иметь вид:

L(x) = 7x1 + 9x2 → min

при ограничениях:

28x1	32x2	14,0,
	83x2	32,9,
47x1
	x1 0,4,

x1 0, x2 0.

ABDE — область допустимых решений (рис. 15). Строим вектор С (7; 9). Линия уровня задается уравнением

7x1 + 9x2 = const.

	x2	C
		E
	A

x1 0,4

B

D L0

47x1 + 83x2 = 32,9

28x1 + 32x2 = 14,0

O

x1

Рис. 15. ОДР и целевая функция в задаче о рационе питания

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

С . Точкой выхода L0 из области допустимых решений является точка B, ее координаты определяются как пересечение прямых, заданных уравнениями

28x1 32x2 14,0,47x1 83x2 32,9.

38

Решая систему, получим приближенно координаты точки B(0, 133; 0,321), в которой и будет оптимальное решение, то есть

Xопт ≈ (0,133; 0,321),

при этом

L(X)min = L(B) ≈ 7 · 0,133 + 9 · 0,321 ≈ 3,82 (руб.).

Таким образом, детская молочная кухня должна в суточный рацион питания для одного трехмесячного ребенка включать 0,133 кг смеси № 5 и 0,321 кг В-риса, при этом стоимость такого рациона составит 3,82 руб.

Задача 2. Фирма, занимающаяся грузовыми перевозками, получила следующий заказ. На двух товарных складах находится сахар в количестве 110 и 100 т, который должен быть доставлен трем оптовым покупателям в количестве 60, 80 и 70 т соответственно. Как следует организовать доставку сахара оптовым покупателям, чтобы суммарный доход от перевозок был максимальным, если доход в условных денежных единицах от каждой перевозки 1 т сахара задан матрицей

15		11	8
					?
	6	2	4

Решение. Общий объем запасов на складах совпадает с общим объемом запросов покупателей:

110 + 100 = 60 + 80 + 70 (т).

Следовательно, данная задача является закрытой транспортной задачей. Обозначим xij количество сахара (т), поставляемого с i-го (i = 1, 2) склада к j-му (j = 1, 2, 3) покупателю. Тогда соответствующая транспортная задача может быть сформулирована следующим образом.

Максимизировать суммарный доход от перевозок:

L(X) = 15x11 + 11x12 + 8x13 + 6x21 + 2x22 + 4x23 max

при условии, что

x11 + x12 + x13 = 110, x21 + x22 + x23 = 100, x11 + x21 = 60,

x12 + x22 = 80, x13 + x23 = 70,

x11 0, x12 0, x13 0, x21 0, x22 0, x23 0.

Введем новые переменные u1, u2, положив u1 = x11, u2 = x12, и выразим через них остальные. Заметим, что получили транспортную задачу, ограничительные условия которой совпадают с ограничительными условиями примера 4 из п. 3. Поэтому, обратившись к решению этого примера, получим

L(U) = 5u1 + 5u2 + 1 240 max

39

u1		u2 110 0,
	u1		60 0,
	u2		80 0,
	u	u	2	40 0,
	1

u1 0, u2 0.

Ограничительные условия определяют на плоскости многоугольник ABDEFG (рис. 16), вершины которого имеют соответственно координаты:

(0; 40), (0; 80), (30; 80), (60; 50), (60; 0), (40; 0). Строим вектор С (5; 5).

Проводим линию уровня L0. Находим значения переменных u1, u2, при которых целевая функция принимает максимальное значение. Перемеща-

ем L0 в направлении вектора С . Из рис. 16 видно, что максимального значения L(U) достигает в любой точке отрезка DE. Поэтому Lmax= L(D) = = 5 · 30 + 5 · 80 + 1 240 = 1 790. Задача имеет альтернативный оптимум и ее общее решение находится по формуле:

U опт (30; 80) (1 ) (60; 50) (60 30 ; 50 30 ), где

0 1.

u2

u1 u2 110 0

100

u1 60 0

u2 80 0

B

D

80

60

u1 u2 40 0

A

40

E

20

L0+

С

G

F

–20

O

20

40

60

80

100

u1

L0

Рис. 16. Альтернативный оптимум в транспортной задаче

40