Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения

Математическая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А 1 , А 2 , …, А т в п пунктов назначения В 1 , В 2 , …, В п . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза.

Обозначим:

c ij – тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения,

a i – запасы груза в i -м пункте отправления,

b j – потребности в грузе в j– м пункте назначения,

x ij – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения.

Тогда математическая постановка задачи состоит в определении минимального значения функции: (6.1)

при условиях
(6.2)

(6.3)

Всякое неотрицательное решение систем линейных уравнений (6.2) и (6.3), определяемое матрицей Х=(х ij ) , называется планом транспортной задачи.

План Х*=(х* ij ) , при котором функция (6.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы.

Для определения опорного плана существует несколько методов: метод северо-западного угла, метод наименьшей стоимости, метод аппроксимации Фогеля и др.

Метод северо-западного угла

В самую северо-западную клетку таблицы заносится максимально допустимая перевозка, при этом либо вывозится весь груз со станции А 1 и все остальные клетки первой строки вычеркиваются, либо потребности первого потребителя В 1 полностью удовлетворяются, тогда все клетки первого столбца вычеркиваются. После этого самой северо-западной клеткой становится клетка А 1 В 2 или В 2 А 1 . Алгоритм продолжается до заполнения таблицы. Недостатки – не учитывается стоимость перевозки, и получается план далекий от оптимального.

Метод наименьшей стоимости

Метод в какой-то степени учитывает затраты на перевозки и строится следующим образом: рассматривается матрица и находится клетка с наименьшей стоимостью, которая заполняется максимально допустимой перевозкой. В большинстве случаев этот метод дает план близкий к оптимальному.

Метод аппроксимации Фогеля

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

Широкораспространенным методом решения транспортных задач является метод потенциалов.

Данный метод позволяет оценить начальное опорное решение и методом последовательного улучшения найти оптимальное решение.

Теорема 1. Если опорный план Х=(х ij ) является оптимальным, существует система из (т+п) чисел, называемых потенциалами, U i , V j , такая, что:

U i + V j =С ij ,для х ij >0 (базисные переменные);

U i + V j =С ij ,для х ij =0 (свободные переменные).

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

для каждой занятой клетки сумма потенциалов равна стоимости перевозки единицы груза, стоящей в этой клетке:

U i + V j =С ij

для каждой свободной клетки сумма потенциалов меньше или равна стоимости перевозки единицы груза, стоящей в этой клетке:

U i + V j £ С ij

Теорема 2. Любая закрытая транспортная задача имеет решение, которое достигается за конечное число шагов метода потенциалов.

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

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

ломаная должна быть связной, т.е. из любой ее вершины можно попасть в другую вершину, двигаясь по ребрам;

в каждой вершине цикла сходятся ровно два ребра – одно по строке, другое по столбцу.

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

Приведем примеры некоторых циклов.

Теорема 3. В таблице перевозок для каждой свободной клетки существует один цикл пересчета.

Алгоритм метода потенциалов

Поставим в соответствие каждой станции А i потенциал и i , а каждой станции В j потенциал v j . Для этого для каждой заполненной клетки х ij ≠0 составим уравнение и i + v j =с ij . Придадим и 1 =1 (можно любое другое значение) и найдем все остальные потенциалы.

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

3. Цикл пересчета начинается в свободной клетке, где ставим знак плюс, а остальные клетки заняты. Знаки в этих клетках чередуются. Выберем наименьшую из перевозок, стоящих в клетках со знаком минус. Тогда данную перевозку прибавляем к перевозкам со знаком плюс и вычитаем из перевозок со знаком минус. Получим новое оптимальное решение. Проверим его на оптимальность.

4. Для новых потенциалов проверяем условие оптимальности. Если условия оптимальности выполняются, то получено оптимальное решение, если нет, то продолжаем поиск оптимального решения по методу потенциалов.

Пример 7.1. Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей
.

Составить такой план перевозок, при котором общая себестоимость перевозок является минимальной.

Решение:

задача закрытого типа.

Составим первый план транспортной задачи методом северо-западного угла. Заполнение клеток таблицы начнем с левой верхней клетки.

S 1 =120·7+40·8+10·5+130·9+60·3+110·6=3120

Составим первый план методом минимальной стоимости. Будем заполнять клетки с минимальными тарифами.

S 2 =160·1+120·4+20·8+50·2+30·3+90·6=1530

Стоимость при таком плане перевозок почти в два раза меньше. Начнем решение задачи с этого плана. Проверим его на оптимальность. Введем потенциалы α i – соответственно отправления, β j – соответственно назначения. По занятым клеткам составляем систему уравнений α i + β j =c ij:

Для свободных клеток таблицы проверяем критерий оптимальности

Будем составлять разности

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

S 3 =70·1+90·2+120·4+20·8+50·2+120·3=1350

Стоимость перевозок меньше, т.е. план улучшили. Проверяем теперь новый план на оптимальность. По занятым клеткам:

По свободным клеткам:

План не оптимальный т. к. имеется положительная оценка
Строим цикл пересчета и переходим к новому плану.

S 4 =50·1+110·2+120·4+20·5+30·2+140·3=1330

Проверяем новый план на оптимальность.

По занятым клеткам:

По свободным клеткам:

Критерий оптимальности выполнен, т. е. последний план оптимальный.

Ответ:

План перевозок

является оптимальным планом тогда и только тогда, когда найдется система платежей

для которой выполняются условия:

Доказательство. Сформулируем вторую теорему двойственности в терминах переменных транспортной задачи.

удовлетворяют ограничениям прямой задачи, а

удовлетворяют ограничениям двойственной задачи, то для оптимальности плана

необходимо и достаточно выполнение условий

Условие а) выполняется для любых допустимых решений прямой задачи, так как

