Реферат Курсовая Конспект
П.2.4. Решение транспортной задачи - Лекция, раздел Программирование, Закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению задач линейного программирования Порядок Решения Транспортных Задач С Помощью Qsb Рассмотрим На Следующем Прим...
|
Порядок решения транспортных задач с помощью 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.
– Конец работы –
Эта тема принадлежит разделу:
На сайте allrefs.net читайте: - закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению задач линейного программирования;...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: П.2.4. Решение транспортной задачи
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов