Математическая постановка транспортной задачи

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А₁,А₂,…,Аt в п пунктов назначения В₁,В₂,..,Вn. При этом в качестве критерия оптимальности обычно берется минимальная стоимость перевозок всего груза.

Примем, что множество I, включающее m пунктов отправления груза, множество J, включающее n пунктов потребления, в каждом из которых имеется спрос на данный груз.

Обозначим через с_ij тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения, через a_i -запасы груза в j -м пункте отправления, через b_j -потребности в грузе в j-м пункте назначения, а через x_ij -количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения.

Найти: План перевозок X = (x_ij), согласно которому груз из пунктов отправления перевозится в пункты потребления с минимальными издержками, а спрос удовлетворяется полностью

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

, → min (1)

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

удовлетворения спроса (2)

условие полного вывоза (3)

условие неотрицательности (4)

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

Определение 1. Всякое неотрицательное решение системы линейных уравнений (2) и (3), определяемое матрицей Х=() (i=1,…m;j=1,…n), называется планом транспортной задачи.

Определение2. План =() (i=1,…m;j=1,…n), при котором функция (1) принимает своё минимальное значение, называется оптимальным планом транспортной задачи.

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

Таблица 1

Пункты отправления	Пункты назначения	Запасы
	…		…
…	…	…	…	…	…	…
…	…	…	…	…	…	…
Потребности		…		…

Очевидно, общее наличие груза у поставщиков равно:

,

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

единиц продукции.

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

= , [5]

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

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

В случае превышения запаса над потребностью

> ,

вводится фиктивный (n+1)-й пункт назначения с потребностью

= -

и соответствующие тарифы считаются равными нулю: =0 (i=1,…m). Полученная таким образом задача является транспортной задачей, для которой выполняется равенство (5).

Аналогично, при

< ,

вводится фиктивный (m+1)-й пункт отправления с запасом груза

= -

и тарифы пологаются равными нулю: =0 (j=1,…m). Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

Число переменных в транспортной задаче с m пунктами отправления и пунктами назначения равно m n, а число уравнений в системах (2) и (3) равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше-то вырожденным.

Для определения опорного плана существует несколько методов. (Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом).

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

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

Классическая транспортная задача линейного программирования является сбалансированной или закрытой, т.е. формулируется в форме, когда имеет место равенство общего объема производства рассматриваемого продукта общему объему его потребления. Этому условию соответствует отдельное ограничение (2.5). В противном случае, если равенство (2.5) не имеет места, то транспортная задача называется несбалансированной или открытой.

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

В то же время классическая транспортная задача может быть дополнена условиями на ограничение сверху возможных значений некоторых или всех переменных: где hij -пропускная способность транспорта между i-м пунктом производства и j-м пунктом потребления. Как нетрудно заметить, подобная модификация приведет к включению в модель дополнительных ограничений. Однако эти дополнительные ограничения не оказывают существенного влияния на процесс их решения с помощью программы Ms Excel. для определения оптимального опорного плана используют средство Поиск решений, реализованного в Excel.

3. Решения транспортной задачи с помощью программы Ms Excel

Для решения классической транспортной задачи с помощью программы Ms Excel необходимо задать конкретные значения параметрам исходной задачи. Для определения рассмотрим задачу оптимального планирования перевозок бензина некоторой марки между нефтеперерабатывающими заводами (НПЗ) и автозаправочными станциями (АЗС). В этом случае в качестве транспортируемого продукта рассматривается бензин, в качестве пунктов производства- 3 нефтеперерабатывавающих завода (т=3), а в качестве пунктов потребления- 4 автозаправочные станции (п=4).

Объемы производства бензина следующие: НПЗ №1- 10 т, НПЗ №2- 14 т, НПЗ №3- 17 т. Объемы потребления бензина следующие: АЗС №1-15 п, АЗС №2- 12 п, АЗС №3-8,5 т, АЗС №4-5,5 т. Стоимость транспортировки одной тонны бензина между НПЗ и АЗС заданна в форме следующей таблицы:

Таблица.1. Стоимость транспортировки бензина

Между НПЗ и АЗС (в тысяч грн.)

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

3х11+5х12+7х13+11х14+х21+4х22+6х23+3х24+ (2.6)

+5х31+8х32+12х33+7х34→

где множество допустимых альтернатив формируется следующей системой ограничений типа равенств:

(2.7)

Заметим, что первые 3 ограничения данной задачи соответствуют общему ограничению (2.2), следующие 4 ограничения- общему ограничению (2.3), а последнее ограничение- общему ограничению (2.5).

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

Для решения сформулированной индивидуальной транспортной задачи с помощью программы MS Excel создадим в книге Линейное программирование новый лист и изменим его имя на Транспортная задача. Для решения задачи выполним следующие подготовительные действия:

1.Внесем необходимые надписи в ячейки A5:A10, B1, F1. B5:G5, как это изображено на рисунке 2.1. Следует отметить, что конкретное содержание этих надписей не оказывает никакого влияния на решения рассматриваемой транспортной задачи.

1. В ячейки В2:Е4 введем значение коэффициентов целевой функции (таблица 2.1).

2. В ячейки F2, введем формулу: =суммпроизв(В2:Е2; В6:Е8), которая представляет целевую функцию (2.6).

3. В ячейки G6:G8 и B10:E10 введем значения, соответствующие правым частям ограничений (2.7).

4. В ячейку F6 введем формулу: =сумм (В6:Е6), которая представляет первое ограничение (2.7).

5. Скопируем формулу, введенную в ячейку F6, в ячейки F7 и F8.

6. В ячейку В9 введем формулу: =сумм (В6:В8), которая представляет четвертое ограничение (2.7).

7. Скопируем формулу, введенную в ячейку В9, в ячейки C9, D9 и E9.

Внешний вид рабочего листа MS Office Excel с исходными данными для решения транспортной задачи показан на рисунке 2.1.

Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню: Сервис│Поиск решения…

После появления диалогового окна Поиск решения следует выполнить следующие действия:

1.В поле с именем Установить целевую ячейку: ввести абсолютный

адрес ячейки $F$2.

2.Для группы Равной: выбрать вариант поиска решения- минимальному значению.

Рисунок. 2.1 Исходные данные для решения

транспортной задач

3. В поле с именем Изменяя ячейки: ввести абсолютный адрес диапазона ячеек $B$2:$E$4.

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

· для задания первого ограничения в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

· в появившемся дополнительном окне выбрать ячейку $F$6, которая

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

· в качестве знака ограничений из выпадающего списка выбрать строгое неравенство “=”;

· в качестве значения правой части ограничения выбрать ячейку $С$6;

· для добавления первого ограничения в дополнительном окне нажать кнопку с надписью Добавить;

· аналогичным образом задать оставшиеся 6 ограничений.

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

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

Рисунок 2.2. Параметры мастера поиска решения и базовых

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

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

Рисунок 2.3 Результат количественного

решения транспортной задачи

Результатом решения транспортной задачи являются найденные оптимальные значения переменных: х11=0, х12=1,5, х13=8,5, х14=0, х21=14, х22=0, х23=0, х24=0, х31=1, х32=10,5, х33=0, х34=5,5, которым соответствует значение целевой функции: f opt = 208,5. При выполнении расчетов для ячеек В6:Е8 был выбран числовой формат с тремя знаками после запятой.

Анализ найденного решения показывает, что для удовлетворения потребностей АЗС №1 следует транспортировать 14т бензина из НПЗ №2 и 1т- из НПЗ №3, для удовлетворения потребностей АЗС №2 следует транспортировать 1,5 т бензина из НПЗ №1 и 10,5т – из НПЗ №3, для удовлетворения потребностей АЗС №3 следует транспортировать 8,5 т бензина из НПЗ №1 и, наконец, для удовлетворения потребностей АЗС №4 следует транспортировать 5,5 т бензина из НПЗ №3. При этом общая стоимость найденного плана перевозок составит 208,5 тысяч грн..

Рисунок 2.4 Отчет по результатам поиска решения

4 Рекомендации по решению задач оптимизации с

помощью надстройки Поиск решения.