Реализация модифицированного симплекс-метода

Числовой пример:

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

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30 кг	Потребитель B3,  потребность 30 кг	Потребитель B4,  потребность 10 кг
Поставщик A1,  запас 30 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг]	[4 руб./кг]
Поставщик A2,  запас 40 кг	[3 руб./кг]	[2 руб./кг]	[5 руб./кг]	[1 руб./кг]
Поставщик A3,  запас 20 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг]	[6 руб./кг]

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

Шаг 1:

Вычислим разницы между  двумя минимальными тарифами по строкам.

Строка 1: 2-2=0

Строка 2: 2-1=1

Строка 3: 3-2=1

И затем по столбцам.

Столбец 1: 3-2=1

Столбец 2: 3-2=1

• Столбец 3: 2-2=0
• Столбец 4: 4-1=3

Наиболее предпочтителен столбец 4, поскольку разница для него максимальна.

В столбце 4 найдем минимальную цену — 1 руб/кг в строке 2. В нашем примере это ячейка X₂₄ (2-й поставщик, 4-й потребитель), где цена доставки = 1 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 40 и 10 кг, то есть 10 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет.

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30 кг	Потребитель B3,  потребность 30 кг	Потребитель B4,  потребность 10-10=0 кг
Поставщик A1,  запас 30 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг]	[4 руб./кг]
Поставщик A2,  запас 40-10=30 кг	[3 руб./кг]	[2 руб./кг]	[5 руб./кг]	[1 руб./кг] 10 кг
Поставщик A3,  запас 20 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг]	[6 руб./кг]

 

Шаг 2

Вычислим разницы между двумя  минимальными тарифами по строкам (не учитывая закрашенные серым и  распределенные ячейки — см. таблицу выше).

• Строка 1: 2-2=0
• Строка 2: 3-2=1
• Строка 3: 3-2=1

И затем по столбцам.

• Столбец 1: 3-2=1
• Столбец 2: 3-2=1
• Столбец 3: 2-2=0

Есть несколько строк и столбцов с одинаковой предпочтительностью, возьмем любую из них, например строку 2, а в ней — выберем минимальный тариф, не учитывая (см. таблицу выше) закрашенные ячейки. В нашем примере это ячейка X₂₂ (2-й поставщик, 2-й потребитель), где цена доставки = 2 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (30 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет.

Возможности поставщика также исчерпаны, закрашиваем в серый цвет также  и строку.

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30-30=0 кг	Потребитель B3,  потребность 30 кг	Потребитель B4,  потребность 10-10=0 кг
Поставщик A1,  запас 30 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг]	[4 руб./кг]
Поставщик A2,  запас 40-10-30=0 кг	[3 руб./кг]	[2 руб./кг] 30 кг	[5 руб./кг]	[1 руб./кг] 10 кг
Поставщик A3,  запас 20 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг]	[6 руб./кг]

 

Шаг 3

Вычислим разницы между двумя  минимальными тарифами по строкам (не учитывая закрашенные серым и  распределенные ячейки — см. таблицу выше).

• Строка 1: 2-2=0
• Строка 3: 4-2=2

И затем по столбцам.

• Столбец 1: 4-2=2
• Столбец 3: 2-2=0

Есть строка и столбец с одинаковой предпочтительностью (максимальной разницей тарифов, равной 2 руб./кг), возьмем любой из них, например строку 3, а в ней — выберем минимальный тариф, не учитывая (см. таблицу выше) закрашенные ячейки. В нашем примере это ячейка X₃₃ (3-й поставщик, 3-й потребитель), где цена доставки = 2 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (минимальное значение между 20 и 30 кг, то есть 20 кг). Поскольку возможности поставщика полностью исчерпаны, закрашиваем соответствующую строку в серый цвет.

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30-30=0 кг	Потребитель B3,  потребность 30-20=10 кг	Потребитель B4,  потребность 10-10=0 кг
Поставщик A1,  запас 30 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг]	[4 руб./кг]
Поставщик A2,  запас 40-10-30=0 кг	[3 руб./кг]	[2 руб./кг] 30 кг	[5 руб./кг]	[1 руб./кг] 10 кг
Поставщик A3,  запас 20-20=0 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг] 20 кг	[6 руб./кг]

 

Шаг 4

Заполнение оставшихся ячеек (см. таблицу  выше) безальтернативно, алгоритмически (если мы пишем программу для ЭВМ) присваиваем разницы = 0, если число  нераспределенных ячеек в строке или столбце меньше двух.

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30-30=0 кг	Потребитель B3,  потребность 30-20-10=0 кг	Потребитель B4,  потребность 10-10=0 кг
Поставщик A1,  запас 30-20-10=0 кг	[2 руб./кг] 20 кг	[3 руб./кг]	[2 руб./кг] 10 кг	[4 руб./кг]
Поставщик A2,  запас 40-10-30=0 кг	[3 руб./кг]	[2 руб./кг] 30 кг	[5 руб./кг]	[1 руб./кг] 10 кг
Поставщик A3,  запас 20-20=0 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг] 20 кг	[6 руб./кг]

 

Дальнейшая оптимизация решения

Полученный результат распределения  составляет 2*20+2*10+2*30+1*10+2*20 = 170 рублей. Метод минимальных тарифов на этом же примере дал результат стоимостью 210 рублей, а метод северо-западного угла — 290 руб., то есть — наименее оптимальный. Проверить этот результат на оптимальность и, при необходимости, окончательно его оптимизировать можно при помощи метода потенциалов(который в этом примере показывает, что это распределение оптимально).

 

5. Решение транспортной  задачи методом Фогеля

 

Однородный груз сосредоточен у трех поставщиков в объемах 9, 16 и 5 тонн. Данный груз необходимо доставить  четырем потребителям в объемах 11, 7, 8 и 4 тонн. Известны стоимости единицы  груза от каждого поставщика каждому  потребителю.

2  5  8  1

8  3  9  2

7  4  6  3

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

Математическая модель транспортной задачи:

F = ∑∑c_ijx_ij,    (1)

при условиях:

∑x_ij = a_i,  i = 1,2,…, m,   (2)

∑x_ij = b_j,  j = 1,2,…, n,   (3)

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

	1	2	3	4	Запасы
1	2	5	8	1	9
2	8	3	9	2	16
3	7	4	6	3	5
Потребности	11	7	8	4

Проверим необходимое  и достаточное условие разрешимости задачи.

∑a = 9 + 16 + 5 = 30

∑b = 11 + 7 + 8 + 4 = 30

Занесем исходные данные в  распределительную таблицу.

	1	2	3	4	Запасы
1	2	5	8	1	9
2	8	3	9	2	16
3	7	4	6	3	5
Потребности	11	7	8	4

Этап I. Поиск первого опорного плана.

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

	1	2	3	4	Запасы
1	2[9]	5	8	1	9
2	8[2]	3[7]	9[3]	2[4]	16
3	7	4	6[5]	3	5
Потребности	11	7	8	4

Сведем все вычисления в одну таблицу.

	1	2	3	4	Запасы	d1	d2	d3	d4
1	2[9]	5	8	1	9	1	-	-	-
2	8[2]	3[7]	9[3]	2[4]	16	1	1	1	5
3	7	4	6[5]	3	5	1	1	-	-
Потребности	11	7	8	4
d1	5	1	2	1
d2	1	1	3	1
d3	0	0	0	0
d4	0	0	0	-