Алгоритм решения (метод северо- западного угла и метод потенциалов)

Автор: | 25.02.2017

Транспортная задача по критерию стоимости

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

Пусть в р пунктах отправления находятся соответственно a1, a2, … ap единиц однородного груза, который должен быть доставлен q потребителям в ко­личествах b1, b2, … bq единиц. Заданы стоимости сik перевозок единицы груза из i-го пункта отправления k-му пункту потребления. Обозначим через хik³0 (i=l, 2, ... , р; k= 1, 2, ... , q) количество единиц груза, перевозимого из i-го склада k-му потребителю; тогда переменные xikдолжны удовлетворять следующим

ограничительным условиям:

(i=l, 2, ... , р); (k= 1, 2, ... , q); хjk³0.

Суммарные затраты на перевозки равны

L=c11x11+c12x12+…+cpqxpq= .

Следовательно, требуется найти pq переменных хjk, удов­летворяющих указанным условиям и минимизирующих, целевую функцию L. Решение такой задачи разбивается на два этапа:

1) определение исходного опорного решения;

2) построение последовательных итераций, т. е. приближение к оптимальному решению.

Алгоритм решения (метод северо- западного угла и метод потенциалов)

1. Определение исходного опорного решения (метод северо- западного угла). Пусть мы имеем таблицу исход­ных данных задачи. Исходное опорное решение будем строить, по так называемому. правилу «северо-западного угла».

ai bk b1 b2 bk bq
a1 x11 c11 x12 c12 x1k c1k x1q c1q
a2 x21 c21 x22 c22 x2k c2k x2q c2q
ai xi1 ci1 xi2 ci2 xik cik xiq ciq
ap xp1 cp1 xp2 cp2 xpk cpk xpq cpq

Заполним вышеуказанную таблицу, начиная с левого верхнего угла, двигаясь далее или по строке вправо, или по столбцу вниз. В клетку (1, 1) занесем меньшее из чиселa1 и b1, т.е. x11=min{a1 , b1}.

Еслиa1 > b1 , то x11=b1 и первый столбец «закрыт», т. е. потребности пер­вого потребителя удовлетворены полностью. Двигаемся далее по первой строке, записывая в соседнюю клетку (1, 2) меньшее из чисел a1 - b1 и b2 т.е. x12=min{a1- b1 , b2}.

Если же b2 > a1, то аналогично «закрывается» первая строка и далее переходим к заполнению соседней клетки (2, 1), куда заносим x21=min{а2,b1 - a1}.

Будем продолжать этот процесс до тех пор, пока на каком-то этапе не исчерпы­ваются ресурсы аp и потребности bq.

2. Построение последовательных итераций (метод потенциалов). Получив исходное опорное реше­ние, перейдем теперь к построению опорных решений, улучшающих друг друга: для этого применим метод потенциалов.

Итак, после построения исходного опорного решения все переменные разбиты на две группы: xkl- базисные и xpq - свободные; линейные функции стоимости перевозок выразятся через свободные переменные так:

Для нахождения коэффициентов γрq при свободных переменных сопоставим каждому пункту отправления Ai некоторую величину ui (i=l, 2, ... , m), кото­рую назовем потенциалом пункта Ai, и каждому пункту назначения Bjвеличину vj -потенциал пункта Bj. Свяжем эти величины равенством uk + vl = ckl , где ckl - стоимость перевозки одной тонны груза из пункта Ak в пункт Bl. Доказы­вается, что совокупность уравнений uk + vl = ckl, составленных для всех базисных переменных, составляет совместную систему линейных уравнений, причем значе­ние одной из переменных можно задавать произвольно, и тогда значения осталь­ных переменных находятсяиз системы однозначно. Обозначим для свободных пе­ременных сумму соответствующих потенциалов через c'pq , т. е. up + vq = c'pq и назовем её косвенной стоимостью (в отличие от данной стоимости cpq). Тогда коэффициенты при свободных переменных в соотношении (1) определяются с по­мощью равенства gpq = cpq - c'pq.

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

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

1. Находят потенциалы uk и vl всех пунктов отправления Ak и назначе­ния Bl.

2. Выбирают какую-нибудь свободную переменную, для которой сумма по­тенциалов строго больше соответствующей стоимости, это соответствует элементу с отрицательным коэффициентом при свободной переменной в правой части функ­ции L.

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

4. Вышеуказанные операции 1—3 повторяют до тех пор, пока не получат оптимальный базис, т.е. неотрицательные коэффициенты при свободных перемен­ных в правой части линейной функции L.

Пример решения

Пример. В двух пунктах отправления А и В находится соответст­венно 150 и 90 т рекламной продукции. В пункты1, 2, 3 требуется доставить соответственно 60, 70 и 110 т. этой продукции. Стоимости перевозки тонны из пункта А в пункты 1, 2, 3 составляют соответственно 6, 10 и 4 руб., а из пункта В—12, 2 и 8 руб. Составить оптималь­ный план перевозок продукции так, чтобы общая сумма транспорт­ных расходов была наименьшей.

