Бартеньев А.П., Кошаров Н.Н.. Транспортная задача линейного программирования
.pdfнаходим клетку с наименьшей оценкой и заносим в нее количест- во груза, обеспечиваемое соответствующим поставщиком.
При переходе в последний столбец потребность обеспечиваем за счет тех поставщиков, у которых остался нераспределенный груз.
Можно построить опорный вариант плана и методом наи- меньшей оценки по строке.
Вернемся к нашей задаче и построим опорный вариант плана методом наименьшей оценки по столбцу.
Таблица 7 – Опорный вариант плана
Навозохранилища |
|
|
Поля |
|
|
|
||
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
|||
|
|
|||||||
|
|
β1=6 |
β2=2 |
β3=2 |
β4=2 |
β5=4 |
навоза |
|
|
|
3 |
2 |
5 |
3 |
1 |
1000 |
|
А1 |
α1= -3 |
- 450 |
550+ |
|||||
|
|
|
|
|||||
|
|
|
|
|
|
|||
|
|
4 |
6 |
2 |
2 |
4 |
|
|
А2 |
α2= 0 |
+ |
400 |
450 |
650 - |
1500 |
||
|
||||||||
|
|
|
|
|||||
А3 |
α3= -1 |
5 |
1 |
1 |
6 |
3 |
|
|
640 |
280 |
920 |
||||||
|
|
|
|
|
||||
|
|
|
|
|
|
|||
Потребность полей |
|
|
|
|
|
|
||
|
в навозе |
450 |
640 |
680 |
450 |
1200 |
3420 |
|
|
|
|
|
|
|
|
|
|
В первом столбце наименьшее расстояние от навозохрани- лища до поля в клетке К11. поэтому все 450т, необходимые пер- вому полю, запланируем вывезти из первого навозохранилища, записав в клетку К11 450. Просматриваем второй столбец и нахо- дим клетку с наименьшей оценкой К32. Необходимые второму полю 640т навоза поставим из третьего навозохранилища, запи- сав соответствующую величину в клетку К32. В третьем столбце клетка с наименьшей оценкой расположена в третьей строке. Сюда занесем 280т, оставшиеся в третьем навозохранилище, а недостающие 400т поставим из второго навозохранилища. Про- смотрев четвертый столбец, находим, что необходимые четвер- тому полю 450т навоза выгоднее всего вывезти из второго наво- зохранилища, ибо здесь наименьшее расстояние перевозки. В клетку К24 запишем 450. И потребности пятого поля удовлетво- ряем за счет оставшихся в первом навозохранилище 550т навоза и 650т, оставшихся во втором навозохранилище. Полученный опорный вариант плана выглядит следующим образом (табл.7).
11
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Рассчитаем объем перевозок в тоннокилометрах: Z=450*3+550*1+400*2+450*2+650*4+640*1+280*1=7120
Как видим, объем грузоперевозок значительно меньше, чем в опорном плане, составленном методом северо-западного угла.
Проверив опорный вариант плана на оптимальность, нахо- дим, что условие оптимальности не выполняется для клетки К21(l 21= 4-0-6= -2). Построив для этой клетки замкнутый маршрут и перераспределив грузоперевозки, получаем следующий вариант
(табл.8).
Таблица 8 – Второй вариант плана
Навозохранилища |
|
|
|
|
Поля |
|
|
|
|
|
|
|
В1 |
|
В2 |
В3 |
В4 |
В5 |
|
Наличие |
|
||
|
|
|
|
|
|
||||||
|
|
|
β1=4 |
|
β2=2 |
β3=2 |
β4=2 |
β5=4 |
|
навоза |
|
|
|
|
3 |
|
2 |
5 |
3 |
1 |
|
|
|
А1 |
α1= -3 |
|
|
1000 |
|
1000 |
|
||||
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
α2= 0 |
|
4 |
|
6 |
2 |
2 |
4 |
|
|
|
А2 |
|
450 |
|
400 |
450 |
200 |
|
1500 |
|
||
|
|
|
|
|
|||||||
|
|
|
5 |
|
1 |
1 |
6 |
3 |
|
|
|
А3 |
α3= -1 |
|
|
640 |
280 |
|
920 |
|
|||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
||
Потребность полей |
|
|
|
|
|
|
|
|
|
|
|
|
в навозе |
|
450 |
|
640 |
680 |
450 |
1200 |
|
3420 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Для |
всех |
незанятых |
клеток |
выполняется |
условие |
||||||
сij-(ai-bj) ³ 0. получен оптимальный план уже во второй таблице. Zmin=1000*1+450*4+400*2+450*2+200*4+640*1+280*1=6220.
Открытая модель транспортной задачи
Как было отмечено выше, открытая модель транспортной за-
дачи всегда приводится к закрытой путем введения фиктивного поставщика или фиктивного потребителя. При этом следует иметь ввиду, что при построении первоначального опорного пла-
на методом наименьшей оценки необходимо наименьшую из них выбирать только среди оценок реальных поставщиков и потреби- телей, а распределять запасы фиктивного поставщика или удов- летворять потребности фиктивного потребителя следует в по- следнюю очередь.
12
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Пример. В хозяйстве во время уборки требуется перевезти зерно с пяти полей на три сушильно-сортировальных агрегата. С первого поля необходимо вывезти 190т зерна, со второго - 220т, с третьего – 140т, с четвертого – 250т, с пятого – 200т, всего – 1000т. Производительность первого сушильного агрегата – 180т, второго – 240т, третьего – 380т, всего они могут пропустить 800т зерна.
В данной задаче зерна имеется на 200т больше, чем могут его переработать сушильные агрегаты. Введем еще один четвертый сушильно-сортировальный агрегат, то есть, так называемого фик- тивного потребителя. Расстояния с полей до фиктивного агрегата примем равными нулю. В клетках четвертого столбца запишем нулевые оценки. Удовлетворять потребности фиктивного агрега- та будем в последнюю очередь.
Первоначальный опорный вариант плана построим методом наименьшей оценки. Просматриваем первый столбец и видим, что самое короткое расстояние до первого агрегата – 1км от пер- вого поля. В клетку К11 запишем необходимые первому агрегату 180т зерна. Во втором столбце в клетку К22 занесем 220т, в треть- ем столбце запишем в клетку К53 200т и в клетку К43 180т. Не- достающие второму агрегату 20т зерна запишем в клетку К32. Все нераспределенное зерно отправим фиктивному агрегату, записав
в клетку К14 10т, в клетку К34 120т и в клетку К44 70т. В резуль-
тате проделанных операций получен опорный вариант плана
(табл.9).
Таблица 9 – Опорный вариант плана
|
Поля |
|
Сушильные агрегаты |
|
|
||
|
В1 |
В2 |
В3 |
|
В4 |
Наличие |
|
|
|
|
|||||
|
|
β1=1 |
β2=10 |
β3=3 |
|
β4=0 |
зерна |
|
α1= 0 |
1 |
5 |
3 |
|
0 |
|
А1 |
180 |
|
10 |
190 |
|||
|
|
|
|||||
А2 |
α2= -6 |
7 |
4 |
6 |
|
0 |
|
220 |
|
450 |
220 |
||||
|
|
|
|
|
|||
А3 |
α3= 0 |
5 |
10 |
4 |
|
0 |
140 |
|
|
|
- 20 |
|
|
120 + |
|
А4 |
α4= 0 |
4 |
4 |
3 |
|
0 |
250 |
|
|
|
+ |
180 |
|
70 - |
|
А5 |
α5= -2 |
5 |
4 |
1 |
|
0 |
|
|
|
200 |
|
|
200 |
||
|
|
|
|
|
|
||
Потребность |
180 |
240 |
380 |
|
200 |
1000 |
|
агрегатов в зерне |
|
||||||
|
|
|
|
|
|
||
|
|
|
|
|
|
|
13 |
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Проверив план на оптимальность, находим, что условие оп- тимальности не выполняется для клеток К12, К42, и К52. Самой «плохой» из них является клетка К42, для которой строим замкну- тый маршрут и перераспределяем поставки. Получаем следую- щий вариант плана (табл.10).
Таблица 10 – Второй вариант плана
|
Поля |
|
Сушильные агрегаты |
|
|
||
|
В1 |
В2 |
В3 |
В4 |
Наличие |
||
|
|
||||||
|
|
β1=1 |
β2=4 |
β3=3 |
β4=0 |
зерна |
|
|
α1= 0 |
1 |
5 |
3 |
0 |
|
|
А1 |
180 |
10 |
190 |
||||
|
|
||||||
А2 |
α2= 0 |
7 |
4 |
6 |
0 |
|
|
220 |
220 |
||||||
|
|
|
|
|
|||
А3 |
α3= 0 |
5 |
10 |
4 |
0 |
|
|
140 |
140 |
||||||
|
|
|
|
|
|||
А4 |
α4= 0 |
4 |
4 |
3 |
0 |
|
|
|
|
20 |
180 |
50 |
250 |
||
|
|
|
|||||
А5 |
α5= -2 |
5 |
4 |
1 |
0 |
|
|
200 |
200 |
||||||
|
|
|
|
|
|||
Потребность агрегатов в |
180 |
240 |
380 |
200 |
1000 |
||
|
зерне |
||||||
|
|
|
|
|
|
||
Проверив второй вариант плана на оптимальность, видим, что условие оптимальности выполняется для всех незанятых кле- ток. Получен оптимальный план. Минимальный объем грузопе- ревозок в тонно-километрах составляет:
Z=180*1+220*4+20*4+180*3+200*1=1880.
Минимальный объем грузоперевозок, может быть, достигнут, если к первому агрегату 180т зерна будет доставлено с первого поля, ко втором агрегату – 220т со второго поля и 20т с четверто- го поля, к третьему агрегату – 180т с четвертого поля и 200т с пя- того поля. Оставшиеся нераспределенными по сушильным агре- гатам 10т зерна с первого поля, 140т с третьего поля и 50т с чет- вертого поля будут вывезены в другие места(на ток, зерносклад и т.п.).
В заключение обратим внимание на то, что при построении
опорного плана иногда не выдерживается условие по количеству занятых клеток(m+n-1). Если не хватает одной занятой клетки и получен так называемый вырожденный опорный план, для устра-
нения вырожденности следует дополнить количество занятых клеток до(m+n-1), введя нулевую перевозку. Клетки, в которые вводят нулевые перевозки, называют фиктивно занятыми.
14
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Можно заранее не выбирать фиктивно занятую клетку, а оп- ределить ее в процессе вычисления потенциалов.
Вначале рассчитывают потенциалы строк и столбцов, кото- рые можно рассчитать. Затем просматривают строки и столбцы, потенциалы которых нельзя рассчитать из-за отсутствия еще од- ной заполненной клетки. В качестве фиктивно занятой клетки выбирается та, в которой проставлена наименьшая оценка. В эту
клетку записывается нуль и затем рассчитываются недостающие потенциалы.
Задача1. В хозяйстве во время уборки требуется перевезти зерно с пяти полей (табл.11) на три сушильно-сортировальных агрегата(табл.13). Расстояния перевозки зерна с полей на су- шильно-сортировальные пункты известны (табл.12).
Требуется составить такой план перевозки зерна, чтобы об- щий объем перевозок в тонно-километрах был минимальным.
Таблица 11 – Количество поступающего зерна с полей, т
№ варианта |
|
|
Поля |
|
|
|
1 |
2 |
3 |
4 |
5 |
||
|
||||||
1 |
200 |
250 |
100 |
300 |
150 |
|
2 |
200 |
300 |
250 |
100 |
150 |
|
3 |
150 |
100 |
300 |
200 |
250 |
|
4 |
100 |
150 |
300 |
250 |
200 |
|
5 |
150 |
250 |
200 |
100 |
300 |
|
6 |
200 |
250 |
100 |
150 |
300 |
|
7 |
300 |
100 |
250 |
150 |
100 |
|
8 |
100 |
300 |
150 |
200 |
250 |
|
9 |
100 |
150 |
200 |
250 |
300 |
|
10 |
100 |
150 |
180 |
250 |
320 |
|
11 |
180 |
170 |
130 |
270 |
250 |
|
12 |
210 |
90 |
190 |
260 |
250 |
|
13 |
300 |
150 |
100 |
200 |
250 |
|
14 |
150 |
100 |
300 |
250 |
200 |
|
15 |
100 |
300 |
150 |
180 |
270 |
|
16 |
260 |
190 |
280 |
170 |
100 |
|
17 |
310 |
240 |
100 |
170 |
180 |
|
18 |
220 |
230 |
250 |
200 |
100 |
|
19 |
100 |
220 |
330 |
200 |
150 |
|
20 |
310 |
140 |
180 |
270 |
100 |
|
21 |
260 |
140 |
100 |
300 |
200 |
|
22 |
210 |
240 |
140 |
260 |
150 |
|
23 |
150 |
100 |
320 |
230 |
200 |
|
24 |
270 |
280 |
100 |
190 |
160 |
|
25 |
200 |
160 |
240 |
120 |
280 |
15
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Таблица 12 – Расстояние от полей до сушильно-сортировальных агрегатов,
км
Поля |
|
Сушильно-сортировальные агрегаты |
|
||
1 |
|
2 |
|
3 |
|
|
|
|
|||
1 |
4 |
|
5 |
|
3 |
2 |
7 |
|
4 |
|
6 |
3 |
5 |
|
7 |
|
2 |
4 |
6 |
|
4 |
|
3 |
5 |
2 |
|
5 |
|
7 |
Таблица 13 – Объем перерабатываемого зерна на сушильно-
сортировальных агрегатах
№ варианта |
|
Сушильно-сортировальные агрегаты |
|
||
1 |
|
2 |
|
3 |
|
|
|
|
|||
1 |
300 |
|
100 |
|
150 |
2 |
280 |
|
320 |
|
230 |
3 |
250 |
|
100 |
|
200 |
4 |
100 |
|
300 |
|
150 |
5 |
150 |
|
250 |
|
150 |
6 |
350 |
|
150 |
|
100 |
7 |
200 |
|
300 |
|
100 |
8 |
150 |
|
200 |
|
250 |
9 |
100 |
|
150 |
|
300 |
10 |
250 |
|
420 |
|
230 |
11 |
240 |
|
360 |
|
300 |
12 |
180 |
|
420 |
|
260 |
13 |
220 |
|
440 |
|
280 |
14 |
340 |
|
260 |
|
250 |
15 |
290 |
|
310 |
|
350 |
16 |
300 |
|
400 |
|
240 |
17 |
420 |
|
180 |
|
270 |
18 |
330 |
|
430 |
|
200 |
19 |
290 |
|
210 |
|
420 |
20 |
350 |
|
250 |
|
350 |
21 |
220 |
|
480 |
|
240 |
22 |
400 |
|
400 |
|
100 |
23 |
410 |
|
340 |
|
180 |
24 |
270 |
|
270 |
|
260 |
25 |
320 |
|
420 |
|
210 |
Задача 2. Минеральные удобрения из трех складов(табл.15) необходимо доставить пяти хозяйствам (табл.16). Расстояния пе- ревозки минеральных удобрений из складов до хозяйств извест- ны (табл.14).
16
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Требуется составить такой план перевозки минеральных удобрений, чтобы общий грузооборот в тонно-километрах был минимальным.
Таблица 14 – Расстояния от хозяйств до складов минеральных удобрений
Склады |
|
|
Хозяйства |
|
|
|
1 |
2 |
3 |
|
4 |
5 |
|
|
|
|||||
1 |
5 |
4 |
6 |
|
3 |
2 |
2 |
7 |
3 |
3 |
|
2 |
3 |
3 |
9 |
5 |
2 |
|
6 |
12 |
Таблица 15 – Наличие минеральных удобрений на складах, т
№ варианта |
|
Склады |
|
|
1 |
2 |
3 |
||
|
||||
1 |
1700 |
2300 |
2500 |
|
2 |
2000 |
2500 |
2000 |
|
3 |
2000 |
3000 |
3500 |
|
4 |
2000 |
2500 |
3000 |
|
5 |
3500 |
3300 |
2700 |
|
6 |
2000 |
2000 |
2500 |
|
7 |
2000 |
2500 |
4500 |
|
8 |
1750 |
2250 |
2000 |
|
9 |
2100 |
2000 |
4500 |
|
10 |
2700 |
4500 |
3300 |
|
11 |
3000 |
2500 |
2000 |
|
12 |
3000 |
3000 |
2500 |
|
13 |
2300 |
3000 |
3200 |
|
14 |
2500 |
3000 |
3000 |
|
15 |
2000 |
3000 |
3500 |
|
16 |
2000 |
1000 |
1500 |
|
17 |
3500 |
2700 |
3300 |
|
18 |
1500 |
2000 |
1500 |
|
19 |
3500 |
2000 |
3000 |
|
20 |
2000 |
2500 |
3000 |
|
21 |
3500 |
3300 |
2700 |
|
22 |
2000 |
3000 |
2500 |
|
23 |
3000 |
3500 |
2000 |
|
24 |
2000 |
2000 |
2500 |
|
25 |
1700 |
2500 |
2300 |
17
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Таблица 16 – Потребность хозяйств в удобрениях, т
№ варианта |
|
|
Хозяйства |
|
|
|
12 |
2 |
3 |
4 |
5 |
||
|
||||||
1 |
1500 |
1100 |
1600 |
900 |
1400 |
|
2 |
1000 |
1900 |
1200 |
1100 |
1300 |
|
3 |
1700 |
2000 |
1400 |
1950 |
1450 |
|
4 |
1350 |
1200 |
1350 |
1500 |
2100 |
|
5 |
1700 |
2200 |
1500 |
2000 |
2100 |
|
6 |
1400 |
1600 |
1000 |
1300 |
1200 |
|
7 |
3250 |
1250 |
2500 |
1000 |
1000 |
|
8 |
1000 |
1900 |
1000 |
800 |
1300 |
|
9 |
1500 |
2100 |
1700 |
2200 |
2000 |
|
10 |
2200 |
2300 |
1900 |
2000 |
2100 |
|
11 |
1500 |
1800 |
1200 |
1400 |
1600 |
|
12 |
1300 |
1500 |
1900 |
2500 |
1300 |
|
13 |
2000 |
1800 |
1300 |
1500 |
1900 |
|
14 |
1400 |
1150 |
2250 |
2200 |
1500 |
|
15 |
1700 |
1400 |
2000 |
1950 |
1450 |
|
16 |
1500 |
750 |
600 |
750 |
900 |
|
17 |
2200 |
1700 |
1500 |
2100 |
2000 |
|
18 |
900 |
1000 |
1100 |
1300 |
700 |
|
19 |
1100 |
2700 |
1500 |
1900 |
1300 |
|
20 |
1350 |
1200 |
1350 |
1500 |
2100 |
|
21 |
2100 |
2000 |
1500 |
2200 |
1700 |
|
22 |
1200 |
1350 |
1500 |
1350 |
2100 |
|
23 |
2000 |
1950 |
1450 |
1700 |
1400 |
|
24 |
1100 |
1200 |
1300 |
1000 |
1900 |
|
25 |
1000 |
1200 |
1300 |
1000 |
2000 |
18
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
Технический редактор – О.А. Прохорович
Отпечатано в издательско-полиграфическом центре
ФГОУ ВПО МичГАУ Подписано в печать 17.11.06. г. Формат 60х84 1/16,
Бумага офсетная № 1. Усл.печ.л. 1,2 Тираж 50 экз. Ризограф
Заказ №
_______________________________________________________________
Мичуринский государственный аграрный университет 393760, Тамбовская обл., г.Мичуринск, ул. Интернациональная, 101,
тел. +7 (47545) 5-26-35 E-mail: mgau@mich.ru
19
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
20
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com