§6. Транспортная модель

Транспортная модель используется при разработке плана перевозок одного вида продукции из нескольких пунктов отправления в пункты назначения. Задача – нахождение оптимального плана перевозок. При построении траспортной модели используются следующие величины:

1) Величины, характеризующие объем продукции в каждом исходном пункте и спрос в каждом пункте назначения. 2) Стоимость перевозки единицы продукции из каждого исходного пункта в пункт назначения.

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

Основное предположение:

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

Предположим, что

а_i – количество продукции, производимой в пункте i.

b_j – количество продукции, потребляемой в пункте назначения j.

С_ij – стоимость перевозки единицы продукции из пункта i в j.

x_ij – количество продукции, перевозимой из i в j.

Сформулируем задачу; как задачу Л. П.

при ограничениях:

- Если здесь равенство, то такая транспортная модель (Т.М.) называется сбалансированной.

§7. Решение транспортной задачи

Алгоритм решения:

Этап1: Найти начальное допустимое базисное решение. Базисных решений должно быть m+n-1.

Этап2: Найти включаемую в базис переменную. Если все небазисные переменные удовлетворяют условию оптимальности симплекс-метода, то вычисления заканчиваются. В противном случае перейти к третьему этапу.

Этап3: Найти исключаемую из базиса переменную. Найти новое базисное решение и вернуться к этапу 2.

Решаем транспортную задачу. Рассмотрим пример.

П

0

20

11

ример: Дана таблица стоимостей

10 20 12 7 9 5 х11	10 х12	х13	х14	15
х21	5 х22	15 х23	5 х24	25
0 16 18 14 0 х31	х32	х33	5 х34	5
5	15	15	10

Решение по этапам.

Этап 1. Есть несколько методов нахождения базисного решения.

Самый удобный – метод северо-западного угла.

Базисных переменных: 3+4-1=6 штук.

Приписывают переменной х₁₁ максимальное значение, допустимое ограничениями на спрос и объем. (В данном случае это – 5.)

После этого вычеркивают соответствующий столбец или строку. Это означает, что остальные элементы вычеркнутого столбца (строки) равны 0. Если ограничения выполняются одновременно, то выбор строки или столбца определяется произвольно.

После того, как спрос и объем производства во всех невычеркнутых строках и столбцах приведены в соответствии с установленным значением переменных; максимальное допустимое значение приписывается первому невычеркнутому элементу нового столбца или строки.

Процесс завершается, пока остается невычеркнутой одна строка или столбец.

В данном случае:

1) х₁₁=5 Вычеркиваем столбец 1.

2) х₁₂=10 Вычеркиваем строку 1.

3) х₂₂=5 Вычеркиваем столбец 2.

4) х₂₃=15 Вычеркиваем столбец 3.

5) х₂₄=5 Вычеркиваем строку 2.

6) х₃₄=5.

Этому решению соответствует :

Этап 2. Будем использовать Метод потенциалов.

В этом методе строке i и столбцу j ставятся в соответствие числа U_i и V_j, называемые потенциалом. Для каждой базисной переменной х_ij потенциалы должны удовлетворять уравнению:

Эти уравнения составляют систему из m+n-1 уравнений, неизвестных – m+n.

Придавая одному из потенциалов (обычно U₁) значение «0», получаем систему и решая, находим остальные потенциалы.

Для небазисных определим следующие величины:

- небазисные

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

В данном случае, это - включаемая.

Этап 3. Построим цикл, соответствующий вводимой переменной х₃₁. Цикл начинается и заканчивается вводимой переменной. Он состоит из горизонтальных и вертикальных, связанных друг с другом, отрезков, концами которых должны быть базисные переменные. Это означает, что каждая ячейка, стоящая на изломе цикла, должна содержать базисную переменную, причем направление обхода цикла несущественно.

Если значение х₃₁ увеличивается на единицу, для сохранения допустимости решения значения базисных переменных, стоящих на изломах цикла, необходимо скорректировать так:

1. уменьшить х₁₁ на 1.

2. увеличить х₁₂ на 1.

3. уменьшить х₂₂ на 1.

4. увеличить х₂₄ на 1.

5. уменьшить х₃₄ на 1.

Исключаемая из базиса переменная выбирается из переменных, находящихся на изломах цикла, значение которых уменьшается при увеличении х₃₁ и которая имеет наименьшее значение.

выбираем исключаемую из базиса (произвольно)

Пусть будет х₃₄. Т.е. х₃₄ приравнивается нулю, (приписано).

Остальные – по таблице скорректируем.

10 0 20 11 20 0 12 7 9 16 14 0 х11	15 х12	х13	х14	15
0 х21	х22	15 х23	10 х24	25
18 5 х31	х32	х33	0 х34	5
5	15	15	10

Получили новое базисное решение ,,,,,, а стоимость перевозки

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

,

,

,

,

Посчитаем .

Наибольшее положительное  х₂₁ – включаемая.

Строим цикл  х₁₁, х₂₂ – выбираем, х₁₁ – исключаем. х₁₁=0  остальные значения не меняются.

Получили новое базисное решение:

, ,,,,,

а стоимость плана -

Требуется еще одна итерация.

х₁₄ – вводимая в базис. Построим цикл  исключаемая х₂₄.

