Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Модификации транспортной задачи

Существуют различные модификации транспортной задачи, которые также могут быть решены методом потенциалов. Рассмотрим некоторые из них.

Задача с частично закрепленными связями – это транспортная задача, в которой заданы некоторые обязательные объемы поставок от конкретного поставщика к конкретному потребителю. Например, требуется обязательно хотя бы 10 холодильных установок перевезти из Стокгольма в Лион.

Такая задача сводится к обычной за счет уменьшения величин запасов и потребностей на заранее заданные объемы перевозки. Например, в задаче о холодильных установках следовало бы уменьшить запасы Стокгольма и потребности Лиона на 10 установок (a1 = 120 – 10 = 110, b2 = 90 – 10 = 80). После этого задачу можно решать методом потенциалов, но после того, как оптимальный план будет получен, перевозки из Стокгольма в Лион (x12) следует увеличить на эти 10 холодильных установок.

Задача с частично запрещенными связями – это транспортная задача, в которой перевозки по каким-либо направлениям запрещены. Например, нельзя везти холодильные установки из Стокгольма в Лион.

Такая задача сводится к обычной путем установления стоимости перевозок cij для запрещенной связи на очень высоком уровне (в масштабах модели). Для данного примера следует приравнять стоимость перевозки одной установки из Стокгольма в Лион вместо восьми, например, к тысяче
12 = 1000). Поскольку в задаче о холодильных установках цены на перевозку измеряются в единицах и десятках фунтов стерлингов, число 1000 будет очень большим в масштабах модели. Однако, если бы цены измерялись в сотнях и тысячах, следовало бы выбрать другое число (например, 100000).

Порядок выполнения работы

1 Изучить методические указания к лабораторной работе.

2 Ответить на контрольные вопросы.

3 Самостоятельно построить открытую модель транспортной задачи и решить ее методом потенциалов (начать решение с опорного плана, построенного МСЗУ). После преобразования в закрытую в модели должно быть 4 поставщика и 5 потребителей (включая дополнительных).

4 При решении задачи с помощью ППП «Система деловых задач»* сохранить данные задачи в файле с именем, составленным из своих инициалов (в папке QSB). По окончании занятия перенести его в свою папку.

5 Проанализировать ход решения, рассмотрев его по итерациям.

6 Построить опорный план МАФ и проанализировать результаты использования этого метода.

7 При использовании ППП «Система деловых задач» изучить возможности корректировки исходных данных – удаление и ввод пунктов отправления и назначения, изменение их мощностей (запасов и потребностей), изменение коэффициентов целевой функции. При этом должны быть рассмотрены как открытая, так и закрытая модели транспортной задачи.

ОФОРМЛЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ

Отчет по лабораторной работе должен включать:

а) формулировку условий транспортной задачи в виде текста;

б) условия открытой и закрытой моделей транспортной задачи в виде задач линейного программирования;

в) опорные планы, построенные МСЗУ и МАФ;

г) ход решения задачи методом потенциалов;

д) результаты решения задачи (ответ).

КОНТРОЛЬНЫЕ ВОПРОСЫ

1 Как ставится транспортная задача?

2 При каких условиях разрешима транспортная задача?

3 Расскажите об открытой и закрытой моделях транспортной задачи.

4 В чем заключается особенность опорного плана транспортной задачи?

5 В чем заключается метод северо-западного угла построения опорного плана транспортной задачи?

6 В чем заключается метод наименьшей стоимости построения опорного плана транспортной задачи?

7 В чем заключается метод аппроксимации Фогеля?

8 Сформулируйте теоремы об изменении плана и о критерии оптимальности транспортной задачи.

9 В чем заключается алгоритм метода потенциалов?

10 В каком случае оптимальный план транспортной задачи будет целочисленным?

 


ЛАБОРАТОРНАЯ РАБОТА 2
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ
С ПОМОЩЬЮ НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ»
В MICROSOFT EXCEL

ЦЕЛЬ РАБОТЫ

Изучить особенности применения надстройки «Поиск решения» к решению транспортной задачи, а также интерпретацию отчетов, которые предоставляет пользователю эта программа.

ПРИБОРЫ И МАТЕРИАЛЫ

