Математика (стр. 7 )

Математическая модель.

5х1 + 9х2 £ 45

3х1 + 3х2 £

2х1 + х2 ≤10

х1 ³ 0 х2 ³ 0 ,

¦(Х) = 5х1 + 6х2 ¾ max.

Общая задача содержит два неизвестных и поэтому может быть решена графически.

Введем систему декартовых координат на плоскости х1Ох2 и построим множество планов задачи. Каждое линейное неравенство системы (1) определяет полуплоскость по одну сторону от граничной прямой, заданной соответствующим равенством. Множество планов задачи есть пересечение полуплоскостей, представляющее собой выпуклый многоугольник или выпуклую незамкнутую многоугольную область.

Построим каждую из граничных прямых по двум точкам (рис. 1).

(1) 5х1 + 9х2 = 45: (9, 0), (0,5);

(2) 3х1 + 3х2 = 19: (6,3; 0), (0;6,3);

(3) 2х1 + х2 = 10: (5, 0), (0,10).

Направление полуплоскости можно определить по одной точке, принадлежащей ей, например, точке О (0, 0). Если граничная прямая проходит через начало координат, то удобно проверять какую-либо точку, лежащую на одной из осей. В нашем случае при х1= 0 и х2= 0 неравенства системы (1) превращаются в верные числовые неравенства: 0 < 45, 0 < 19, 0 < 10. Следовательно, все три полуплоскости содержат точку О (0,0), то есть обращены к на чалу координат. На рис.1 это показано стрелками около каждой граничной прямой.

Так как х1 ³ 0, х2 ³ 0, то множество планов задачи (1) представляет собой общую часть трех полуплоскостей, попавшую в первую координатную четверть, то есть выпуклый пятиугольника (на рис. 1 он ОАВСД). Целевую функцию (Х) = 5х1 + 6х2 можно изобразить на плоскости в виде сетки параллельных прямых. Однако, достаточно построить одну прямую, соответствующую какому-либо значению функции, например, ¦(Х) = 18. Эта прямая пройдет через точки (3,6; О) и (0, 3). На рис. 1 она показана пунктиром. Далее передвигаем эту прямую параллельно самой себе в направлении от начала координат (в этом направлении целевая функция возрастает), пока она не встретит последнюю на своем пути точку области планов. Ее координаты найдем из системы уравнений прямых (1) и (2), пересекающихся в этой точке:

5х1 + 9х2 = 45,

3х1 + 3х2 =

х2

10

6.3

5

А В

X*= (3,10/3)

С ¦max

5 Д 6.3 9

0 ¦=18 х1

Рис. 1

Решив систему уравнений (2), получим х1 = 3, х2 =10/3 . Значит,

Х* = (3, 10/3) — оптимальный план задачи (1)

¦(Х*) = 5 × 3 + 6 × 10/3 = 35 — максимальное значение целевой функции (1).

Глава 4. Транспортная задача.

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

Постановка задачи

Пусть имеется m поставщиков и n потребителей некоторой однородной продукции. Известны мощности поставщиков - числа ai > 0 (i = 1, 2, ..., m), емкости потребителей - числа bj > 0 (j = 1, 2, . ., n) и числа сij > 0 (i = 1, 2, ..., m; j = 1, 2, ..., n) - стоимости перевозки единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, то есть указать, сколько единиц продукции каждый поставщик должен доставить каждому потребителю, чтобы суммарная стоимость перевозок была наименьшей. Если суммарная мощность поставщиков равна суммарной емкости потребителей, то есть

Sai = Sbj ,

то модель транспортной задачи называется закрытой, а в противном случае — открытой.

Условия транспортной задачи можно представить в виде следующей таблицы.

bj ai	b1	b2	¼	bn
a1	c11	c12	¼	c1n
a2	c21	c22	¼	c2n
¼	¼	¼	¼	¼
am	cm1	cm2	¼	cmn

