Файл: Золотарь, И. А. Экономико-математические методы в дорожном строительстве.pdf

Так как суммы по горизонтальным строкам и вертикальным столбцам по-прежнему должны равняться соответствующим значе­ ниям а и Ь, то величину 0i необходимо вычесть из *2з и Хц и при­

бавить К *13 .

Так как компоненты плана хц не должны быть отрицательны­ ми, то ясно, что величина 0! ограничивается теми Хц, из которых она вычитается. Как известно, транспортная задача представляет собой частный случай общей задачи линейного программирования, когда для определения пт неизвестных (в табл. 17 т —2 и п = 4) имеется п+ т— 1 линейных уравнений типа (V.2) — (V.6) *. Поэтому при введении в первичный опорный план перевозки * 2 4 необходимо

принять такое значение 0ь чтобы исключить одну из переменных ^преж него опорного плана. Примем 0i = 2. При этом получим лишь четыре положительных компонента плана. Так как необходимо иметь п + т— 1=5 неотрицательных компонентов плана, то введем

вопорный план одну из нулевых перевозок, в частности перевозку

*12, ибо вторая нулевая перевозка *ц характеризуется большей

стоимостью (cn > ci2). Можно было бы ввести *н для фиктивного объекта работ, однако в данной задаче это потребовало бы двух лишних итераций при оптимизации опорного плана. С учетом при­ веденных положений получим следующий опорный план:

Исследуем данный план на оптимальность, для чего составим систему уравнений типа (V.26):

Приняв по-прежнему Ui = 0, получим:

У 2=0,6; V"з= 0,3; £ /,= 0,4; 1/1 = 0,1; К4= - 0 , 4 .

* Обоснование этого положения дано на стр. 89.

80

Внесем полученные значения Ui и Vj во вспомогательную табли­ цу (табл. 19) и покажем в ней полужирным шрифтом Ui+Vj = Cij для переменных, входящих в новый опорный план. Светлым шриф­ том вписаны величины Cij=Ui + Vj для переменных, не входящих в

= —0 ,0 5 < 0 .

Таким образом, условие (V.28) выполняется и полученный план перевозок является оптимальным.

Решение нашей задачи дается следующей матрицей:

Очевидно, что удовлетворяются и условия (V.2)-—(V.6 ), ибо

Рассмотрим на конкретном примере еще один весьма эффектив­ ный метод оптимизации опорных планов в транспортной задаче ли­ нейного программирования.

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

ведены стоимостные характеристики перевозок для 1 м3 материала:

81

Методом северо-западного угла легко найдем опорный план пе­ ревозок:

Если вычислить значение целевой функции для данного опорно­ го плана, то получим

£ = 4 - 0 ,4 + 5 - 0 ,1 + 1-0,24-6-0,3+6-0,5+3-0,4 + 9-0,8= 15,5.

Оптимизацию опорного плана произведем методом «лестницы»

(«stepping stone»).

Суть метода состоит в том, что вместо нулевых перевозок в опор­ ном плане последовательно вводятся единичные перевозки (по од­ ной на каждый шаг оптимизации) и проверяется, будет ли возрас­ тать или уменьшаться значение L целевой функции. Если выявля­ ется перевозка, уменьшающая значение L, то строится новый опорный план и его оптимизация продолжается тем же методом. Если внесение перевозок в любую из нулевых клеток очередного опорного плана приводит к увеличению L, то данный опорный план является оптимальным.

Внесем единичную перевозку в клетку (1 ,4) опорного плана. Тогда для соблюдения ограничений в нашей задаче необходимо уменьшить на единицу объем перевозок х\г, увеличить на единицу перевозку х23 и уменьшить на единицу перевозку лг24Обозначим из­ менение значения целевой функции через AL. Приводимая ниже вспомогательная матрица показывает все изменения в перевозках, появляющиеся от введения единичной перевозки хи. Для наглядно­ сти в соответствующих клетках матрицы показаны стоимостные характеристики перевозок Хц.

82

Введение перевозки х 14 приводит к увеличению значения целе­ вой функции и потому нецелесообразно.

Для выяснения того, насколько целесообразна перевозка Х15, за­ пишем вспомогательную матрицу, из которой видно, что внесение единичной перевозки в клетку х г5 заставляет внести изменения еще в пять клеток плана.

ДL1B= - 1 -0 ,2 + 1 -0 ,9 + 1 - 0 ,3 - 1 -0 ,5 + 1 -0,4— 1 .0 ,8 = 0 ,!.

Таким образом, введение перевозки jcjs также увеличивает зна­ чение целевой функции и потому нецелесообразно.

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

- 1 -0 ,4 + 1 -0 ,2 + 1 - 0 ,6 - 1 -0 ,3

83

д122= - 1 -0,1 + 1 -0,2+ 1 - 0 ,4 - 1 -0,3 = 0,2.

84

Таким образом, только введение перевозки х25 уменьшает зна­ чение целевой функции A L 25 <0 и потому целесообразно. Возникает вопрос, какой объем перевозок необходимо внести в клетку ^25Введение перевозки х2ъ затронет те клетки опорного плана, которые были показаны во вспомогательной матрице при вычислении AL2s (в опорном плане эти клетки обведены двойными линиями). Вводя х25, необходимо уменьшить х24 и х35, т. е. те, для которых во вспомо­

85