2020-01-14
85
Решение транспортной задачи
Транспортная задача является частным случаем общей задачи линейного программирования. В линейном программировании функция цели и система ограничений заданна линейно.
Транспортная задача может быть решена основным методом линейного программирования – симплекс метода, но для неё разработаны более удобные и эффективные методы, в частности метод потенциала. Алгоритм транспортной задачи был впервые применён для рационализации перевозов груза, поэтому получил название транспортная задача.
Постановка задачи
Имеется m отправителей и n потребителей однородного груза. Запасы грухов у отправителей – ai, потребность в грузе у получателей – bj. Известна стоимость Сij перевозки единицы от каждого отправителя до каждого получателя. Требуется определить оптимальную схему перевозки груза от отправителей к получателям так, чиобы суммарные транспортные расходы были min. Обычно условие задачи записывается в виде таблицы:
| В1 | В2 | Вn | Запасы ai | |
| А1 | С11 X11 | С12 X12 | С1n X1n | a1 |
| А2 | С21 X21 | С22 X22 | С2n X2n | a2 |
| Аm | Сm1 Xm1 | Сm2 Xm2 | Сmn Xmn | am |
| Потребность bj | b1 | b2 | bn | S ai = S bj |
|
|
|
xij – количество груза, перевозимого от ai отправителя к bj потребителю.
При решении транспортной задачи должны выполняться 4 условия:
1. Все запасы грузов должны быть вывезены, т.е. 
i=1…m
2. Все потребности в грузе должны быть удовлетворены, т.е. 
j=1…n.
3. Суммарные транспортные затарты должны быть min, т.е.
F=C11∙X11+ C12∙X12+…+ Cmn∙Xmn ® min
или 
Существуют следующие методы решения задач:
1 Метод приближением условно оптимальными планами.
2 Метод потенциалов.
3 Метод рент.
4 Метод Филкерсона и т.д.
Расстановка поставок методом двойного предпочтения
1 итерация
| В1 | В2 | В3 | B4 | Uj | ||
| А1 | 5 | 4 | 2 45 | 2 45 | 90 | 0 |
| А2 | 3 80 | 6 | 3 | 1 15 | 95 | -1 |
| А3 | 1 10 | 2 90 | 3 | 7 | 100 | -3 |
| Фикт. | 0 | 0 -3 | 0 135 | 0 | 135 | -2 |
| 90 | 90 | 180 | 60 | |||
| Vi | 4 | 5 | 2 | 2 |
Fmin=90+90+240+15+10+180=625
2 итерация
| В1 | В2 | В3 | B4 | Uj | ||
| А1 | 5 | 4 | 2 90 | 2 | 90 | 0 |
| А2 | 3 35 | 6 | 3 -1 | 1 60 | 95 | 2 |
| А3 | 1 55 | 2 45 | 3 | 7 | 100 | 0 |
| Фикт. | 0 | 0 45 | 0 90 | 0 | 135 | -2 |
| 90 | 90 | 180 | 60 | |||
| Vi | 1 | 2 | 2 | -1 |
Fmin=180+105+60+55+90=490
Конечная таблица
| В1 | В2 | В3 | B4 | Uj | ||
| А1 | 5 | 4 | 2 90 | 2 | 90 | 0 |
| А2 | 3 | 6 | 3 35 | 1 60 | 95 | 1 |
| А3 | 1 90 | 2 10 | 3 | 7 | 100 | 0 |
| Фикт. | 0 | 0 80 | 0 55 | 0 | 135 | -2 |
| 90 | 90 | 180 | 60 | |||
| Vi | 1 | 2 | 2 | 0 |
Fmin=180+105+60+90+20=455
3.2. Расчёт сетевого графика
Сетевая модель называется сетевым графиком, на котором в определённом порядке показаны все операции по созданию объекта. Векторы или нити на графике – это выполняемые работы. Узлы – это события, т.е. момент начала или окончания ряда работ. Сетевой график в отличие от линейного даёт не только перечень работ, но и взаимосвязь между ними. На основе расчёта графика контролируется ход работ, основное внимание уделяется критическим работам, для остальных рассчитывается резерв времени. В основу построения сети закладывают три понятия: работа, событие, путь.
|
|
|
Основные расчётные параметры – ранние и поздние сроки начала и окончания работы, и резервы времени.
Рассмотрим фрагмент графика.
|
|
|
|
|
|
|
i-j- данная работа
t-j- время данной работы
h-i- предшествующая работа
j-k- последующая работа
tkp- время критического пути
tijPH- раннее начало данной работы
tijPO- раннее окончание данной работы
tijПН- позднее начало работы
tijНО- позднее окончание данной работы
Rij- общий или полный резерв, времени работы
Rij- частный резерв времени работы
Раннее начало исходных работ полагается равное нулю. T1iРН= 0
Раннее окончание любой работы равно сумме её раннего начала и продолжительности.
tijPP= tijPH+ tij
Раннее начало любой работы равно max раннему окончанию предшествующих работ.
tijPH= maxh thPO
max ранее окончание завершающих работ равно критическому времени
maxj tjNPO= tкр.
Позднее окончание завершающих работ - равно критическому времени. Позднее окончание работ. Позднее начало любой работы равно разности её позднего окончания и продолжительности: tijПН = tijНО - tij
Позднее окончание любой работы равно min- му позднему началу последующих работ:
tijНО = mink tjkПН
Все параметры сетевого графика не отрицательны.
Для работ критического пути ранние поздние параметры совпадают.
Полный резерв времени показывает насколько можно увеличить продолжительность данной работы не увеличивая t- критическое.
|
|
Частный или свободный резерв времени показывает, на сколько можно увеличить продолжительность данной работы, не изменяя раннего начало последующих работ.
Частный резерв равен разности раннего начала последующих работ и раннего окончания данной работы.
rij= tjkрн- tijро
riN= tкр- tjNро
rij 
Rij
Все расчёты записываются в таблицу - критический путь.
| Код работы | Длит. работы | Тр.н. | Тр.о. | Тп.н. | Тп.о. | Общ. резерв | Частн. резерв |
| 1-2 | 4 | 0 | 4 | 0 | 4 | 0 | 0 |
| 1-3 | 5 | 0 | 5 | 8 | 13 | 8 | 6 |
| 1-7 | 3 | 0 | 3 | 11 | 14 | 11 | 11 |
| 2-3 | 7 | 4 | 11 | 6 | 13 | 2 | 0 |
| 2-4 | 9 | 4 | 13 | 10 | 19 | 6 | 4 |
| 2-7 | 10 | 4 | 14 | 1 | 14 | 0 | 0 |
| 2-8 | 8 | 4 | 12 | 13 | 21 | 9 | 6 |
| 3-4 | 6 | 11 | 17 | 13 | 19 | 2 | 0 |
| 3-5 | 8 | 11 | 19 | 19 | 27 | 8 | 0 |
| 4-5 | 0 | 17 | 17 | 27 | 27 | 10 | 2 |
| 4-8 | 1 | 17 | 18 | 20 | 21 | 3 | 0 |
| 4-10 | 20 | 17 | 37 | 19 | 39 | 2 | 2 |
| 5-6 | 11 | 19 | 30 | 27 | 38 | 8 | 0 |
| 5-10 | 9 | 19 | 28 | 30 | 39 | 11 | 11 |
| 5-12 | 7 | 19 | 26 | 39 | 46 | 20 | 20 |
| 6-11 | 4 | 30 | 34 | 40 | 44 | 10 | 10 |
| 6-12 | 8 | 30 | 38 | 28 | 46 | 8 | 8 |
| 7-8 | 0 | 14 | 14 | 21 | 21 | 7 | 4 |
| 7-9 | 10 | 14 | 24 | 14 | 24 | 0 | 0 |
| 8-9 | 3 | 18 | 21 | 21 | 24 | 3 | 3 |
| 8-10 | 7 | 18 | 25 | 32 | 39 | 14 | 14 |
| 9-10 | 15 | 24 | 39 | 24 | 39 | 0 | 0 |
| 10-11 | 5 | 39 | 44 | 39 | 44 | 0 | 0 |
| 11-12 | 2 | 44 | 46 | 44 | 46 | 0 | 0 |
Решение
1-2-7-9-10-11-12
Ткрит = 46
Заключение