(1)

Приведем математическую модель закрытой транспортной задачи. Пусть хij (i = 1, 2, ..., m; j = 1, 2, ..., n) — количество единиц продукции, перевозимой от i-го поставщика j-му потребителю. Тогда план перевозок можно представить в виде матрицы

х11 х12 … х1n

x21 x22 … x2n (2)

Х = … … … …

xm1 xm2 … xmn

Матричная модель.

х11 + х12 + … + х1n = a1,

х21 + х22 + … + х2n = a2,

…………………………………

xm1 + хm2 + … + хmn = am;

х11 + х12 + … + xm1 = b1, (3)

х12 + х22 + … + хm2 = b2,

…………………………………...

х1n + х2n + … + хmn = bn;

a1 + a2 + … + am = b1 + b2 + … + bn; (4)

xij ³ 0 (i = 1, 2, …, m; j = 1, 2, …, n); (5)

¦(X) = c11x11 + c12x12 + … + c1nx1n +

+ c21x21 + c22x22 + … + c2nx2n + (6)

………………………………..

+ cm1xm1 + cm2xm2 + … + cmnxmn ¾ min

В системе (3) первые m уравнений учитывают продукцию, вывозимую от поставщиков, последние n — продукцию, доставляемую потребителям. Условие (4) означает, что модель транспортной за дачи — закрытая. Целевая функция (6) выражает суммарную стоимость перевозок.

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

Критерий оптимальности плана перевозок. Для того чтобы

план перевозок Х* = (х*ij)i=1¸ m, j = 1¸ n был оптимальным, необходимо и достаточно, чтобы существовали числа

u1, u2,¼¼, um ¾ потенциалы поставщиков,

n1, n2, ¼¼, nn ¾ потенциалы потребителей,

удовлетворяющие следующим условиям:

10. ui + nj £ cij для всех i =1, 2,…., m; j = 1, 2,…, n;

20. если xij > 0 , то ui + nj = cij

Метод потенциалов так же, как и симплекс-метод, относится к группе методов последовательного улучшения плана. Приведем краткое описание алгоритма метода потенциалов, а более подробно рассмотрим его на примере.

Алгоритм метода потенциалов.

1. Построение исходного плана перевозок каким-либо из методов (“северо - западного угла” или наименьшей стоимости).

2. Проверка построенного плана на оптимальность при помощи критерия оптимальности плана перевозок.

3. Улучшение плана, то есть построение нового плана перевозок с меньшей (или равной) стоимостью перевозок.

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

bj ai	20	10	30
25	9	4	7
15	5	3	6
35	6	5	8

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

(7)

Требуется найти такой план перевозок, при котором суммарная стоимость перевозок будет наименьшей.

Прежде всего, подсчитаем суммарную мощность поставщиков и суммарную емкость потребителей:

а1 + а2 + а3 = 25+15+35 = 75;

b1+ b2 + b3 = 20+10+30 = 60.

Так как а1 + а2 + а3 > b1 + b2 + b3 то задача (7) является открытой моделью транспортной задачи и для сведения ее к закрытой модели введем фиктивного потребителя с емкостью

bф = (а1 + а2 + а3) - (b1 + b2 + b3) == 15.

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

bj ai	20	10	30	15
25	9	4	7	0
15	5	3	6	0
35	6	5	8	0

(8)

Решим полученную закрытую модель транспортной задачи (8) методом потенциалов с помощью описанного выше алгоритма. Составим исходный план перевозок Х1 методом “северо-западного угла”, распределяя мощности поставщиков по порядку между потребителями, так чтобы каждая перевозка была максимально возможной. У 1-го поставщика имеется 25 ед. продукции, а 1-му потребителю нужно 20 ед., следовательно, самое большее, ему можно направить 20 ед., то есть, положим, х11 = 20. Оставшиеся у первого поставщика 5 ед. направим 2-му потребителю, то есть, положим, х12 = 5. Не достающие 2-му потребителю 5 ед. направим ему от 2-го поставщика, то есть х22 = 5. Аналогично положим х23 = 10, х33 = 20, х34 = 15. Остальные перевозки, очевидно равны нулю.

