Бартеньев А.П., Кошаров Н.Н.. Транспортная задача линейного программирования
.pdfМинистерство сельского хозяйства РФ Федеральное государственное образовательное учреждение
высшего профессионального образования «Мичуринский государственный аграрный университет»
Кафедра математического моделирования экономических систем
Транспортная задача линейного программирования
Методические указания и задания для студентов экономических специальностей
заочной и дистанционной форм обучения
Мичуринск-наукоград РФ
2006
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Методические указания разработаны доцентом, к.э.н. А.П. Бартеньевым, ст. преподавателем Н.Н. Кошаровым.
Утверждено методической комиссией экономического факультета протокол № 1 от 25 сентября 2006 г.
©Издательство Мичуринского государственного аграрного университета, 2006
2
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Транспортная задача линейного программирования
Сущность транспортной задачи заключается в нахождении наиболее рационального плана перевозки однородного продукта из пунктов нахождения в пункты потребления. В общем виде транспортная задача формулируется следующим образом. Имеет- ся m пунктов отправления А1, А2,…, Аm однородного продукта, на которых сосредоточено соответственно а1, а2,…, аm количество продукта. Имеется n пунктов потребления1, В2, …, Вn, потреб- ность которых в этом продукте b1, b2,…, bn соответственно. Из- вестны также транспортные издержки на перевозку единицы гру- за из пункта Аi в пункт Вj, которые обозначены через сij. Если общая сумма продукта в пунктах отправления равна общей по-
требности в нем всех пунктов потребления а1+а2+…+аm=b1+b2+…+bn, то такая модель называется закрытой, а если не равна, то модель называется открытой. При решении за- дачи открытая модель всегда приводится к закрытой путем вве- дения фиктивного поставщика, или фиктивного потребителя.
Требуется найти такое неотрицательное решение системы из m+n уравнений
x11+x12+…+x1n=a1 x21+x22+…+x2n=a2
…
…
…
xm1+xm2+…+xmn=аm x11+x21+…+xm1=b1 x12+x22+…+xm2=b2
…
…
…
x1n+x2n+…+xmn=bn
при котором линейная форма достигнет минимума
Z(min)=c11x11+c12x12+…+c1nx1n+c21x21+c22x22+…+c2nx2n+…+cm1xm1+c m2xm2+…cmnxmn.
3
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Обозначим через хij объем перевозок продукта от i-го по- ставщика к j-ому потребителю. Тогда условия задачи удобно бу- дет записать в виде следующей таблицы (табл. 1).
Таблица 1 – Опорный вариант плана
Пункты отправления |
|
Пункты потребления |
|
Наличие |
|||
|
|
|
|
|
|
грузов |
|
|
|
|
|
|
|
|
|
|
В1 |
|
В2 |
… |
|
Вn |
|
А1 |
c11 |
|
c12 |
… |
|
c1n |
a1 |
x11 |
|
x12 |
|
x1n |
|||
|
|
|
|
|
|||
А2 |
c21 |
|
c22 |
… |
|
c2n |
a2 |
x21 |
|
x22 |
|
x2n |
|||
|
|
|
|
|
|||
… |
… |
|
… |
… |
|
… |
… |
Am |
cm1 |
|
cm2 |
… |
|
cmn |
am |
xm1 |
|
xm2 |
|
xmn |
|||
|
|
|
|
|
|||
Потребность в грузах |
b1 |
|
b2 |
… |
|
bn |
|
Вкачестве примера рассмотрим следующую задачу.
Вхозяйстве имеются три навозохранилища, в которых хра- нятся 1000т,1500 т и 920т навоза. Этот навоз нужно вывести на 5 полей: на первое – 450т, на второе – 640т, на третье – 680т, на четвертое – 450т, на пятое – 1200т. Расстояние от навозохрани-
лищ до полей задано матрицей
æ3 |
2 |
5 |
3 |
1ö |
||
ç |
4 |
6 |
2 |
2 |
4 |
÷ |
А=ç |
÷ |
|||||
ç |
5 |
1 |
1 |
6 |
3 |
÷ |
è |
ø |
Для построения опорного плана транспортной задачи суще- ствуют различные методы. Рассмотрим наиболее простой из них
– метод северо-западного угла. Этот метод получил свое название потому, что распределение поставок начинается с левой верхней клетки, что соответствует северо-западу на географической кар- те.
Начинаем заполнение таблицы с клетки К11, соответствую- щей первому поставщику и первому потребителю. Удовлетворя- ем потребности первого поля за счет запасов навоза в первом на- возохранилище. В первом навозохранилище имеется 1000т наво- за, а на первое поле его требуется вывезти 450т, то есть, а1> b1. записываем в клетку К11 450. исключаем первый столбец из рас- смотрения. Из оставшейся части таблицы вновь выберем северо-
4
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
западный угол – клетку К12, которой соответствует первый по- ставщик и второй потребитель. Во второе поле необходимо вы- вести 640т навоза, в первом же навозохранилище осталось лишь 550т навоза. Записываем в клетку К12 550, запасы первого наво- зохранилища исчерпаны. Перемещаемся ко второму навозохра- нилищу в клетку К22 и записываем в нее недостающие 90т, удов- летворив, таким образом, потребность второго поля в навозе. Ис- ключаем из рассмотрения второй столбец и перемещаемся в клет- ку К23. Во втором навозохранилище осталось 1410 т навоза, что
позволяет полностью удовлетворить потребность третьего поля в навозе. Записываем в клетке К23 680т навоза и исключаем третий столбец из рассмотрения. Перемещаемся в клетку К24. во втором хранилище осталось 730т навоза, за счет него удовлетворим по- требность четвертого поля, записав в клетку К24 число 450. Ос- тавшиеся во втором хранилище 280т навоза, запишем в клетку К25. Пятому полю требуется 1200т навоза, недостающие 920т на- воза поставляем из третьего хранилища, записав в клетку К35 920т. В таблице 2 получено исходное опорное решение.
Рассматривая алгоритм записи исходного опорного решения методом северо-западного угла, можно установить следующее:
1.В таблицу всегда заносятся неотрицательные числа.
2.Из рассмотрения исключается строка или столбец лишь то- гда, когда соответствующее ограничение превращается в тожде- ство. Следовательно, после заполнения таблицы все ограничения
–тождества.
3.Так как при записи базисной переменной исключается или строка, или столбец, и лишь при записи последней базисной пе- ременной исключаются одновременно и строка, и столбец, то всего в таблицу вносятся (m+n-1) базисных переменных. После записи опорного плана всегда проверяем соответствует ли коли- чество заполненных клеток величине (m+n-1).
5
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Таблица 2 – Первый вариант плана
Навозохранилище |
|
|
Поля |
|
|
Наличие |
||
В1 |
В2 |
В3 |
В4 |
В5 |
||||
|
|
|||||||
|
|
β1=7 |
β2=6 |
β3=2 |
β4=2 |
β5=4 |
навоза |
|
|
α1= -4 |
3 |
2 |
5 |
3 |
1 |
|
|
А1 |
450 |
550 |
1000 |
|||||
|
|
|
||||||
|
α2= 0 |
4 |
- 6 |
2 |
2 |
+ 4 |
|
|
А2 |
90 |
680 |
450 |
280 |
1500 |
|||
|
||||||||
|
|
5 |
1 |
1 |
6 |
3 |
|
|
|
α3= -1 |
920 |
|
|||||
А3 |
+ |
|
|
920 |
||||
|
|
|
- |
|||||
|
|
|
|
|
|
|
||
Потребность полей в |
|
|
|
|
|
|
||
|
навозе |
450 |
640 |
680 |
450 |
1200 |
3420 |
Определим объем перевозок навоза в тонно-километрах: Z=450*3+550*2+90*6+680*2+450*2+280*4+920*3=9130.
Метод потенциалов
Алгоритм метода потенциалов заключается в следующем.
1.Строим первоначальный опорный план, содержащий (m+n-
1)занятых клеток.
2.Для полученого плана определяем систему потенциалов
ai (i= 1,2,…m) и bj (j= 1,2,…n), исходя из условия сij= ai+bj (это условие действительно для всех занятых клеток). Поскольку для
построения системы потенциалов используем только занятые клетки, то число неизвестных (ai и bj), равное (m+n), на единицу превышает число уравнений, равное (m+n-1). Поэтому для одно-
значного определения всех потенциалов одному из них придают произвольное значение (как правило, тому, для которого в соот- ветствующей ему строке или столбце находится наибольшее ко- личество занятых клеток). Обычно в качестве такого произволь- ного значения выбирается нуль. Затем из условия сij= ai+bj по- следовательно находят значения остальных потенциалов.
3. Исследуем систему потенциалов на оптимальность. План оптимален, если для всех незанятых клеток выполняется условие
сij ³ aI+bj, или сij-(ai+bj) ³ 0. То есть, разность между оценкой незанятой клетки и суммой потенциалов строки и столбца, на пе-
ресечении которых находится эта клетка, является неотрицатель-
6
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
ной величиной. Обозначим эту разность через lij. Проверим вы- полнение условия lij ³ 0 для каждой свободной клетки. Если это условие выполняется, то построенный опорный план оптимален.
Впротивном случае переходим к новому плану.
4.Для этого вычислим lij для всех незанятых клеток и среди
отрицательных величин находим наибольшую по абсолютному значению, что соответствует клетке с максимальным нарушением оптимальности. Такая клетка называется “плохой”.
5.Для найденной клетки строим замкнутый маршрут по за- нятым клеткам. Такой маршрут всегда существует и определяет- ся единственным образом. Маршрут начинается с плохой клетки и в ней же заканчивается – маршрут замкнут. Переход от одной клетки к другой осуществляется только по горизонтали и верти- кали, причем в углах поворота маршрута обязательно должны находится заполненные клетки.
6.В углах поворота маршрута проставляем знаки плюс и ми- нус через один, начиная с “плохой” клетки, в которую записыва-
ем “+”.
7.Выбираем наименьшую поставку среди клеток, помечен- ных знаком “-”.
8.Переходим к новому варианту плана. Для этого найденную наименьшую поставку прибавляем в клетки, помеченные знаком “+” и вычитаем из клеток, помеченных знаком “-”. Полученный вариант плана вновь проверяем на оптимальность. Процесс про- должается до тех пор, пока все свободные клетки не будут удов- летворять условию оптимальности.
Вернемся к нашей задаче. Наибольшее число занятых клеток имеется во второй строке. Примем потенциал этой строки рав-
ным нулю (a2= 0). Вычислим потенциалы остальных строк и столбцов, исходя из условия что для всех занятых клеток
сij=ai+bj. Для клетки k22 6=0+b2, отсюда b2=6-0= 6. Далее b3=2-
0=2, b4=2-0= 2, b5= 4-0= 4. Перейдя в клетку k12, для которой по- тенциал второго столбца известен, можно рассчитать потенциал
первой строки a1=2-6=-4, далее рассчитаем потенциал первого столбца b1=3-(-4)=7. Остается рассчитать потенциал третей стро- ки через оценку клетки k15 и потенциал пятого столбца a3=3-4= -1.
7
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Проверяем план на оптимальность, рассчитав для всех неза- нятых клеток lij.
l13=5-(-4)-2=7 l14=3-(-4)-2=5 l15=1-(-4)-4=1 l21=4-0-7=-3 l31=5-(-1)-7=-1 l32=1-(-1)-6=-4 l33=1-(-1)-2=0 l34=6-(-1)-2=5.
Условие оптимальности не выполняется для клеток k21, k31 и k32, причем самой “плохой” является клетка k32, для которой
l32= -4.
Проставляем в клетку k32 знак “+” и строим для нее замкну- тый маршрут, чередуя в углах поворота знаки “-” и “+”. Из клет-
ки k32 придем в клетку k22, из нее в клетку k25, затем в клетку k35 и вернемся в клетку k32. Маршрут может проходить через занятые
клетки (он прошел через клетки k23 и k24).Контур маршрута обо- значим пунктиром. Просмотрев клетки, помеченные знаком “-” находим, что наименьшая величина грузоперевозки среди них равна 90т. Прибавляем эту величину в клетки, помеченные зна- ком “+”, и вычитаем из клеток, помеченных знаком “-”. Перехо- дим к новому варианту плана (табл. 3).
Таблица 3 – Второй вариант плана
Навозохранилища |
|
|
Поля |
|
|
|
||
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
|||
|
|
β1=3 |
β2=2 |
β3=2 |
β4=2 |
β5=4 |
||
|
|
навоза |
||||||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
α1= 0 |
3 |
- 2 |
5 |
3 |
1 |
|
|
А1 |
450 |
550 |
|
|
+ |
1000 |
||
|
α2= 0 |
4 |
6 |
2 |
2 |
4 |
|
|
А2 |
|
|
680 |
450 |
370 |
1500 |
||
|
|
5 |
1 |
1 |
6 |
3 |
|
|
А3 |
α3= -1 |
90 |
830 |
920 |
||||
|
|
|
||||||
|
+ |
|
|
- |
||||
|
|
|
|
|
|
|||
Потребность полей |
|
|
|
|
|
|
||
|
в навозе |
450 |
640 |
680 |
450 |
1200 |
3420 |
|
|
|
|
|
|
|
|
|
8
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Приравняв α2 к нулю, рассчитываем потенциалы строк и столбцов и повторяем всю вычислительную процедуру. Условие оптимальности не выдерживается для клетки k15 (l15=1-0-4 = -3). Строим для этой клетки замкнутый маршрут, находим наимень- шую величину грузоперевозки в клетках, помеченных знаком “-” (550т), прибавляем ее в клетки, помеченные знаком “+” и вычи- таем из клеток, помеченных знаком “-”. Получаем новый вариант плана (табл. 4).
Таблица 4 – Третий вариант плана
Навозохранилища |
|
|
Поля |
|
|
Наличие |
||
В1 |
В2 |
В3 |
В4 |
В5 |
||||
|
|
|||||||
|
|
β1=6 |
β2=2 |
β3=2 |
β4=2 |
β5=4 |
навоза |
|
|
|
- 3 |
2 |
5 |
3 |
1 |
|
|
|
α1= -3 |
550 |
|
|||||
А1 |
450 |
|
|
|
1000 |
|||
|
|
|
+ |
|||||
|
α 2= 0 |
4 |
6 |
2 |
2 |
4 |
|
|
А2 |
+ |
|
680 |
450 |
370 - |
1500 |
||
|
α3= -1 |
5 |
1 |
1 |
6 |
3 |
|
|
А3 |
|
640 |
|
|
280 |
920 |
||
Потребность полей в на- |
|
|
|
|
|
|
||
|
возе |
450 |
640 |
680 |
450 |
1200 |
3420 |
|
|
|
|
|
|
|
|
|
Условие оптимальности не выполняется для клетки k21(l21=4-0-6=-2).Строим для этой клетки замкнутый маршрут, пе-
рераспределяем поставки и получаем четвертый вариант плана
(табл. 5).
Таблица 5 – Четвертый вариант плана
Навозохранилища |
|
|
Поля |
|
|
|
||
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
|||
|
|
|||||||
|
|
β1=4 |
β2=0 |
β3=2 |
β4=2 |
β5=2 |
навоза |
|
|
α1= -1 |
3 |
2 |
5 |
3 |
1 |
|
|
А1 |
- |
|
|
|
920 + |
1000 |
||
|
|
80 |
|
|
|
|
||
|
|
4 |
|
2 |
2 |
|
|
|
|
|
6 |
|
4 |
|
|||
А2 |
α2= 0 |
+ 370 |
680 |
450 |
1500 |
|||
|
|
|||||||
|
|
|
- |
|
|
|||
|
|
|
|
|
|
|
||
|
α3= 1 |
5 |
1 |
1 |
6 |
3 |
920 |
|
А3 |
640 |
+ |
280 – |
|||||
|
|
|
||||||
Потребность полей |
|
|
|
|
|
|
||
|
в навозе |
450 |
640 |
680 |
450 |
1200 |
3420 |
9
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
В четвертом варианте плана условие оптимальности не вы- полняется для клетки К33(l33 =1-1-2=-2). Повторив всю вычисли- тельную процедуру, получаем следующий вариант плана (табл.6).
Таблица 6 – Пятый вариант плана
Навозохранилища |
|
|
Поля |
|
|
Наличие |
||
|
|
|
|
|
||||
В1 |
В2 |
В3 |
В4 |
В5 |
||||
|
|
|||||||
|
|
β1=4 |
β2=2 |
β3=2 |
β4=2 |
β5=4 |
навоза |
|
А1 |
α1= -3 |
3 |
2 |
5 |
3 |
1 |
|
|
|
|
|
|
1000 |
1000 |
|||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
А2 |
α2= 0 |
4 |
6 |
2 |
2 |
4 |
1500 |
|
|
|
450 |
|
600 |
450 |
|
||
|
|
|
|
|
|
|
|
|
А3 |
α3= -1 |
5 |
1 |
1 |
6 |
3 |
920 |
|
|
|
|
640 |
80 |
|
200 |
||
|
|
|
|
|
||||
|
|
|
|
|
|
|
||
Потребность полей |
|
|
|
|
|
|
||
|
в навозе |
450 |
640 |
680 |
450 |
1200 |
3420 |
Условие оптимальности выполняется для всех незанятых клеток.
Zmin=1000*1+450*4+600*2+450*2+640*1+80*1+200*3=6220.
Согласно, полученному решению из первого навозохранилища следует все 1000т навоза вывезти на пятое поле, из второго:450т – на первое поле, 600т – на третье поле, 450т – на четвертое поле, из третьего: 640т – на второе поле, 80т – на третье поле и 200т – на пятое поле.
Построение опорного варианта плана методом наименьшей оценки
При построении первоначального опорного варианта плана методом северо-западного угла мы не учитываем оценки мар- шрутов перевозки – в нашем примере они означали расстояние от навозохранилищ до полей.
Суть метода наименьшей оценки заключается в том, что про-
сматривается первый столбец и выбирается клетка с наименьшей оценкой и в нее записывается максимально возможное количест- во груза. Затем из рассмотрения исключается либо столбец (если потребности соответствующего потребителя полностью удовле- творены), либо строка (если запасы соответствующего поставщи- ка полностью израсходованы). Переходим в следующий столбец,
10
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com