Материал: 4758
Задача 1(песчаный карьер).
Имеется три песчаных карьера, из которых доставляется песок на 5 участков ремонта автодорог. Цены перевозок одной тонны песка, величины потребностей и запасы песка в карьерах даны в табл.1.
Таблица 1 Цены перевозок, величины потребностей и запасы песка в карьерах
|
Участки работ |
|
|
|
|||
Карьеры |
В1 |
|
В2 |
В |
В |
В |
Предложение |
|
|
З |
4 |
5 |
|
||
|
|
|
|
|
|||
А1 |
3 |
|
3 |
5 |
3 |
1 |
500 |
А2 |
4 |
|
3 |
2 |
4 |
5 |
300 |
АЗ |
3 |
|
7 |
5 |
4 |
1 |
100 |
Потребности |
150 |
|
35 |
2 |
1 |
1 |
|
0 |
|
00 |
00 |
00 |
|
||
|
|
|
|
||||
Требуется:
I) Предложить план перевозок песка на участки ремонта автодорог, который обеспечивает минимальные совокупные транспортные издержки.
II)Что произойдет с оптимальным планом, если изменятся условия перевозок:
а) появится запрет на перевозки от первого карьера до второго участка работ;
б) по этой коммуникации будет ограничен объем перевозок 3 тоннами?
I ) Решение: Составим экономико-математическую модель задачи.
В данном случае запасы песка в трех пунктах отправления (карьерах) в сумме равны потребностям участков работ. Таким образом, данная транспортная задача закрытого типа.
На практике достаточно редко суммарный запас поставщиков и общее количество груза, заявленное потребителями, совпадают. Как правило, они различаются. Это – так называемая несбалансированная, или открытая ТЗ.
Ввод условий задачи состоит из следующих основных этапов.
1.Создание формы для решения задачи.
2.Ввод граничных условий.
3.Ввод исходных данных.
4.Назначение целевой функции.
5.Ввод зависимостей из математической модели. 6. Ввод ограничений.
7.Просмотр результатов и печать отчета. Рассмотрим более подробно каждый из этих этапов.
1.Создание формы для решения задачи предполагает создание
матрицы перевозок.
Для этого необходимо выполнить резервирование изменяемых ячеек: в блок ячеек С2:G4 введем «1».
Таким образом, резервируется место, где после решения задачи будет находиться распределение поставок, обеспечивающее минимальные затраты на перевозку песка.
2. Ввод граничных условий.
Введем условия реализации мощностей поставщиков (карьеров), т.е.
n |
|
|
|
|
ai xij , |
где ai - мощность |
i -го поставщика; |
xij |
— |
j 1 |
|
|
|
|
объем поставки груза от |
i -го поставщика к |
j -му потребителю; |
n |
— |
количество потребителей. |
|
|
|
|
Для этого необходимо выполнить следующие операции:
-установить курсор в ячейку В2;
-щелкнуть знак « » на панели инструментов Excel;
-выделить необходимые для суммирования ячейки C2:G2;
-нажать ENTER - подтверждение ввода формулы для суммирования. Аналогичные действия выполним для ячеек В3, В4, т.е. введем условия реализации мощностей всех поставщиков (для всех строк).
Введем условия удовлетворения запросов потребителей, т.е.
m |
|
b j xij , |
где b - мощность j -го потребителя; m — |
i 1 |
|
количество поставщиков.
Для этого необходимо выполнить следующие операции:
-установить курсор в ячейку С5;
-щелкнуть знак « » на панели инструментов Excel. При этом
автоматически выделяется весь столбец C2:C4; - нажать ENTER - подтверждение суммирования показателей выделенного столбца. Последовательность этих действий выполнить для ячеек D5-G5.
Таким образом, введены ограничения для всех поставщиков и всех потребителей.
3. Ввод исходных данных.
Введем мощности трех карьеров (ячейки В10:В12), потребности 5 участков (С9:G9), а также удельные затраты по доставке песка от конкретного карьера к участку (блок С10:G12) (рис. 1).
Рис. 1. Мощности трех карьеров и удельные затраты по доставке песка.
4. Назначение целевой функции.
Для вычисления значения целевой функции, соответствующей минимальным суммарным затратам на доставку груза, необходимо зарезервировать ячейку и ввести формулу для ее вычисления:
n m |
|
F Cij xij , |
где Cij - стоимость доставки одной тонны песка |
j 1i 1 |
|
от i -го карьера |
|
к j -му заказчику; xij — объем поставки (число тонн песка) от i -го карьера к j -му заказчику.
Для этого нужно:
-установить курсор в ячейку С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 денежных единиц, будет обеспечен при следующем плане поставок:
от первого карьера нужно отправить 150т, 250т и 100т песка на участки
В1, В2 и В4 соответственно;
от второго карьера нужно отправить 100т и 200т песка на участки В2 и В3 соответственно;
от третьего карьера нужно отправить 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.Как находилась целевая функция?