Решение транспортной задачи линейного программирования в среде MS Excel (стр. 4 из 9)

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. Следует отметить, что конкретное содержание этих надписей не оказывает никакого влияния на решения рассматриваемой транспортной задачи.

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

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

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

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

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

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

8. Скопируем формулу, введенную в ячейку В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 Отчет по результатам поиска решения

2.3 Решение транспортной задачи с помощью методов

потенциалов

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

Для того чтобы исходная закрытая транспортная задача линейного программирования (2.1) - (2.5) имела оптимальное решение, необходимо и достаточно существование таких неотрицательных чисел {v1,v2,v3,…,vn, u1,u2,…,um}, которые обеспечивают выполнение двух групп условий:

, (2.8)

и если некоторое

>0 то ui+uj=cij. (2.9)

Соответствующие данным условиям числа {v1,v2,…,vn, u1,u2,…,um} получили название потенциалов. Очевидно, данные условия могут служить признаком окончания поиска решения транспортной задачи.

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

1. Если исходная транспортная задача линейного программирования является открытой, то она преобразуется к замкнутому виду (2.1)- (2.5). С этой целью могут быть введены дополнительные переменные {xm+1,j}

для фиктивного пункта производства am+1, если выполняется неравенство: или дополнительные переменные для фиктивного пункта потребления bn+1, если выполняется неравенство:

При этом дополнительным переменным должны соответствовать нулевые коэффициенты целевой функции: cm+1,1=cm+1,2=…=cm+1,n=0 или c1,n+1=c2,n+1=…=cm,n+1=0. Тем самым, с точностью до обозначений индексов переменных, в качестве исходной транспортной задачи будем рассматривать ее математическую модель в замкнутой форме (2.1)- (2.5).

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

Рассмотрим особенности построение данной таблицы. Верхняя строка и левый столбец содержат искомые значения потенциалов, которые требуется отыскать на последующих этапах алгоритма, и значения правых частей ограничений (2.2)-(2.3).

Таблица 2.2. Общий вид таблицы метода потенциалов

F(x)	v1 b1	v2 b2	….	vn bn
u1 a1	c11 x11	c12 x12	…	c1n x1n
u2 a2	c12 x12	c22 x22	c2n x2n
…	…	…	…	…
um am	cm1 xm1	cm2 xm2	…	cmn xmn

В каждой ячейке таблицы содержится два значения: cij- стоимость транспортировки единицы продукта из i–го пункта производства в j–й пункт потребления и xij - значения переменных начального допустимого решения. При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ячейка называется занятой. Самая верхняя слева ячейка исходной таблицы содержит значение целевой функции (1) для содержащегося в таблице промежуточного решения. При этом значение целевой функции рассчитывается по формуле: F(x)=c11x11+c12x12+…+cnmxnm, где хij-ненулевые элементы таблицы 2.2, соответствующие переменным решаемой задачи.