Таблица 1.

ai bk
А
В

Запишем исходные данные в табл. 1. Заполнение начнем с клетки (1, 1): x11=min{150, 60} = 60, первый столбец закрыт. Переходим к клетке (1, 2): x12=min {150—60, 70}= 70, второй столбец закрыт; далее, переходим к клетке (1, З):

x13=min{150—60—70, 110} = 20. Так как в третьем столбце оказался остаток, равный 90, то переходим к заполнению клетки (2, 3), куда заносим x23= min {90, 90} = 90. Поскольку остатки по строке и столбцу равны нулю, опорное исходное решение построено. Этому плану соответствуют затраты в количестве L =6.60 +10.70+4.20+8.90==1860 руб.

В правиле «северо-западного угла» не учитывается величина затрат cik, a потому исходное опорное решение часто может быть далеким от оптимального. Применяют также прием «минимального элемента», в котором учитывается вели­чина cik. В этом случае построение исходного опорного решения начинают с клет­ки с наименьшей величиной cik, в данном примере - с клетки (2, 2), где c22=2 (табл. 2). В эту клетку заносим x22= min { a2 , b2} = min{90, 70} =70.

Таблица 2

ai bk
А
В
остаток

Остатки по строке и столбцу записываем в соответствующие клетки строки и столбца остатков. Столбец b2 закрыт. Теперь переходим к клетке (1. 3), так как после c22 = 2 наименьшим является c13=4. В клетку (1, 3) заносим x13=min{a1- b1 , b3}=min{ 150—60, 110}=90. Затем переходим к клетке (1, I):

x11=min{a1 , b1}= min {150, 60}==60. Наконец, переходим к клетке (2, 3), в ко­торую заносим x23=min{a2- b2 , b3}= min {90—70, 110} =20.

Применяя это правило, мы получили другой вариант исходного опорного решения, при котором затраты L=6.60+4.90+2.70+8.20=1020 руб., т.е. сум­ма затрат ближе к оптимальному плану.

Воспользуемся изложенными общими понятиями и продолжим решение Примера. Мы получили исходное опорное решение (следуя правилу «минимального элемента»): x11= 60, x12= 0, x13=90, x21=0, x22= 70, x23=20, L=1020. Для нахождения потенциалов необходимо решить систему

.

Значение одного из неизвестных зададим произвольно, например u1 =l. Тогда v1 =5, v3 = -3, u2 =5, v2 = -3. Далее вычисляем косвенные стоимости c'pq:

c'12 = u1 + v2 = -2, c'21 = u2 + v1 = 10.

Подсчитаем теперь разности gpq = cpq - c'pq:

g12 = c12 - c'12 =10-(-2)=12, g21 = c21 - c'21 = 12-10=2.

Следовательно, выражение L через свободные переменные имеет вид L = 1020 + 12 x12+2 x21. Среди коэффициентов при переменных в правой части нет отрицательных. Значит, исходное опорное решение является оптимальным. Таким образом, правило «минимального элемента» сразу дает оптимальное решение.

Решим теперь эту же задачу при условии, что исходное решение получено по правилу «северо-западного угла», т.е. x11= 60, x12= 70, x13=20, x23=90, L=186O. Для нахождения потенциалов необходимо решить систему

.

Полагая u1 =l, получим v1 =5, v2 = 9, v3 = 3, u2 = 5,.

Вычисляем косвенные стоимости c'pq:

c'21 = u2 + v1 = 10, c'22 = u2 + v2 = 14.

Подсчитаем теперь разности gpq = cpq - c'pq:

g21 = c21 - c'21 =12-10= 2, g22 = c22 - c'22 = 2-14= -12.

Следовательно, выражение L через свободные переменные имеет вид L = I860 + 2 x21 - 12 x22. Среди коэффициентов при переменных в правой части есть отрицательный при x22, следовательно, можно попытаться уменьшить L, увеличив x22 (сохранив нулевое значение x21). Положим x22=l. Поскольку суммы значений неизвестных по строкам и столбцам должны остаться неизменными, нужно про­извести следующий балансовый пересчет:

70 -l. 20+l
l90-l

Добавление l к x22компенсируется вычитанием l из x12, а это в свою очередь ­прибавлением l к x13 и т.д. до тех пор, пока мы не вернемся обратно к x22. Обходя клетки по пунктирной ломаной линии, в однойиз вершин которой нахо­дится свободная переменная x22 , а в остальных вершинах - базисные переменные (причем не обязательно все), мы получим так называемый цикл пересчета (лома­ная называется циклом), отвечающий свободной клетке x22. Как видно из табли­цы, для неотрицательности переменных l можно увеличить до l=70, тогда получим второе опорное решение:

0
0 70

т.е. x11= 60, x12= 0, x13=90, x21=0, x22= 70, x23=20. Значение функции L для него составляет L=1860 – 12,70=1020, т. е. полу­чили оптимальное решение (судя по предыдущему решению).

Литература

1. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. М.”Высшая школа”. ч.1. -320 с.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

10 + = 18