Дипломная работа: Решение транспортной задачи линейного программирования в среде MS Excel

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