Конспект лекций по предмету "Линейное программирование"

Course-Work.ru П.2.4. Решение транспортной задачи , Порядок решения транспортных задач с помощью QSB рассмотрим на следующем примере. Пример. Требуется составить такой план прикрепления трёх...
Узнать цену дипломной по вашей теме


Конспект лекций П.2.4. Решение транспортной задачи

Порядок решения транспортных задач с помощью QSB рассмотрим на следующем примере.

Пример. Требуется составить такой план прикрепления трёх потребителей к трём поставщикам, при котором общая стоимость перевозок будет минимальной. Тарифы перевозки единицы продукции от поставщиков к потребителям, объёмы предложения поставщиков и спроса потребителей заданы в таблице.

Поставщики

Тарифы перевозок

Предложение поставщиков





































Спрос потребителей









Обозначим через xi j – количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю.

Тогда ЭММ:



Здесь предполагается, что суммарное предложение равно суммарному спросу. Такая задача называется закрытой или замкнутой. Если это условие не выполнятся, то задача называется открытой. Для сведения открытой задачи к закрытой вводится или фиктивный поставщик или фиктивный потребитель.

Подготовьте ЭММ задачи для решения на ЭВМ, причём объёмы предложения поставщиков и спроса потребителей должны быть целыми числами, а тарифы перевозок могут быть вещественными. Итак, в нашей задаче: ЦФ на минимум, 3 поставщика, 3 потребителя. Предложение поставщиков: 120, 100 и 80. Спрос потребителей: 90, 90 и 120.

Выберите опцию 3 – Транспортная задача в главном меню системы. На экране появится функциональное меню, идентичное рассмотренному ранее.

В функциональном меню выберите опцию 2- Ввод новой задачи, введите название задачи (например, prim3 ), ответьте на вопросы о задаче. Варианты ответов: ЦФ на минимум, 3 поставщика, 3 потребителя, будем использовать заданные обозначения поставщиков (S1, S2,...Sn) и потребителей (D1, D2,...,Dn). По окончании нажмите клавишу Spacebar .На экране появится шаблон для ввода объёмов предложения поставщиков и спроса потребителей.

Заполните шаблон следующим образом:

постав.:

S1: 120____ S2: 100____ S3: 80___

D1: 90____ D2: 90____ D3: 120___

После нажатия клавиши Spacebar на экране появится шаблон для ввода стоимости перевозок (или прибыли от перевозок).

Введите данные, как показано ниже:





от к

S1: D1: 7____ D2: 6____ D3: 4___

S2 D1: 3____ D2: 8___ D3: 5___

S3 D1: 2____ D2: 3____ D3: 7____

После нажатия Spacebar на экране появится функциональное меню.

В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:

Меню опции <Решение>

пункт

1---- Решение и просмотр начальной таблицы

2---- Решение и просмотр всех таблиц

3---- Решение и просмотр итоговой таблиц

4---- Решение без просмотра таблиц

5---- использовать метод Фогеля

6---- Возврат в функциональное меню

Выбор опции 6 обеспечивает возврат в функциональное меню без решения задачи. При выборе остальных опций задача будет решена. При этом для задач небольшой размерности доступны все режимы, а для больших задач – только опции 4-5.

Для построения начального допустимого плана по умолчанию используется метод северо-западного угла, который можно заменить на метод аппроксимации Фогеля с помощью опция 4.

Для поиска оптимального плана применён метод потенциалов. При этом признаком оптимальности плана является существование таких чисел U(i) и V(j), для которых выполняются условия:

U(i)+V(j)=C(i,j) для xi j > 0;

U(i)+V(j)£C(i,j) для xi j = 0, (*)

где C(i,j) и xi j – стоимость перевозки единицы груза и количество перевозимого груза от i-го поставщика (i = 1...m) j-мц потребителю (j = 1...n).

Выберите опцию 2 – Решение и просмотр всех таблиц. Результаты решения на каждой итерации представлены одинаковыми по форме таблицами.

В первой таблице показан начальный допустимый план прикрепления поставщиков к потребителям (потенциалы U(i) и V(j) полагаются равными нулю, значение ЦФ = 2050).. Переход к следующей таблице осуществляется нажатием любой клавиши, кроме G ,при нажатии которой вычислительный процесс пойдёт без остановки до конца.

В этой таблице вычислены потенциалы по формуле (*). Признак оптимальности плана не выполнен для клетки (S3, D1), а именно U(i)+V(j)=4+7=11 превосходит стоимость перевозки от поставщика S3 к потребителю D1 на 9, что изображено в виде и в этой клетке поставлены две звёздочки (**). Это значит, что в данную клетку следует поместить перевозку, объём которой равен 60 (определяется из цикла (3,1)-(3,3)-(2,3)-(2,2)-(1,2)-(1,1)).

Начальн. решение NWC

SN/DN

D1

D2

D3

предлож.

U(i)

S1



7.000



6.000



4.000

120.00



90.00



30.00







S2



3.000



8.000



5.000

100.00







60.00



40.00



S3



2.000



3.000



7.000

80.00











80.00



спрос V(j)

90.00



90.00



120.00







Минимум значение цф = 2050

На следующей итерации фиксируется перемещение перевозок по циклу, вычисляется текущее значение ЦФ (=1510), определяется клетка (S1, D3), для которой не выполнен признак оптимальности (е(1,3)=–8) и т.д. Процесс поиска оптимального решения заканчивается на четвёртой итерации. После нажатия любой клавиши на экране появляется меню способов представления полученного решения задачи.

Выберите опцию 1 – просмотр итогового решения. На экране появится таблица с результатами решения задачи:

итоговый результат prim3 Стр.: 1

от

к

груз

тариф

от

к

груз

тариф

S1

S1

S1

S2

S2

D1

D2

D3

D1

D2

0.0

10.0

110.0

90.0

0.0

7.000

6.000

4.000

3.000

8.000

S2

S3

S3

S3

D3

D1

D2

D3

10.0

0.0

80.0

0.0

5.000

2.000

3.000

7.000

миним. значение цф = 1060 итерация = 4



После 4 итераций получили оптимальный план, согласно которому от первого поставщика везётся ко второму потребителю 10, к третьему 110, к четвёртому 90; от второго поставщика – в первому потребителю 90; к третьему 10; от третьего поставщика – ко второму потребителю 80.


Не сдавайте скачаную работу преподавателю!
Данную дипломную работу Вы можете использовать как базу для самостоятельного написания выпускного проекта.

Доработать Узнать цену работы по вашей теме

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

 
Пишем работу самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.