Условие b) можно расписать как следствие о дополняющей нежесткости, а именно

Итак, для базисных переменных

имеем равенство

а для небазисных переменных

достаточно выполнения допустимости двойственных переменных

Таким образом имеем условия 1) и 2) критерия.

Критерий доказан.

9.5 Построение опорного плана транспортной задачи

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:

Базисными клетками транспортной таблицы являются клетки с от-

личными от нуля положительными перевозками, остальные клетки - свободные. Базисные клетки образуют опорный план транспортной задачи, если выполняются два условия:

1) сумма перевозок в каждой строке равна запасу в данной

2) сумма перевозок в каждом столбце равна соответствующему

столбцу спросу

Опорный план транспортной задачи содержит не более n+m-1

отличных от нуля перевозок

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

меньше и n+m-1, опорный план - невырожден , если число

ненулевых перевозок равно n+m-1.

Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях.

Метод севево-западного угла

Рассмотрим "северо-западный угол" незаполненной таблицы, то

есть клетку, соответствующую первому поставщику и первому потребителю.

Возможны три случая.

Это означает, что первый поставщик отгрузил весь произведенный продукт первому потребителю и его

запас равен нулю, поэтому

При этом неудовлетворенный спрос в первом пункте потребления равен

то есть спрос первого потребителя полностью удовлетворен и поэтому

а остаток продукта в первом пункте производства равен

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

поэтому условно считается, что выбывает только поставщик,

а спрос потребителя остается неудовлетворенным и равным нулю.

После этого рассматриваем северо-западный угол оставшейся не-

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

через n+m-1 шагов получим опорный план.

10. Математическая модель транспортной задачи. Открытые и закрытые задачи. Допустимый, опорный и оптимальный планы перевозок.

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ: открытая ТЗ и закрытая ТЗ.

Транспортная задача называется закрытой, если выполняется условие баланса : суммарный объем производства равен суммарному объему потребления:

Следнет обратить внимание на то, что математическая модель задает закрытую транспортную задачу.

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный объем производства меньше суммарного объема потребления:

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

, (3.3)

при этом полагают .

Второй случай. Суммарный объем производства больше суммарного объема потребления:

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

, (3.5)

при этом полагают .

Методы решения.

· Как задача линейного программирования ТЗ может быть решена симплекс методом .

· Также разработаны специальные (более эффективные) методы решения транспортной задачи: обобщенный венгерский метод ; метод северо-западного угла, метод минимального элемента для нахождения опорного плана; метод потенциалов для нахождения оптимального плана .

11. Построение начального (опорного) плана перевозок по методу северо–западного угла и по методу наименьшей стоимости.

1.Метод северо-западного угла. При нахождении опорного плана на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного («северо-западный угол») и заканчивается клеткой для неизвестного, т.е. как бы по диагонали таблицы.

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

Транспортная задача

Постановка транспортной задачи

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее часто называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным.

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

Выбор критерия оптимальности

При решении транспортной задачи выбор критерия оптимальности имеет важное значение. Как известно, оценка экономической эффективности примерного плана может определятся по тому или иному критерию, положенного в основу расчета плана. Этот критерий является экономическим показателем, характеризующим качество плана. До настоящего времени нет общепринятого единого критерия всесторонне учитывающего экономические факторы. При решении транспортной задачи, в качестве критерия оптимальности в различных случаях используют следующие показатели:

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

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

3) Эксплутационные расходы на транспортировку грузов (критерий - себестоимость эксплутационных расходов). Более верно отражает экономичность перевозок различными видами транспорта. Позволяет делать обоснованные выводы о целесообразности переключения с одного вида транспорта на другой.

4) Сроки доставки грузов (критерий - затраты времени).

5) Приведенные затраты (с учетом эксплуатационных расходов, зависящих от размеров движения и капиталовложения в подвижной состав).

6) Приведенные затраты (с учетом полных эксплуатационных расходов капиталовложений на строительство объектов в подвижной состав).

где - эксплутационные издержки,

Расчетный коэффициент эффективности капиталовложения,

Капитальные вложения, приходящие на 1 т груза на протяжении участка,

Т - время следования,

Ц - цена одной тоны груза.

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j–м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

при условиях

(2)

(3)

(4)

Поскольку переменные удовлетворяют системам линейных уравнений (2) и (3) и условию неотрицательности (4), то обеспечиваются вывоз имеющегося груза из всех пунктов отправления, доставка необходимого количества груза в каждый из пунктов назначения, а также исключаются обратные перевозки.

Таким образом, Т-задача представляет собой задачу ЛП с m*n числом переменных, и m + n числом ограничений - равенств.

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

то модель такой транспортной задачи называется закрытой или сбалансированной .

Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми . Возможные два случая:

В первом случае полное удовлетворение спроса невозможно .

Такую задачу можно привести к обычной транспортной задаче следующим образом. В случае превышения потребности над запасом, т. е. вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю:

Тогда требуется минимизировать

при условиях

Рассмотрим теперь второй случай .

Аналогично, при вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю:

Тогда соответствующая Т-задача запишется так:

Минимизировать

при условиях:

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

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

В некоторых случаях нужно задать, что по каким-либо маршрутам нельзя перевозить продукцию. Тогда стоимости перевозок по этим маршрутам задаются так, чтобы они превышали самые высокие стоимости возможных перевозок (для того, чтобы было невыгодно везти по недоступным маршрутам) – при решении задачи на минимум. На максимум – наоборот.

Иногда нужно учесть, что между какими-то пунктами отправки и какими-то пунктами потребления заключены договора на фиксированные объемы поставки, то надо исключить объем гарантированной поставки из дальнейшего рассмотрения. Для этого объем гарантированной поставки вычитается из следующих величин:

· из запаса соответствующего пункта отправки;

· из потребности соответствующего пункта назначения.

Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(6)

При данном плане перевозок общая стоимость перевозок составит

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

4) Сроки доставки грузов (критерий - затраты времени).

где - эксплутационные издержки,

Расчетный коэффициент эффективности капиталовложения,

Капитальные вложения, приходящие на 1 т груза на протяжении участка,

Т - время следования,

Ц - цена одной тоны груза.

при условиях

то модель такой транспортной задачи называется закрытой или сбалансированной .

В первом случае полное удовлетворение спроса невозможно .

Тогда требуется минимизировать

при условиях

Рассмотрим теперь второй случай .

Тогда соответствующая Т-задача запишется так:

Минимизировать

при условиях:

· из запаса соответствующего пункта отправки;

· из потребности соответствующего пункта назначения.

Конец работы -

Эта тема принадлежит разделу:

Транспортная задача

Пример.. четыре предприятия данного экономического района для производства продукции..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (поставщики) A 1 , A 2 , . . ., A m в n пунктов потребления (потребители) B 1 , B 2 , . . . B n так, чтобы:

Вывезти все грузы от поставщиков;

Удовлетворить спрос каждого потребителя;

Обеспечить минимальные суммарные транспортные расходы на перевозку всех грузов.

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой используется минимальная стоимость перевозки всего груза .

Обозначим:

a i - наличие груза в i -ом пункте отправления ;

b j - величина потребности в этом грузе в j -ом пункте назначения ;

с ij - стоимость перевозки единицы груза из i -ого пункта отправления в j -ый пункт потребления (тариф перевозки);

x ij - количество груза, перевозимого из i -ого пункта отправления в j -ый пункт назначения, назначения, x ij ≥ 0.

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

Запишем математическую модель транспортной задачи.

Требуется определить матрицу ) , которая удовлетворяет следующим условиям:

,
(5.1)

,
(5.2)

,
,
(5.3)

и доставляет минимальное значение целевой функции

L () =
(5.4)

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

Определение 1. Всякое неотрицательное решение систем линейных уравнений (5.1) и (5.2), определенное матрицей ) называется допустимым планом транспортной задачи .

Определение 2. План ) при котором функция (5.4) принимает максимальное значение, называется оптимальным планом транспортной задачи.

Теорема 1. Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений (5.1) и (5.2) транспортной задачи, на единицу меньше числа уравнений, т.е. равен (m + n – 1).

Следовательно, число линейно независимых уравнений равно (m + n – 1), они образуют базис, а соответствующие им переменные будут являться базисными.

Определение 3 . Допустимый план транспортной задачи, имеющий не более (m + n – 1) отличных от нуля величин , называется базисным или опорным.

Определение 4. Если в опорном плане число отличных от нуля значений переменных в точности равно (m + n – 1), то план является невырожденным, а если меньше – вырожденным.

Теорема 2. Для разрешимости транспортной задачи необходимо и достаточно, что суммарные запасы груза в пунктах отправления были равны суммарным потребностям в пунктах назначения, т.е.

Определение 5. Модель транспортной задачи, удовлетворяющая условию (5.5), называется закрытой. Если указанное условие не выполняется, то модель является открытой.

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

В случае превышения запаса над потребностью, т.е. > , вводится фиктивный (n+ 1) –ый пункт назначения с потребностью b n +1 = − , а соответствующие тарифы считаются равными нулю: С i , n + 1 = 0

Если < , то вводится фиктивный (m + 1) –ый пункт отправления с потребностью a m +1 = − и тарифами С m + 1, j = 0

Рассмотрим один из методов построения первого опорного плана транспортной задачи – метод минимальной стоимости или наилучшего элемента матрицы удельных затрат.

Определение 6. Наилучшим элементом матрицы удельных затрат (тарифов) будем называть наименьший тариф, если задача поставлена на минимум целевой функции, наибольший тариф – если задача поставлена на максимум.

Алгоритм построения первого опорного плана.

1. Среди матрицы удельных затрат находим наилучший тариф.

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

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

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

Дальнейшее улучшение первого опорного плана транспортной задачи и получение оптимального плана производим методом потенциалов.

Теорема 3 . План ) транспортной задачи является оптимальным, если существует система (m + n) чисел u i и v j (называемых потенциалами), удовлетворяющая условиям:

(5.6)

