Исследование очередного решения на оптимальность

Пример № 1

На трех базах находится однородный груз. На базе А₁ в количестве 300 т., на базе А₂ в количестве 150 т., на базе А₃ в количестве 50 т. Весь этот груз необходимо развести четырем заказчикам так, чтобы стоимость перевозок была наименьшей. Заказчику в пункте В₁ должно поступить 170 т., в пункте В₂ – 110 т., в пункте В₃ – 100 т., в пункте В₄ – 120 т. Расстояния между базами и пунктами назначения приведены в таблице 1 в угловых скобках.

Таблица 1

Базы	Заказчики	Запасы на базах
В1	В2	В3	В4
А1				—	300 т.
А2	—	—			150 т.
А3	—	—	—		50 т.
Потребности заказчика	170 т.	110 т.	100 т.	120 т.	500 т. 500 т.

 

Решение

1. Описание транспортной задачи как задачи линейного программирования

Пусть из i-ой базы (i = ) j-му заказчику (j = ) доставлено х_ij тонн груза. От j-го заказчика i-я база находится на известном расстоянии с_ij (км), указанном в таблице 1 в угловой скобке. В этом случае х_іjс_іj есть количество тонно-километров необходимое для такой перевозки. Рассматривая в произведениях х_іjс_іj всевозможные комбинации значений индексов i и j, получим для каждой такой комбинации свое значение тонно-километров. Из суммы этих произведений образуется общая стоимость перевозок F, выраженная в тонно-километрах

. (1)

Требуется найти такой план перевозок (х₁₁, х₁₂,…, х₃₄), который минимизирует его стоимость. Этот план перевозок называется оптимальным.

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

Покажем, что транспортная задача есть частный случай задачи линейного программирования. Действительно, целевая функция F в ней это линейная функция вида (1) относительно определяемых переменных х_іj. Линейной является и система ограничений, на которой требуется найти минимум функции F. Так в примере №1 система ограничений представлена уравнениями

х₁₁ + х₁₂ + х₁₃ + х₁₄ = 300,

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 150,

х₃₁ + х₃₂ + х₃₃ + х₃₄ = 50,

х₁₁ + х₂₁ + х₃₁ = 170,

х₁₂ + х₂₂ + х₃₂ = 110,

х₁₃ + х₂₃ + х₃₃ = 100,

х₁₄ + х₂₄+ х₃₄ = 120.

Особенность системы ограничений в транспортных задачах состоит в том, что коэффициенты при неизвестных во всех уравнениях системы ограничений равны 1. Эта особенность позволяет предположить метод решения транспорт- ной задачи, отличный от симплекс-метода.

 

Примечание. Часто с_ij означают не расстояния между базами и заказчиками, а стои-мость перевозки одной тонны груза между ними. Очевидно, что эта стоимость пропорциональна расстоянию. Поэтому, если х_іj – количество тонн груза, перевозимого из i-ой базы j-му заказчику, то функция (1) означает в этом случае стоимость всех перевозок, выраженную не в тонно-километрах, а в рублях.

2. Формирование опорного решения (опорного плана перевозок) методом северо-западного угла

При формировании опорного плана методом северо-западного угла, заполняется левая верхняя клетка (северо-западный угол) исходной таблицы или её оставшейся части. После заполнения северо-западного угла с учетом предельных возможностей базы, лежащей с заполняемой клеткой в одной строке, из таблицы исключается или очередной столбец слева, или очередная строка сверху. Так в данной таблице потребность заказчика В₁ может быть полностью удовлетворена базой А₁ (а₁ = 300; в₁ = 170; а₁ > в₁). Полагая х₁₁=170, вписываем это значение в клетку (1;1) и исключаем из рассмотрения первый столбец.

На базе А₁ остается 130 т. груза (). В новой таблице с тремя строками А₁, А₂, А₃ и тремя столбцами В₂, В₃, В₄ северо-западным углом оказывается клетка (1;2). Первая база с оставшимися 130 т. груза может полностью удовлетворить потребность второго заказчика В₂ ( > в₂). Полагая х₁₂ = 110, вписываем это значение в клет-ку (1; 2) и исключаем из рассмотрения второй столбец. На базе А₁ остается 20 т. груза ().

