Методы оптимальных решений (стр. 11 )

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

х11 х12 … х1n

x21 x22 … x2n (62)

Х = … … … …

xm1 xm2 … xmn

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

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

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

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

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

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

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

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

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

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

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

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

+ c21x21 + c22x22 + … + c2nx2n + (66)

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

+ cm1xm1 + cm2xm2 + … + cmnxmn ¾ min

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

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

Критерий оптимальности плана перевозок. Для того чтобы план перевозок Х* = (х*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

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

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

Прежде всего, подсчитаем суммарную мощность поставщиков и суммарную емкость потребителей: а1 + а2 + а3 = 25+15+35 = 75; b1+ b2 + b3 = 20+10+30 = 60.

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

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

(67)

Решим полученную закрытую модель транспортной задачи (67) методом потенциалов с помощью описанного выше алгоритма. Составим исходный план перевозок Х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=