(5.7)

Потенциалы u i и v j являются переменными двойственной задачи, составленной к исходной транспортной задаче, и обозначают оценку единицы груза в пунктах отправления и назначения соответственно.

Обозначим: ) оценка свободной (незанятой) клетки таблицы.

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

Алгоритм метода потенциалов

1. Построение первого опорного плана транспортной задачи методом минимальной стоимости.

2. Проверка вырожденности плана .

Потенциалы могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане (число базисных переменных) меньше, чем (m+n−1), то вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n−1). Нуль вводят в клетку с наилучшим тарифом, которая принадлежит строке или столбцу. Одновременно вычеркиваемых при составлении первого опорного плана. При этом фиктивно занятая нулем клетка таблицы не должна образовывать замкнутого прямоугольного контура с другими занятыми клетками таблицы.

3. Расчет значения функции цели (5.4) путем суммирования произведений тарифов (удельных затрат) на объемы перевозимого груза по всем занятым клеткам таблицы.

4. Проверка оптимальности плана.

Определяем потенциалы . Для каждой занятой клетки записываем уравнение , в результате получаем систему (m + n−1) уравнений с (m + n) переменными.

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

Для каждой свободной клетки определяем оценки .

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

5. Построение нового опорного плана.

Из всех положительных оценок свободных клеток выбираем наибольшую (задача поставлена на минимум); из всех отрицательных – наибольшую по абсолютной величине (задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т.е. направить в нее груз. Заполняя выбранную клетку, необходимо изменить объем поставок, записанных в ряде других занятых клеток и связанных с заполняемой так называемым циклом.

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

Вершинам цикла, начиная от вершины, находящейся в выбранной клетке на загрузку, присваиваем поочередно знаки «+» и «−» . будем назвать эти клетки плюсовыми и минусовыми.

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

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

Замечания

1. Если в минусовых клетках построенного цикла находятся два или несколько одинаковых минимальных значений , то при перераспределении объемов груза освобождается не одна, а две или несколько клеток. В этом случае план становится вырожденным. Для продолжения решения необходимо одну или несколько одновременно освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клеткам с наилучшим тарифом. Нулей вводят столько, чтобы во вновь полученном опорном плане число занятых клеток (базисных переменных) было ровно (m + n−1).

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

3. Значение целевой функции на каждой итерации можно рассчитать следующим образом:

(задача поставлена на минимум),

(задача поставлена на максимум),

где - величина перемещаемого по контуру объема груза;

Оценка свободной клетки, в которую направляется груз при переходе к новому опорному плану;

− значение функции цели на k-ой итерации;

− значение функции цели на предыдущей итерации.

Пример

На трех складах оптовой базы имеется однородный груз в количествах 40, 80 и 80 единиц. Этот груз необходимо перевезти в четыре магазина, каждый из которых должен получить соответственно 70, 20, 60 и 60 единиц. Стоимости доставки единицы груза (тарифы) из каждого склада ) во все магазины ) заданы матрицей .

Составить план перевозок однородного груза с минимальными транспортными затратами (числа условные).

Решение.

1. Проверим необходимое и достаточное условие разрешимости задачи:

40+80+80 = 200,

70+20+60+60 = 210.

Как видно, суммарная потребность груза превышает его запасы на складах оптовой базы. Следовательно, модель транспортной задачи является открытой и в исходном виде решения не имеет. Для получения закрытой модели введем дополнительный (фиктивный) склад А 4 с запасом груза, равным а 4 = 210 – 200 = 10 ед. тарифы перевозки единицы груза из склада А 4 во все магазины полагаем равными нулю.

Все исходные данные заносим в таблицу 7.

Запасы

В 1

В 2

В 3

В 4

A 1

A 2

A 3

A 4

Потребности

2. Построение первого опорного плана методом минимальной стоимости.