В новой таблице с тремя строками А₁, А₂, А₃ и двумя столбцами В₃, В₄ северо-западный угол соответствует клетке (1;3). Теперь третий заказчик

В₃ может принять весь запас с базы А₁ ( < в₃ ). Полагая

х₁₃ = 20, вписываем это значение в клетку (1;3) и исключаем из рассмотрения первую строку. Но потребность заказчика В₃ оказалась не удовлетворенной (). Эту потребность может удовлетворить база А₂. После чего в ней останется (т. груза). Записывая в клетку (2;3) х₂₃ = 80 мы полностью удовлетворяем потребность заказчика В₃ и вычеркиваем третий столбец. Теперь на северо-западе находится клетка (2;4) и потребность заказчика В₄ будет частично удовлетворяться остатками груза с базы А₂. Таким образом,

х₂₄ = 70, что приводит к исключению второй строки в таблице 1. А не вполне удовлетворенная потребность заказчика В₄ () удовлетворяется запасами груза с базы А₃. При этом х₃₄ = 50.

Опорный план составлен. Ошибки в его составлении можно обнаружить, если найти суммы указанных значений х_іj по строкам и сравнивать их на равно с запасами груза на базах. Суммы х_іj по столбцам сравниваются на равно с потребностями заказчиков.

3. Циклы пересчета в таблице перевозок

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

Циклом пересчета в таблице перевозок называется последовательность переменных х_іj, удовлетворяющих следующим условиям:

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

2) каждые две последовательные переменные, входящие в цикл, могут находиться только на одной строке или только в одном столбце;

3) каждая строка или столбец данного цикла может содержать только две переменные;

4) каждый цикл замкнут. То есть, при последовательном обходе выбранных переменных цикл начинается и заканчивается одной и той же клеткой.

Если для свободной клетки исходной таблицы, заполненной методом северо-западного угла, можно построить цикл пересчета, то такой цикл является единственным. Число вершин в этом цикле чётно. Если же для какой-либо свободной клетки исходной таблицы цикл пересчета построить нельзя, то для реализации этой возможности некоторые из свободных переменных обращаются в базисные переменные с нулевыми значениями (в пустых клетках записываются нули. См. пример № 2). Решение, содержащее нулевые значения базисных переменных, называется вырожденным.

Укажем циклы пересчета для всех свободных клеток таблицы 1 и пере-распределение груза в них по следующим правилам:

а) снабдим свободную клетку знаком (+) и с каждым переходом к следую-щей клетке цикла будем изменять знак на противоположный;

б) в клетках, отмеченных знаком (-) выберем наименьшее из чисел. Это то количество груза, которое будет последовательно перевозиться из одной клетки в другую. Из клеток, отмеченных знаком (-), зафиксированное количество груза вывозится; в клетках со знаком (+) – прибывает.

Циклы пересчета в примере №1:

1)

 

F = 70·170 + 50·110 + 80·20 + 40·100 + 60·50 + 11·50 = 26 550 (т.км.);

 

2)

 

F = 70 · 90 + 50 · 110 + 15 · 100 + 80 · 80 + 60 · 70 + 11 · 50= 24 450 (т.км.);

 

 

3)

 

F = 70 · 170 + 50 ·30 + 15 ·100 + 80 · 90 + 60 · 70 + 11 · 50 = 26 850 (т.км.);

 

 

4)

F = 70 ·120 + 50 ·110 + 15 ·70 + 40 ·30 + 60 ·120 + 50 · 50 = 25 850 (т.км.);

5)

 

F = 70 · 170 + 50 · 60 + 15 · 70 + 40 ·30 + 60 ·120 + 10 · 50 = 24 850 (т.км.);

 

6)

 

F = 70 ·170 + 50 ·110 + 15 · 20 + 40 · 30 + 60 ·120 + 90 ·50 = 30 600 (т.км.);

 

Следует сравнить стоимость перевозок в каждом цикле со стоимостью перевозок по опорному (первоначальному) плану

F_нач = 70·170 + 50·110 + 15·20 + 40·80 + 60·70 + 11·50 = 25650 (т.км.)

и выбрать наименьший из всех результатов – результат (2), который представ-лен в таблице 2.

Таблица 2

Базы