Для выполнения лабораторной работы необходим персональный компьютер, функционирующий под управлением операционной системы семейства Windows. Программное обеспечение экономических расчетов – универсальный пакет Microsoft Excel (средства электронной таблицы, «Мастер функций») включая надстройку «Поиск решения».

ОПИСАНИЕ РАБОТЫ

3.1 Постановка транспортной задачи
для «Поиска решения»

 

Так как транспортная задача представляет собой задачу линейного программирования, она может быть решена симплекс-методом, который, в частности, реализован в надстройке «Поиск решения» универсального пакета Excel [3, 15].

Поставим для «Поиска решения» открытую модель задачи о холодильных установках:

min (25x11 + 14x12 + 18x21 + 8x22 + 12x31 + 6x32)

x11 + x12 120

x21 + x22 40

x31 + x32 90

x11 + x21+ x31 150

x12 + x22 + x32 90

Подготовим данные в Excel следующим образом (слева и вверху указаны номера строк и столбцов электронной таблицы):


 

  A B C D
   
   
   
  в Лейпциг, шт. в Лион, шт.  
Количество установок, перевозимых из Стокгольма 0,00 0,00  
Количество установок, перевозимых из Триеста 0,00 0,00  
Количество установок, перевозимых из Руана 0,00 0,00  
  Стокгольме Триесте Руане
Ограничение по выпуску продукции в 0,00 0,00 0,00
 
  Лейпциг Лион  
Ограничение по потребности центра сбыта 0,00 0,00  
   
  ф.ст.    
Общая стоимость перевозки,    

Здесь в диапазон ячеек В1:С3 введены коэффициенты целевой функции (строки соответствуют центрам производства, а столбцы – центрам сбыта).

В диапазоне В5:С7 находятся переменные. Так как это изменяемые ячейки, в них можно ничего не вводить (по умолчанию они равны нулю) или ввести любые числа, например, нули. Не следует только вводить в них текстовую информацию или присваивать им формат, например, текста или даты, с которым программа не сможет производить вычисления. Введенный слева и сверху текст предназначен для удобства чтения отчетов о решении. Например, переменную, которая находятся в ячейке В5, «Поиск решения» назовет «Количество установок, перевозимых из Стокгольма в Лейпциг, шт.», составив это название из текста, ближайшего к этой ячейке слева и сверху. Так и должна называться переменная x11.

В В9:D9 находятся формулы для левых частей первых трех ограничений. Чтобы их ввести, рекомендуется в любую ячейку ввести формулу =СУММ(B5:C5) (т.е. x11 + x12), которую затем скопировать протаскиванием на 2 строки вниз (при протаскивании номера строк изменятся). Полученные три формулы перенести* в нужные ячейки.

В строке 10 введены объемы производства холодильных установок, а в строке 13 – объема сбыта.

В В12 находится левая часть четвертого ограничения - формула =СУММ(B5:B7), которая скопирована в С12 (при этом получают левую часть пятого ограничения).

Имена ограничений будут образованы так же, как и имена переменных. Например, первое ограничение (ячейка В9) получит имя: «Ограничение по выпуску продукции в Стокгольме».

Ячейка В15 – целевая, и получит имя «Общая стоимость перевозки, ф.ст.». В нее введена формула целевой функции: =СУММПРОИЗВ(B1:C3;B5:C7).

 
 

В «Поиск решения» вводится следующая модель (рисунок 3):

Рисунок 3 – Модель «Поиска решения»

 

В «Параметрах» «Поиска решения» необходимо поставить флажки «Линейная модель» и «Неотрицательные значения». Ограничения целочисленности вводить не нужно. В данном случае при решении задачи симплекс-методом также всегда будет получено целочисленное решение, так как коэффициенты в ограничениях – нули и единицы (при преобразовании системы методом Гаусса ограничения будут умножаться или делиться на 1, и свободный член никогда не станет дробным).

В результате выполнения поиска в изменяемых ячейках появятся значения, соответствующие оптимальным перевозкам, а в целевой ячейке – наименьшие затраты.

Кроме того, программа предоставляет пользователю возможность ознакомиться с тремя типами отчетов о решении задачи.

 

Последнее изменение этой страницы: 2016-08-11

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...