Среди тарифов минимальным или наилучшим является С 14 =1. В клетку А 1 В 4 направляем максимально возможный груз, равный min{60,40} = 40. Тогда x 14 = 40. Из склада А 1 весь груз вывезен, но потребность четвертого магазина неудовлетворенна на 20 ед. строка А 1 выходит из рассмотрения.

Среди оставшихся тарифов минимальный элемент - С 23 = 2. В клетку А 2 В 3 направляем груз min{60,80} = 60. При этом столбец В 3 выходит из рассмотрения, а из склада А 2 не вывезено 20 ед.

Из оставшихся элементов минимальный С 22 = 3. В клетку А 2 В 2 направляем груз в количестве min{20,20} = 20. При этом столбец одновременно вычеркиваются строка А 2 и столбец В 2 .

Выбираем минимальный элемент С 31 = 4. В клетку А 3 В 1 направляем груз, равный min{70,80} = 70. При этом столбец В 1 выходит из рассмотрения, а из склада А 3 не вывезено 10 ед. Оставшийся груз с третьего склада направляем в летку А 3 В 4 , x 34 = 10. Потребность четвертого магазина не удовлетворена на 10 ед. направим от фиктивного поставщика – склад А 4 10 ед. груза в клетку А 4 В 4 , x 44 = 10.

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

3. Проверка вырожденности плана

Число занятых клеток или базисных переменных в первом опорном плане равно шести. план транспортной задачи является вырожденным, так как число базисных переменных в невырожденном плане равно m + n – 1 = 4 + 4 – 1 = 7. Для продолжения решения задачи опорный план необходимо дополнить введением фиктивной перевозки, т.е. занять нулем одну из свободных клеток.

При построении первого опорного плана одновременно были вычеркнуты строка А 2 и столбец В 2 , поэтому произошло вырождение плана. На право фиктивной перевозки претендуют свободные клетки строки А 2 и столбца В 2 , которые имеют минимальный тариф и не образуют с занятыми клетками замкнутого прямоугольного контура. Такими клетками являются А 2 В 4 и А 3 В 2 . Нуль направляем в клетку А 2 В 4 .

4. Расчет значения целевой функции

Значение целевой функции первого опорного плана определяем путем суммирования произведений тарифов на объемы перевозимого груза по всем занятым клеткам таблицы.

L(Х 1) = 4∙70 + 3∙20 + 2∙60 + 1∙40 + 3∙0 + 6∙10 + 0∙10 = 560 (тыс.руб.).

5. Проверка условия оптимальности

Рассчитаем потенциалы по занятым клеткам таблицы из условия: ( Так как число неизвестных потенциалов больше числа уравнений (m + n > m + n – 1), то один из потенциалов принимаем равным нулю. Пусть . Тогда для занятых клеток можем записать систему уравнений:

Полагая , получим , , , ,

Рассчитанные потенциалы заносим в таблицу 7. Подсчитаем оценки свободных клеток.

Первый опорный план не является оптимальным, так как имеются положительные оценки свободных клеток и . Выбираем максимальную положительную оценку свободной клетки - .

6. Построение нового опорного плана

Для клетки А 3 В 2 построим прямоугольный замкнутый контур 0таблица 7) и проведем перераспределение груза контуру. Вершинам контура, начиная от вершины, находящейся в свободной клетке А 3 В 2 ,присваиваем поочередно знаки «+» и «−» .

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее, т.е. θ = min(20,10) = 10. Прибавляем значение θ = 10 к объемам груза, стоящих в плюсовых клетках, вычитаем из объемов груза, стоящих в минусовых клетках замкнутого контура. В результате получим новый опорный план, приведенный в таблице 8.

Запасы

В 1

В 2

В 3

В 4

A 1

A 2

A 3

3 10

A 4

Потребности

Второй опорный план транспортной задачи невырожденный, так как число занятых клеток равно 7.

L(X 2) = L(X 1) – θ∙ = 560 – 10∙3 = 530 (тыс.руб.).

Этот план проверяем на оптимальность. Снова находим потенциалы поставщиков и потребителей. Для этого составляем по занятым клеткам следующую систему уравнений.