Пример 3. Транспортная задача с закрытой моделью
Определить план доставки грузов от поставщиков потребителям при условии, что суммарная стоимость всех перевозок будет минимальной. Потребности потребителей и запасы груза на складах поставщиков приведены в таблице 17.
Таблица 17
| Стоимость перевозки | Запасы на складе | ||||
| Потребитель 1 | Потребитель 2 | Потребитель 3 | Потребитель 4 | ||
| Поставщик 1 | |||||
| Поставщик 2 | |||||
| Поставщик 3 | |||||
| Потребность |
Целевая функция задает общую стоимость перевозок
F(x) =2х11 +3х12 +5х13+4х14+3х21+2х22+4х23+1х24+4х31 +3х32 +2х33+6х34
F(x) ® min
Создаем на Листе Excel таблицу с исходными числовыми данными и рабочую таблицу с изменяемыми ячейками, в которые будут записываться искомые результаты плана перевозок (рис.1).
Заполняем таблицу «План доставки» формулами, необходимыми для создания ограничений:
1. Ограничения на запасы – в ячейку F 11 вводим =СУММ(В 11: Е 11). Затем копируем эту формулу в ячейки F 12: F 13.
2. Ограничения на потребности – в ячейку В 14 ведите =СУММ(В 11: В 13) и скопируйте её в ячейки С 14: Е 14.
3. Общие суммы запасов на складе – в ячейку G 14 введите =СУММ(G 11: G 13).
4. Общая сумма потребностей — в ячейку F 15 вводим =СУММ(В 15: Е 15).
5. В ячейку G 15 введите логическую формулу для контроля общих сумм: =ЕСЛИ(F 15= G 14 .²совпадает² .²не совпадает²).
6. В ячейку G 16 запишите формулу для целевой функции =СУММПРОИЗВ(В 3: Е 5 . В 11: Е 13).
Результат выполнения пунктов 1-6 в числовом режиме показан на рис. 1.
Рис. 1. Фрагмент рабочего листа в числовом режиме
Для поиска оптимального набора значений параметров плана доставки, который соответствует минимальному значению целевой функции (общей стоимостью всех перевозок), следует воспользоваться надстройкой Поиск решения в меню Сервис. В появившемся окне (рис. 2) устанавливаем целевую ячейку G 16, выбираем вариант оптимизации – минимизация, водим адреса изменяемых ячеек и ограничения. Для ввода ограничений используем кнопку Добавить. Кнопки Изменить и Удалить служат соответственно для изменения или удаления помеченного ограничения.
Рис. 2. Окно «Поиск решения»
Кнопка Предположить служит для автоматического выбора изменяемых ячеек. Далее нажимаем кнопку Параметры и в появившемся окне устанавливаем флажки Линейная модель и Неотрицательные значения. Остальные значения можно оставить без изменения. Нажимаем кнопку ОК. Для решения задачи в окне Поиск решения нажимаем кнопку Выполнить. Полученный результат представлен на рис. 3.
Рис. 3. Результат выполнения поиска решения
После нахождения решения появляется диалоговое окно для выбора типа отчета (рис. 4). Выберите все три отчета и сохраните полученный результат как сценарий с именем «Закрытая модель». Отчеты появляются на отдельных листах книги Excel. При несовместной системе ограничений задачи в диалоговом окне появится сообщение «Поиск не может найти подходящего решения». При неограниченности целевой функции в заданном направлении в диалоговом окне появится сообщение «Значения целевой ячейки не сходятся».
Р и с. 4. Диалоговое окно для выбора типа отчета
Полученное решение оптимально, но может быть не единственным. Полученные отчеты позволяют найти другие возможные решения.
Отчет Результаты состоит из трех таблиц и имеет следующий вид (рис. 5):
Рис. 5. Отчет по результатам
В первой таблице указано оптимальное значение целевой функции, во второй – значения переменных, в третьей – оптимальные объемы доставки, их статус и допустимое снижение объемов доставки без изменения оптимального решения. Фактически вся это информация уже содержится в итоговой таблице.
Отчет Устойчивость содержит две таблицы (рис. 6).
Первая из этих таблиц «Изменяемые ячейки» содержит диапазоны изменения коэффициентов целевой функции, в которых не происходит изменения оптимального решения. Здесь приведен также нормированный градиент, указывающий, на сколько изменится целевая функция, если значение в данной ячейке увеличится на единицу. Для транспортной задачи нормированный коэффициент равен разности тарифа и косвенного тарифа для данной ячейки. Косвенный тариф определяется как сумма потенциалов свободных ячеек. Если все оценки свободных ячеек ³0, то такой план улучшить нельзя, поскольку увеличение значения в любой ячейке приведет к увеличению целевой функции. Наличие оценки £0 в какой-то свободной ячейке укажет на неоптимальность плана. Чем больше значение оценки, тем менее перспективна данная ячейка для включения её в план перевозок.
Рис. 6. Отчет по устойчивости
Во второй таблице «Ограничения» приводятся теневые цены ресурсов и диапазоны изменения объемов доставки, в которых теневые цены остаются неизменными. Значения 1E+30, приведенные в таблице, означают возможность бесконечного увеличения правых частей соответствующих ограничений без изменения теневых цен.
Отчет Пределы содержит две таблицы (рис. 7).
Рис. 7. Отчет по пределам
В первой указано значение целевой функции. А во второй приведен список влияющих ячеек, их значений, а также нижних и верхних пределов. Для транспортной задачи с закрытой моделью нижние и верхние пределы совпадают.
Пример 4. Транспортная задача с отрытой моделью.
В моделях с открытой моделью запасы поставщиков не равны потребностям потребителей.
Пусть запасы поставщиков больше потребностей потребителей (таблица 18).
Таблица 18
| Поставщики | Запасы на складе |
| Поставщик 1 | |
| Поставщик 2 | |
| Поставщик 3 |
На Лист Excel с закрытой моделью удалите из плана доставки полученные результаты и введите изменения в столбце «Запасы на складе» согласно таблице 18. Изменится общая сумма запасов на складе и в ячейке G 15 появится сообщение «не совпадает». Это означает, что не все запасы будут израсходованы. В диалоговом окне Поиск решения измените одно из ограничений (рис. 8), где неравенство $ F $11:$ F $13< .=$ G $11:$ G $13 означает условие неполного распределения запасов.
Рис. 8. Заполнение диалогового окна Поиск решения
Для решения задачи в окне Поиск решения нажимаем кнопку Выполнить. Полученный результат представлен на рис. 9.
Рис. 9. Результаты поиска решения
Сохраните результат выполнения поиска решения при новых условиях в виде сценария с именем «Открытая модель 1».
Пример 5. Пусть запасы поставщиков меньше потребностей потребителей (таблица 19).
Таблица 19
| Потребители | Потребности |
| Потребитель 1 | |
| Потребитель 2 | |
| Потребитель 3 | |
| Потребитель 4 |
На Лист Excel с закрытой моделью примера 3 удалите из плана доставки полученные результаты и введите изменения в исходные данные согласно таблице 19. Изменится общая сумма запасов на складе (90) и потребностей (105). Значение ячейки G 15 «не совпадает».
Выполните поиск решения в новых условиях, изменив ограничения (рис. 10). Выражение $ B $14:$ E $14< .=$ B $15:$ E $15 означает условие неполного удовлетворения потребностей.
Рис. 10. Заполнение диалогового окна Поиск решения
Результат решения (рис. 11) сохраните в виде сценария с именем «Открытая модель 2».
Рис. 11. Результаты поиска решения
Контрольные вопросы
1. Какова постановка стандартной транспортной задачи?
2. Раскройте понятие сбалансированности транспортной задачи.
3. Что такое фиктивные и запрещающие тарифы?
4. Поясните, в чем заключается метод северо-западного угла?
5. Каким образом проверяется оптимальность плана?
6. Как выбираются циклы?
7. Как выбирается величина, перемещаемая по клеткам?
8. Какие задачи относятся к транспортным задачам с открытой моделью?
9. Какие задачи относятся к транспортным задачам с закрытой моделью?
10. Разработайте алгоритм поиска решения открытой транспортной задачи с помощью Excel
Литература
1. Казанцев А.К. Основы производственного менеджмента: учебное пособие [Текст] / А.К. Казанцев, Л. Северова. – М.: ИНФРА-М, 2008.
2. Балдин К.В. Управленческие решения [Текст] / К.В. Балдин, С.Н. Воробьев, В.Б. Уткин. — М.: Дашков и К0, 2005.
3. Зайцев М.Г. Методы оптимизации управления и принятия решений: примеры, задачи, кейсы [Текст]/ М.Г. Зайцев — М.: Дело, 2008.
4. Лапыгин Ю.Н. Управленческие решения [Текст] / Ю.Н. Лапыгин.- М.: Эксмо, 2009
