Тема работы: Формулировка транспортной задачи и построение ее математической модели. Понятие открытой и закрытой транспортной задачи и ее математическая модель.
Цель работы: Знакомство с методикой формулировки и решения задач математического программирования с использованием процедуры Поиск решения табличного процессора Excel.
Содержание работы и порядок ее выполнения
Лабораторная работа включает в себя три варианта задач составления оптимального по стоимости плана перевозок и рассчитана на 6 часов лабораторных занятий. Условия задач выдаются студентам преподавателем, руководящим лабораторными занятиями. Недостающие знания студент восполняет во внеаудиторное время, изучая необходимую литературу.
На занятиях студент знакомится с содержанием работы, составляет по полученным исходным данным математическую модель первого варианта задач, по построенной математической модели задачи с помощью процедуры «Поиск решения» табличного процессора Excel находит оптимальный план перевозок. Методика использования процедуры «Поиск решения» описана в лабораторной работе № 5.
Затем студент отчитывается по теоретической части лабораторной работы, предоставляет отчет о работе преподавателю и защищает полученные результаты. После чего приступает к выполнению второго и третьего вариантов задач.
Формулировка транспортной задачи и построение ее математической модели
Транспортная задача (ТЗ) является частным случаем ЗЛП и формулируется следующим образом: пусть имеются т пунктов отправления (ПО) А1, А2,..., Ат, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2,..., ат единиц. Имеются n пунктов назначения (ПН), В1, В2,..., Вn, подавших соответственно заявки на b1, b2,..., bп единиц груза.
Задача 1(песчаный карьер). Имеется три песчаных карьера, из которых доставляется песок на 5 участков ремонта автодорог. Цены перевозок одной тонны песка, величины потребностей и запасы песка в карьерах даны в табл.1.
Таблица 1
Цены перевозок, величины потребностей и запасы песка в карьерах
| Карьеры | Участки работ | Предложение | ||||
| В1 | В2 | ВЗ | В4 | В5 | ||
| А1 | ||||||
| А2 | ||||||
| АЗ | ||||||
| Потребности |
Требуется:
I) Предложить план перевозок песка на участки ремонта автодорог, который обеспечивает минимальные совокупные транспортные издержки.
II) Что произойдет с оптимальным планом, если изменятся условия перевозок:
а) появится запрет на перевозки от первого карьера до второго участка работ;
б) по этой коммуникации будет ограничен объем перевозок 3 тоннами?
I) Решение: Составим экономико-математическую модель задачи.
В данном случае запасы песка в трех пунктах отправления (карьерах) в сумме равны потребностям участков работ. Таким образом, данная транспортная задача закрытого типа.
На практике достаточно редко суммарный запас поставщиков и общее количество груза, заявленное потребителями, совпадают. Как правило, они различаются. Это – так называемая несбалансированная, или открытая ТЗ.
Ввод условий задачи состоит из следующих основных этапов.
1. Создание формы для решения задачи.
2. Ввод граничных условий.
3. Ввод исходных данных.
4. Назначение целевой функции.
5. Ввод зависимостей из математической модели. 6. Ввод ограничений.
7. Просмотр результатов и печать отчета.
Рассмотрим более подробно каждый из этих этапов.
1. Создание формы для решения задачи предполагает создание матрицы перевозок.
Для этого необходимо выполнить резервирование изменяемых ячеек: в блок ячеек С2:G4 введем «1».
Таким образом, резервируется место, где после решения задачи будет находиться распределение поставок, обеспечивающее минимальные затраты на перевозку песка.
2. Ввод граничных условий.
Введем условия реализации мощностей поставщиков (карьеров), т.е.
где 
- мощность 
-го поставщика; 
— объем поставки груза от -го поставщика к 
-му потребителю; 
— количество потребителей.
Для этого необходимо выполнить следующие операции:
- установить курсор в ячейку В2;
- щелкнуть знак «
» на панели инструментов Excel;
- выделить необходимые для суммирования ячейки C2:G2;
- нажать ENTER - подтверждение ввода формулы для суммирования.
Аналогичные действия выполним для ячеек В3, В4, т.е. введем условия реализации мощностей всех поставщиков (для всех строк).
Введем условия удовлетворения запросов потребителей, т.е.
где 
- мощность -го потребителя; 
— количество поставщиков.
Для этого необходимо выполнить следующие операции:
- установить курсор в ячейку С5;
- щелкнуть знак « » на панели инструментов Excel. При этом автоматически выделяется весь столбец C2:C4; - нажать ENTER - подтверждение суммирования показателей выделенного столбца.
Последовательность этих действий выполнить для ячеек D5-G5.
Таким образом, введены ограничения для всех поставщиков и всех потребителей.
3. Ввод исходных данных.
Введем мощности трех карьеров (ячейки В10:В12), потребности 5 участков (С9:G9), а также удельные затраты по доставке песка от конкретного карьера к участку (блок С10:G12) (рис. 1).
Рис. 1. Мощности трех карьеров и удельные затраты по доставке песка.
4. Назначение целевой функции.
Для вычисления значения целевой функции, соответствующей минимальным суммарным затратам на доставку груза, необходимо зарезервировать ячейку и ввести формулу для ее вычисления:
где 
- стоимость доставки одной тонны песка от -го карьера
к -му заказчику; — объем поставки (число тонн песка) от -го карьера к -му заказчику.
Для этого нужно:
- установить курсор в ячейку С13. В данную ячейку будет помещаться значение целевой функции после решения задачи;
- на панели инструментов нажать кнопку Мастер функций. В диалоговом окне Мастер функций выбрать категорию Математические и функцию СУММПРОИЗВ;
- в окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией.
В задаче целевая функция представляет собой произведение удельных затрат на доставку груза (расположенных в блоке ячеек С10:G12) и объемов поставок для каждого участка (содержимое ячеек С2:G4). Для этого:
- в поле Массив 1 указать адреса С10:G12;
- в поле Массив 2 указать адреса С2:G4;
- подтвердить окончание ввода адресов массивов. В поле ячейки С13 появится некоторое числовое значение, равное произведению единичных поставок на удельные коэффициенты затрат по доставке грузов (число 53 в данной задаче, рис. 1).
5. Ввод зависимостей и ограничений из математической модели.
Выполним команду меню Сервис \ Поиск решения. В диалоговом окне Поиск решения нужно:
- назначить целевую ячейку – в данном случае С13;
- ввести направление целевой функции – Минимальному значению;
- в строке Изменяя ячейки ввести диапазон С2:G4 (адреса искомых переменных);
- ввести ограничения, для этого нажать на кнопку Добавить и ввести данные в диалоговое окно Добавление ограничения;
В результате диалоговое окно Поиск решения выглядит следующим образом (рис.2):
Рис. 2. Диалоговое окно Поиск решения
В диалоговом окне Поиск решения нужно нажать на кнопку Параметры и в диалоговом окне Параметры поиска решения установить флажки в окнах Линейная модель и Неотрицательные значения. После этого нужно нажать на кнопку Выполнить.
6. Просмотр результатов и печать отчета.
После выполнения всех вышеуказанных действий на экран выводится окно Результаты поиска решения.
- В окне Тип отчета нужно выбрать интересующий вид отчета и нажать ОК.
- Внизу страницы экрана содержится сообщение Отчет по результатам. Щелкнуть на этом сообщении, на экран выводятся результаты решения задачи, которые можно распечатать.
В матрице перевозок содержатся оптимальные объемы поставок грузов от карьерам к участкам дорог, дающие минимум затрат на доставку. Значение целевой функции содержится в ячейке С13 и для конкретной задачи равно 2300 (рис. 3).
Из вышеизложенного можно сделать следующий вывод:
минимум затрат на доставку песка, равный 2300 денежных единиц, будет обеспечен при следующем плане поставок:
s от первого карьера нужно отправить 150т, 250т и 100т песка на участки В1, В2 и В4 соответственно;
s от второго карьера нужно отправить 100т и 200т песка на участки В2 и В3 соответственно;
s от третьего карьера нужно отправить 100т песка на участок В5.
Рис. 3. Значение целевой функции.
II) а) Определим, как изменится план перевозок, если ввести запрет на перевозки от первого карьера до второго участка работ. Для этого присвоим значению D10 достаточно большое число, т.е. высокую стоимость перевозки, например, D10=1000. Выполним команду меню Сервис \ Поиск решения. Результат поиска решения представлен на рис. 4.
Рис. 4. Результат поиска решения (1 изменение).
Значение целевой функции на этом плане составило 3100 ед., т.е. на 800 ден. ед. больше, чем при оптимальном плане.
б) Определим, как изменится план перевозок, если объем перевозок от первого карьера до второго участка работ будет ограничен 3 тоннами. Выполним команду меню Сервис \ Поиск решения. В диалоговом окне Поиск решения добавим ограничение D2<=3. Результат поиска решения представлен на рис. 5.
Рис. 5. Результат поиска решения (2 изменение).
Значение целевой функции на этом плане составило 3088 ед., т.е. на 788 ден. ед. больше, чем при оптимальном плане.
Контрольные вопросы:
1. В чем состоит особенность ТЗ как частного случая 3ЛП?
2. Что называется перевозками и планом перевозок в ТЗ?
3. Чему соответствует число уравнений ТЗ и каково число независимых уравнений?
4. Что такое базисные и свободные переменные ЗЛП? Что такое несбалансированная или открытая ТЗ?
5. Как находилась целевая функция?
6. На основании чего делаются выводы в изменениях условий?
Задача 2 (дальнобойщик). Требуется распределить автомобили трех типов по транспортным линиям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех линий соответственно не менее 300, 200, 900 и 600 т. груза.
Ниже в табл. 2,3 приведены исходные данные.
Таблица 2
Зависимость числа рейсов от типа автомобиля
| Тип автомобиля | Число автомобилей этого типа | Число рейсов в месяц автомобилем одного типа по линиям: | |||
Таблица 3
Зависимость эксплуатационных расходов от типа автомобиля
| Тип автомобиля | Эксплуатационные расходы на один рейс по данному маршруту, долл. | |||
Необходимо так распределить автомобили по линиям, чтобы суммарные эксплуатационные расходы были минимальны.