Получили оптимальное решение.

, ,,,,,

и при этом стоимость плана – $315.

Замечания.

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

2. Метод наименьшей стоимости. Метод северо-западного угла не всегда дает «хороший» начальный план. Из методов нахождения начального плана выделим метод наименьшей стоимости. Алгоритм этого метода: выбирается переменная, которой соответствует наименьшая стоимость во всей таблице стоимостей, и ей придается возможно большее значение, допустимое ограничениями на спрос и объем производства (если их несколько, то выбор осуществляется произвольно). Далее, вычеркивается соответствующий столбец или строка. Если ограничения по столбцу и строке выполняются одновременно, то вычеркивается либо строка, либо столбец. После вычисления новых значений спроса и объема производства для всех невычеркнутых строк и столбцов процесс повторяется при возможно большем значении той переменной, которой соответствует минимальная стоимость среди невычеркнутых. Процедура завершается, когда остается одна строка или один столбец.

Рассмотрим тот же пример, и найдем начальное решение методом минимальной стоимости.

10 0 20 11 20 0 12 7 9 16 18 14 0 х11	15 х12	х13	0 х14	15
х21	х22	15 х23	10 х24	25
5 х31	х32	х33	х34	5
5	15	15	10

Данное решение найдено так:

1) х₁₂=15 , вычеркиваем столбец 2.

2) х₃₁=5 , вычеркиваем строку 3.

3) х₂₃=15 , вычеркиваем столбец 3.

4) х₁₁=0 , вычеркиваем столбец 1.

5) х₁₄=0 , вычеркиваем строку 1.

6) х₂₄=10.

Этому решению соответствует  = $335.

3. Распределительный метод. Это один из методов отыскания оптимального решения после нахождения начального плана. Он состоит в непосредственном отыскании свободных клеток (соответсвующие небазисным переменным) в таблице стоимостей с отрицательной ценой цикла и в перенесении перевозок по этому циклу. Ценой цикла назовем алгебраическую сумму стоимостей, стоящих в вершинах цикла, причем стоимости, стоящие в вершинах со знаком «+» берутся со знаком «+», а стоимости, стоящие в вершинах со знаком «-» берутся со знаком «-». Сначала выбирается небазисная переменная с наименьшей стоимостью для включения в новый базис и строится цикл. Аналогично тому, как это делалось раньше, выбирается исключаемая из базиса переменная. Процедура продолжается, пока не получится цикл с неотрицательной ценой. Если циклов с отрицательной ценой больше не осталось, то дальнейшее улучшение плана невозможно, т.е. оптимальный план получен. Продемонстрируем этот метод на том же примере.

Предположим, что начальный план найден методом северо-западного угла.

10 20 12 7 9 5 х11	10 х12	х13	х14	15
х21	5 х22	15 х23	5 х24	25
0 16 18 14 х31	х32	х33	5 х34	5
5	15	15	10

Начальный план: х₁₁=5, х₁₂=10, х₂₂=5, х₂₃=15, х₂₄=5, х₃₄=5.

Этому решению соответствует :

Возьмем свободную клетку, стоимость перевозки в которой минимальна, т.е. клетку с . х₃₁ Эта переменная и будет включаемой в новый базис. Строим цикл, определим цену цикла : z = 0-18+20-7+0-10 = -15. Придаем . . х₃₁ = 5 и из базиса исключим . х_34. Получили новое базисное решение: х₁₁=0, х₁₂=15, х₂₂=0, х₂₃=15, х₂₄=10, х₃₁=5, а стоимость перевозки .

Возьмем в качестве включаемой переменную с минимальной стоимостью перевозки - х₁₄ и строим цикл.

10 20 12 7 9 0 х11	15 х12	х13	х14	15
х21	0 х22	15 х23	10 х24	25
0 16 18 14 5 х31	х32	х33	х34	5
5	15	15	10

Цена цикла: z = 11-20+7-0 = -2. В качестве исключаемой выбираем переменную х₂₄. Получили новое базисное решение: х₁₁=0, х₁₂=5, х₂₂=10, х₂₃=15, х₁₄=10, х₃₁=5, а стоимость перевозки .

Продолжаем процедуру. В качестве включаемой выбираем переменную х₂₁ , строим цикл. Цена цикла z = 12-7+0-10=-5.

10 20 12 7 9 0 х11	5 х12	х13	10 х14	15
х21	10 х22	15 х23	х24	25
0 16 18 14 5 х31	х32	х33	х34	5
5	15	15	10

Получили новое базисное решение: х₂₁=0, х₁₂=5, х₂₂=10, х₂₃=15, х₁₄=10, х₃₁=5, а стоимость перевозки .

В качестве включаемой выбираем х₁₁ , и строим цикл. Цена цикла положительная z = 10-0+7-12 = 5. Это означает, что дальнейшее улучшение плана невозможно. Можно проверить ( проверьте самостоятельно), что любой другой цикл будет иметь положительную цену. Таким образом, получен оптимальный план, кстати совпадающий оптимальным планом, найденным методом потенциалов.

10 20 12 7 9 х11	5 х12	х13	10 х14	15
0 х21	10 х22	15 х23	х24	25
0 16 18 14 5 х31	х32	х33	х34	5
5	15	15	10