План перевозок оформим в виде таблицы, разделенной на клетки. В центре каждой клетки плана поместим перевозки хij, а в правом верхнем углу — стоимости перевозки единицы продукции сij (i = 1, 2, 3; j = 1, 2, 3, 4). В клетки, соответствующие нулевым

перевозкам, нули не вписываем, оставляя их пустыми. В таком случае план Х1 будет иметь вид

	9		4	7	0	u1=0
20		5
5		3		6	0	u2=-1
5		10
6	5		8		0	u2=1
20		15
n1=9	n2=4	n3=7	n4=-1

X1=

При описанном выше способе распределения продукции план Х1 будет содержать не больше, чем m + n — 1 положительных перевозок или занятых клеток, где m — число поставщиков, n — число потребителей. Остальные компоненты плана Х1 соответствующие нулевым перевозкам, будем называть свободными клетками. Если число занятых клеток k = m + n — 1, то план перевозок называется невырожденным, если k < m+ n — 1, то — вырожденным. Для плана Х1 имеем: k = 6, m + n —1 = 6 и, значит, k = m + n—1. Следовательно, план Х1 является невырожденным. Заметим что если план перевозок окажется вырожденным, то следует часть свободных клеток условно считать занятыми, записан в них нули, так чтобы общее число занятых клеток было равно m + n — 1. В дальнейшем с этими нулями следует “обращаться” так же, как и с положительными перевозками.

Подсчитаем суммарную стоимость перевозок по плану Х

¦(Х1) = 9 ´ 20 + 4 ´ 5 + 3 ´ 5 + 6 ´ 10 + 8 ´ 20 + 0 ´ 15 = 180 + 20 + +15 + 60 + +160 = 435.

Проверим план Х1 на оптимальность. Найдем потенциалы u1, u2, u3 поставщиков и потенциалы n1, n2, n3,n4 потребителей, так чтобы выполнялись условия 10 и 20 критерия оптимальности плана перевозок.

По условию 20 для занятых клеток:

u1 + v1 = 9, u2 + v2 = 3, u3 + v3 = 8, u1 + v2 = 4, u3 + v3 = 6, u3 +v4 =

Один из потенциалов всегда задается произвольно, например, за дадим u1 = 0. Тогда из системы (9) получим v1 = 9, v2 = 4, u2 = -1, n3 = 7,u3 = 1, n4 = —1. Эти потенциалы полезно записать справа и снизу от плана Х1.

По условию 10 для свободных клеток:

u1 + v3 £ 7, u2 + v1 £ 5, u3 + v1 £ 6,

u1 + v4 £ 0, u2 + v4 £ 0, u3 +v1 £

Подставив потенциалы, найденные из уравнений (9), в неравенства (10), получим

0 + 7 = 7 = 7, -1 + 9 = 8 > 5, 1 + 9 = 10 > 6,

0 - 1 = -1 < 0,= -2 < 0, 1 + 4 = 5 =

Мы видим, что не выполняются два неравенства системы (70), причем

D21 = с21 - (u2 + n1) = 5 - 8 = -3,

D31 = с31 - (u3 + n1) = = -4.

Следовательно, план Х1 можно улучшить, введя в план перевозку х31= q, для которой разность D31 оказалась меньше разности D21. С этой целью составим так называемый цикл, имеющий начало в свободной клетке (3, 1), а остальные вершины — в занятых клетках последовательно увеличивая и уменьшая перевозки, попавшие в цикл, на величину q. В результате получим план Х2(q).

	9		4	7	0
20 - q		5 + q
5		3		6	0
5 - q		10 + q
	6	5		8		0
+q		20-q		15

Х2(q) =