Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Пример № 2
На складах фирмы А, расположенных в трех пунктах отправления (порты А1, А2, А3) находится однородный товар, который необходимо по заявкам фирмы В перевезти в четыре ее пункта назначения (порты В1, В2, В3, В4). Перевозки осуществляет некая фирма С, у которой однотипные суда на момент отправки груза будут находиться в пунктах отправления соответственно три, пять и два. В соответствии с заявкой необходимо отправить в пункты назначения фирмы В суда с товаром фирмы А в количестве четыре, два, три и одно соответственно. Расстояния в морских милях между пунктами отправления и пунктами назначения сведены в таблицу № 1.
Составить оптимальный план перевозок товара, обеспечивающий минимальный суммарный расход топлива, при условии, что средний расход топлива на единицу пути при следовании экономической скоростью V = 10 узлов составляет 0.01 ед. топлива.
Таблица № 1
|
Пункты отправления |
Пункты назначения |
|||
|
В1 |
В2 |
В3 |
В4 |
|
|
А1 |
400 |
600 |
800 |
200 |
|
А2 |
400 |
1200 |
500 |
100 |
|
А3 |
800 |
1000 |
600 |
400 |
По условию задачи нам неизвестно число судов направленных из i-го пункта отправления в j-й пункт назначения, обозначим их как неизвестные переменные модели xi,j . Стоимость перевозки груза (расход топлива при переходе одного судна из i-го пункта отправления в j-й пункт назначения) обозначим как ci,j . Тогда общую стоимость перевозки груза можно представить в виде целевой функции:
Число судов, находящихся в i-м пункте отправления на момент отправки обозначим как ai,j, а число судов, необходимых для следования в j-й пункт назначения обозначим как bi,j.
С учетом этих обозначений задача может быть сформулирована следующим образом: найти неизвестные xi,j, обращающие целевую функцию в минимум
при следующих ограничениях:
уравнений, задающих условия решения задачи
и ограничений на переменные
при условии
где ,
Так как в данной транспортной задаче все условия определены, то она представляет собой каноническую формулировки задачи линейного программирования, поэтому ее можно решить аналитическим методом по критерию стоимости.
Составим транспортную таблицу для нахождения начального плана (см. транс. табл. № 1).
Транспортная таблица № 1
|
Пункты отправления |
Пункты назначения |
Ресурсы (предложение) |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 |
3 |
3 |
|||
|
А2 |
1 |
2 |
2 |
5 |
|
|
А3 |
1 |
1 |
2 |
||
|
Заявки (спрос) |
4 |
2 |
3 |
1 |
Определим
Так как , то в дальнейшем в другие элементы данной строки назначения производить нельзя. Следующее назначение производиться на пересечении второй строки и первого столбца:
Так как , то в дальнейшем исключается заполнение первого столбца, а следующее назначение производиться на пересечении второй строки и второго столбца:
Так как , то в дальнейшем исключается заполнение второго столбца, а следующее назначение производиться на пересечении второй строки и третьего столбца:
Так как , то в дальнейшем в другие элементы данной строки назначения производить нельзя. Следующее назначение производиться на пересечении третьей строки и третьего столбца:
Так как , то в дальнейшем исключается заполнение третьего столбца, а следующее назначение производиться на пересечении третьей строки и четвертого столбца:
Так как , то в дальнейшем исключается заполнение третьей строки.
Для контроля проверим:
- баланс условия - выполнения заявок по распределению судов из пункта отправления в пункты назначения – выполнен;
- перевозки - положительны.
Полученный план удовлетворяет условиям ТЗ и может быть принят в качестве начального решения.
Введем следующие обозначения:
- ui, – потенциал пункта отправления (плата за перевозку груза фирме С фирмой А);
- v,j – потенциал пункта назначения (плата за перевозку груза фирме С фирмой В).
С учетом этих обозначений двойственная задача линейного программирования может быть сформулирована следующим образом:
Найти неизвестные ui, и v,j, обращающие целевую функцию в максимум:
при условии
где ,
Рассчитаем стоимости перевозки грузов при переходе одного судна из любого пункта отправления в любой пункт назначения, отразив их в таблице № 2.
где Si,j - расстояния между пунктами отправления и пунктами назначения;
- средний расход топлива на единицу пути при следовании экономической скоростью.
Таблица № 2 – Стоимость перевозки грузов
|
Пункты отправления |
Пункты назначения |
|||
|
В1 |
В2 |
В3 |
В4 |
|
|
А1 |
4 |
6 |
8 |
2 |
|
А2 |
4 |
12 |
5 |
1 |
|
А3 |
8 |
10 |
6 |
4 |
Далее составим транспортную таблицу № 2, отразив в ней первоначальный план перевозки грузов и в правом верхнем углу ячеек стоимости перевозки грузов при переходе одного судна из любого пункта отправления в любой пункт назначения.
Зададимся значением и последовательно определим все потенциалы для положительных перевозок, записав их в транспортную таблицу.
После нахождения потенциалов пунктов отправления и назначения последовательно найдем значения псевдостоимости, записав их в левый верхний угол ячеек транспортной таблицы.
Так как по условию для положительных перевозок стоимость и псевдостоимость совпадают, то можно сразу записать значения псевдостоимости.
Транспортная таблица № 2
|
Пункты отправления |
Пункты назначения |
Ресурсы |
Потенциал ПО |
|||
|
В1 |
В2 |
В3 |
В4 |
|||
|
А1 |
4 3 - 4 |
12 6 |
5 8 |
3 2 |
3 |
- 4 |
|
А2 |
4 1+ 4 |
12 2- 12 |
5 2 5 |
3 1 |
5 |
- 4 |
|
А3 |
5 8 |
13 10 |
6 1 6 |
4 1 4 |
2 |
- 5 |
|
Заявки |
4 |
2 |
3 |
1 |
С = 60 ед. топл. |
|
|
Потенциал ПН |
0 |
8 |
1 |
-1 |
Ввиду того, что для какой-либо нулевой перевозки грузов псевдостоимость выше стоимости, т.е. , то начальный план перевозки грузов, не является оптимальным.
Введем новую переменную на ту коммуникацию, для которой разность между псевдостоимостью и стоимостью наибольшая. Наибольшая положительная разность соответствует ячейке А1B2 таблицы, следовательно новое назначение и производиться в эту ячейку. Сбалансируем условия задачи путем уменьшения объема перевозок. Для определения числа воспользуемся тем, что . Исходя из этого условия:
Подставив в транспортную таблицу № 2 значения , получим новый улучшенный план перевозок груза (см. транс. табл. № 3).
Транспортная таблица № 3
|
Пункты отправления |
Пункты назначения |
Ресурсы |
Потенциал ПО |
|||
|
В1 |
В2 |
В3 |
В4 |
|||
|
А1 |
4 1 4 |
6 2 6 |
5 8 |
3 2 |
3 |
- 4 |
|
А2 |
4 3 4 |
6 12 |
5 2 - 5 |
3 1 |
5 |
- 4 |
|
А3 |
5 8 |
7 10 |
6 1+ 6 |
4 1 - 4 |
2 |
- 5 |
|
Заявки |
4 |
2 |
3 |
1 |
С = 48 ед. топл. |
|
|
Потенциал ПН |
0 |
2 |
1 |
-1 |
Проверка нового плана перевозок груза на оптимальность и переход к улучшенному плану производиться аналогичным образом. Так как полученный план не является оптимальным, перейдем к составлению следующего улучшенного плана перевозок грузов.
Подставив в транспортную таблицу № 3 значения , получим новый улучшенный план перевозок груза (см. транс. табл. № 4).
Транспортная таблица № 4
|
Пункты отправления |
Пункты назначения |
Ресурсы |
Потенциал ПО |
|||
|
В1 |
В2 |
В3 |
В4 |
|||
|
А1 |
4 1 4 |
2 2 2 |
5 8 |
1 2 |
3 |
- 4 |
|
А2 |
4 3 4 |
2 12 |
5 1 5 |
1 1 1 |
5 |
- 4 |
|
А3 |
5 8 |
7 10 |
6 2 6 |
2 4 |
2 |
- 5 |
|
Заявки |
4 |
2 |
3 |
1 |
С = 46 ед. топл. |
|
|
Потенциал ПН |
0 |
2 |
1 |
-3 |
В последнем плане все псевдостоимости ненулевых перевозок меньше стоимости этих перевозок, следовательно, этот план перевозок грузов является оптимальным.
Для нахождения стоимости перевозок, соответствующей данному плану, необходимо умножить значения положительных перевозок на соответствующую им стоимость и полученные результаты сложить.
Если из ПО А1 отправить одно судно в ПН В1 и два судна в ПН В2, из ПО А2 отправить три судна в ПН В1, одно судно в ПН В3 и одно судно в ПН В4, а из ПО А3 отправить два судна в ПН В3, то данный план перевозок грузов будет эффективным, т.к. дает минимальный расход топлива, равный 46 ед.