Решение задач линейного программирования транспортного типа: Методические указания к выполнению индивидуальных домашних заданий, страница 7

                                             x₂₁ + x₂₂ + x₂₃               = 53,                                              (2.2)

                                             x₃₁ + x₃₂ + x₃₃               = 45,                                               (2.3)

                                                  x₄₁ + x₄₂ + x₄₃               = 24,                                               (2.4)

                                                  x₁₁ + x₂₁ + x₃₁  + x₄₁ = 90,                                               (2.5)                                                                                                                                                                                                                         x₁₂ + x₂₂ + x₃₂  + x₄₂ = 61,                                              (2.6)

                                             x₁₃ + x₂₃ + x₃₃  + x₄₃ = 45,                                              (2.7)

                                             x_ij  0,       i =; j = ,                                            (2.8)

                               P = –3x₁₁ – 5x₁₂ – 3x₁₃ – 7x₂₁ – 3x₂₂ – 7x₂₃ – 6x₃₁ – 3x₃₂ –
                                               – 5x₃₃ –  8x₄₁ – 5x₄₂ – 5x₄₃ min.                                  (2.9)

Таким образом, задача (2.1) – (2.9) представляет собой задачу транспортного типа и в дальнейшем используется терминология транспортной задачи.

2.1. Для нахождения начального опорного плана используем метод минимального элемента. Кратко опишем схему этого метода.

В транспортной таблице находится клетка с минимальным тарифом. Если таких клеток несколько, то берется любая из них. Пусть это клетка (i, j). Тогда сравниваются запасы поставщика a_i и потребность потребителя b_j. В качестве перевозки берется величина x_ij = min{a_i, b_j}. Если a_i < b_j, то закрывается строка i; если же a_i > b_j, то закрывается столбец j. Если a_i = b_j, то закрываются одновременно и строка, и столбец, а в одну из клеток, расположенных в этой строке или столбце, заносится 0 (нулевая перевозка). Затем среди оставшихся клеток таблицы выбирается клетка с наименьшим тарифом, и в нее записывается максимально возможная перевозка. Процесс продолжается до тех пор, пока не будет получен опорный план перевозок, возможно, вырожденный.

Применим этот метод к транспортной таблице решаемой задачи (см. табл. 2.0). Ищем минимальный элемент (наименьший транспортный тариф): c₄₁ = – 8. В клетку (4, 1): помещаем перевозку x₄₁ = min{a₁, b₁} = min{24, 90} = 24. Четвертая строка закрывается, так как запас четвертого поставщика исчерпан.

В оставшейся части таблицы снова находим минимальный элемент: c₂₁ = –7. Определим поставку, которую нужно занести в клетку (2,1). Предложение второго поставщика a₂ = 53 единицы, а спрос первого потребителя b₁ частично уже удовлетворен предыдущей поставкой x₄₁. Он теперь равен b₁′ = b₁ – x₄₁ = 90 – 24 = 66 единиц. Отсюда x₂₁ = min{a₂, b₁′} = min{53, 66} = 53. Вторая строка закрывается, так как исчерпан запас второго поставщика.

Находим в оставшейся части таблицы наименьший элемент: c₃₁ = –6. Определим поставку, которую нужно занести в клетку (3, 1). Запас третьего поставщика a₃ = 45 единиц, а спрос b₁′ у первого потребителя уменьшился на величину предыдущей поставки x₂₁ и стал равен b ₁′′ =  b₁′ – х₂₁ = 66 – 53 = 13 единиц. Отсюда, х₃₁ = min{45, 13} = 13. Первый столбец закрывается, так как спрос первого потребителя полностью удовлетворён.

Среди оставшихся тарифов наименьшим будет с₃₃ = –5. Определим поставку, которую нужно занести в клетку (3, 3). У третьего поставщика неиспользованный запас составляет a₃ – х₃₁ = 45 – 13 = 32 единицы. У третьего потребителя объём потребности b₃ = 45, значит х₃₃ = min {32, 45} = 32 единицы. Этой поставкой полностью исчерпано предложение третьего поставщика, поэтому третья строка закрывается.

Среди оставшихся клеток выбираем минимальный элемент: с₁₂ = –5. Следовательно, в клетку (1, 2) отправляется поставка х₁₂ = min{a₁, b₂} = min{74, 61} = 61. Второй столбец закрывается, поскольку спрос второго потребителя полностью удовлетворён этой поставкой.

Среди оставшихся клеток выбираем минимальный элемент с₁₃ = –3 и определяем величину поставки в клетку (1, 3): х₁₃ = min{a₁′, b₃′}. Так как предложение первого поставщика a₁ = 74 уменьшилось на величину предыдущей поставки х₁₂ = 61, то оставшийся запас a₁′ = a₁ – х₁₂ = 74 – 61 = 13. В то же время спрос третьего потребителя b₃ = 45 уменьшился за счёт поставки х₃₃ = 32 и составляет на данный момент величину b₃′ = b₃ – х₃₃ = 45 – 32 = 13. Таким образом, х₁₃ = min{13, 13} = 13.

Полученный опорный план Х₀ содержит 6 занятых клеток с положительными поставками и, следовательно, является невырожденным (m + n – 1 = 4 + 3 – 1 = 6).

Обычно в смысле близости к оптимальному решению опорный план, построенный этим методом лучше плана, полученного методом северо-западного угла.  

Таблица 2.0

bj ai	90	61	45	Ui
74	-3	-5     61	-3     13	0
53	-7      –    53	-3	-7      +	3
45	-6    13 +	-3	-5    32 –	2
24	-8    24	-5	-5	4
Vj	-4	-5	-3	P0 = -1145

Получен первоначальный опорный план Х₀ методом минимального элемента, для которого значение целевой функции P₀ = –1145.

 

                –   61 13

 Х₀ =    53  –    –    ,    Р₀ = –1145.

            13   –   32

            24   –   –

2.2. Дальнейшее решение продолжим методом потенциалов.

Шаг 1. Используем условие (6) критерия оптимальности плана транспортной задачи (см. стр. 6) для задачи (2.1) – (2.9). Пусть U₁ = 0. Тогда

                                V₂ = U₁ + C₁₂ = 0 – 5 = –5,

                                  V₃ = U₁ + C₁₃ = 0 – 3 = –3,

                                  U₃ = V₃ – C₃₃ = –3 – (–5) = 2,

                                  V₁ = U₃ + C₃₁ = 2 – 6 = –4,

                                  U₂ = V₁ – C₂₂ = – 4 – (–7) = 3,

                                  U₄ = V₁ – C₄₁ = – 4 – (–8) = 4.

Далее рассчитываются значения ∆_ij = V_j – U_i – C_j для всех свободных клеток по условию (7) критерия оптимальности: