2015-06-30
389
Решение задачи о перевозке холодильных установок начнем с опорного плана, построенного методом северо-западного угла:
| Лейпциг | Лион | дополнительный центр сбыта | ai | |
| Стокгольм | ||||
| Триест | ||||
| Руан | ||||
| bj | 150 |
Здесь базисными являются переменные x11, x21, x22, x32 и x33. Построим для них систему уравнений:
u1 + v1 = 25
u2 + v1 = 18
u2 + v2 = 8
u3 + v2 = 6
u3 + v3 = 0
Число уравнений m + n – 1 = 5, число неизвестных m + n = 6. Следовательно, решений бесконечно много. Необходимо найти хотя бы одно.
Для этого зафиксируем любую неизвестную равной любому числу. Например, пусть u1 = 0, тогда из первого уравнения v1 = 25, из второго
u2 = 18 – 25 = -7, из третьего v2 = 8 – (-7) = 15, далее u3 = -9 и v3 = 9.
Суммы потенциалов будем записывать в правых нижних углах клеток (заполним их величинами (ui + vj)).
| v1 = 25 | v2 = 15 | v3 = 9 | ai | |
| u1 = 0 | ||||
 25
| 0+15=15 | 0+9=9 | ||
| u2 = -7 | ||||
| -7+9=2 | ||||
| u3 = -9 | ||||
| -9+25=16 | ||||
| bj |
Для пересчета плана можно выбрать любую небазисную переменную, так как здесь во всех незаполненных клетках критерий оптимальности нарушается (15 > 14; 9 > 0; 2 > 0; 16 > 12)
Выберем, например, клетку x31, где критерий оптимальности также нарушен (16 > 12), и построим цикл. В данном примере у него будет 4 вершины, одна из которых находится в пустой клетке (соответствует небазисной переменной х31), а остальные соответствуют базисным переменным х21, х22 и х32. Осуществим его разметку.
Наименьшее число из базисных компонент, помеченных знаком «-» (т.е. из 30 и 80), равно 30. Это и будет величина пересчета плана.
Новый опорный план строится следующим образом: в пустой клетке ставят число 30 (величину пересчета плана) - эта переменная входит в базис (из Руана в Лейпциг поставляется х31 = 30 установок). Переменная, соответствующая поставкам из Триеста в Лейпциг (раньше она равнялась 30), выходит из базиса, становится равной нулю (х21 = 0), и эта клетка в таблице остается незаполненной. Изменятся также поставки из Триеста и Руана в Лион. К этим вершинам цикла прибавляют или вычитают 30 в зависимости от того, каким знаком они помечены, поэтому х22 = 10 + 30 = 40, а х32 = 80 – 30 = 50.
Итак, в новом опорном плане в базисе останутся все те же переменные, кроме одной - х31 = 30. Для этой переменной u3 + v1 > х31; следовательно, по теореме об изменении плана транспортной задачи на новом опорном плане целевая функция уменьшится на xi1j11(ui1 + vj1 - сi1j1) = 30*(16 - 12) = 120, т.е. перевозки будeт дешевле на 120 ф.ст. Можно убедиться, что это действительно так, путем подстановки нового плана в целевую функцию: 25x11 + 14x12 + 18x21 + 8x22 + 12x31 + 6x32 = 25*120 +
+ 8*40 + 12*30 + 6*50 = 3980 (ф.ст.) (это на 120 ф.ст. меньше, чем 4100 ф.ст. – оплата перевозок по плану, построенному МСЗУ).
Почему нельзя было просто поменять значениями переменные х31 и х21, не занимаясь построением цикла и не изменяя значения других переменных (или просто ввести в базис х31 вместо любой другой переменной)? Легко убедиться, что в этом случае новый план не будет допустимым (суммы значений переменных по строкам и столбцам не будут равняться объемам производства и сбыта), следовательно, план не будет и опорным.
Почему для пересчета плана была выбрана именно клетка x31 (ведь можно выбрать любую из нескольких переменных, для которых был нарушен критерий оптимальности)? При выборе из всех клеток той переменной, которая будет введена в базис, целесообразно заранее определить, на сколько изменится целевая функция при переходе к новому опорному плану (для этого нужно определить величину пересчета плана и умножить ее на разность между суммой потенциалов и коэффициентом целевой функции). Для данного примера при вводе в базис переменной х12 перевозки подешевели бы на 10*(0 + 15 - 14) = 10 (чтобы найти величину пересчета плана – 10 – студентам предлагается самостоятельно построить цикл для клетки х12). Путем аналогичных рассуждений получим, что для х13 перевозки подешевели бы на 10*(0 + 9 - 0) = 90, а для х23 - на 20 ф.ст. Следовательно, выбранный нами вариант обеспечивает наибольшее удешевление перевозок.
Построим новый опорный план и снова найдем для него потенциалы:
| v1 = 25 | v2 = 19 | v3 = 13 | ai | |
| u1 = 0 |  120
| |||
| u2 = -11 | ||||
| u3 = -13 | ||||
| bj |
Здесь критерий оптимальности нарушается для трех переменных: х12, x13 и x23. Введем в базис переменную х12. Тогда величина пересчета плана равна 50, и новый опорный план примет следующий вид:
| v1 = 25 | v2 = 14 | v3 = 13 | ai | |
 25
| ||||
| u1 = 0 | ||||
| u2 = -6 | ||||
| u3 = -13 | ||||
| bj |
Далее аналогично:
 v1 = 25
| v2 = 14 | v3 = 0 | ai | |
| u1 = 0 | ||||
| u2 = -6 | ||||
| -6 | ||||
| u3 = -13 | ||||
| -13 | ||||
| bj |
| v1 = 25 | v2 = 14 | v3 = 0 | ai | |
| u1 = 0 | ||||
| u2 = -7 | ||||
| -7 | ||||
| u3 = -13 | ||||
| -13 | ||||
| bj |
Полученный план оптимален. В этом плане х11 = 20, х12 = 90, х13 = 10, х21 = 40, х31 = 90, а все остальные переменные равны нулю. Оптимум можно рассчитать подстановкой этих чисел в выражение для целевой функции: 25*20 + 14*90 + 0*10 + 18*40 +12*90 = 3560. Это означает, что самый дешевый план перевозок холодильных установок состоит в следующем: следует поставить в Лейпциг 20 установок из Стокгольма, 40 из Триеста и 90 из Руана. Из оставшихся в Стокгольме установок 90 штук поставляются в Лион и 10 остаются невостребованными. Затраты на такие перевозки составят 3560 ф.ст. Это ответ задачи.
Транспортная задача может иметь и более одного оптимального плана, если есть небазисная клетка, в которой сумма потенциалов равна коэффициенту целевой функции. Чтобы найти другой оптимальный план, нужно пересчитать план, введя в базис эту клетку. При переходе к новому плану значение целевой функции не изменится. В самом деле, оно должно измениться на xi1j11(ui1 + vj1 - сi1j1), а эта величина равна нулю (т.к. второй сомножитель – нулевой). Однако, если и величина пересчета плана xi1j11 равна нулю, то и сам план не изменится (из вырожденного базиса выйдет одна нулевая переменная, и вместо нее войдет другая, тоже нулевая). Поэтому, чтобы альтернативное решение действительно существовало, нужно еще, чтобы величина пересчета плана была отлична от нуля.
При этом следует помнить, что если задача непрерывная, то наличие двух оптимальных планов говорит о том, что их существует бесконечное множество: любая смесь этих планов (точка на отрезке между ними) – также оптимальный план.
