ЭММиМ. Задача об использовании ресурсов. Для изготовления двух видов продукции р 1, р 2 используются три вида ресурсов S
 Скачать 0.79 Mb.
|
|
Пункты назначения (ПН). Имеется n пунктов назначения B1, B2,…, Bn, подавшие заявки на b1, b2,…, bn ед. товара. Известны стоимости (тарифы) cij перевозок единиц товара от каждого ПО в каждый ПН. Требуется составить такой план перевозок, при котором все заявки на товар были бы выполнены при минимальной стоимости всех перевозок. В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем ТЗ могут быть закрытыми и открытыми. Если  , то задача называется закрытой.Если  , то задача называется открытой.Закрытая транспортная задача Построим математическую модель задачи, определив в ней переменные, ограничения и целевую функцию. Переменные: xij - количество груза, отправляемого из пункта Ai в пункт Bj, причем xij 0. Запишем условия задачи в виде следующей транспортной таблицы
Строки транспортной таблицы соответствуют ПО (в последней клетки каждой строки указан объем запаса груза), а столбцы – ПН (последняя клетка каждого столбца содержит значение потребности. Все клетки таблицы (кроме тех, которые расположены в нижней строке и в правом столбце) содержат информацию о перевозках xij и их стоимости сij. Запишем систему ограничений. 1) Ограничение по уровню запасов: Суммарное количество груза, направленного из каждого ПО во все ПН должно быть равно запасу груза в данном ПО:  2) Ограничение по уровню спроса: Суммарное количество груза, доставляемого в каждый ПН из всех ПО должно быть равно заявке данного ПН:  Целевая функция: Суммарная стоимость всех перевозок, которую необходимо минимизировать:  Планом перевозок называется любая совокупность значений переменных xij - матрица размера m×n. Допустимым решением называется план xij, удовлетворяющий системе ограничений ТЗ. Оптимальным решением называется допустимое решение, доставляющее минимум целевой функции. Решение ТЗ в Excel Надстройка Поиск решения в Microsoft Excel позволяет напрямую находить оптимальное решение транспортной задачи. I. Закрытая модель, .До вызова Поиск решения необходимо подготовить данные для решения ТЗ на рабочем листе Excel. В Excel закрытая задача решается учетом ограничений для всех отправителей и всех потребителей  - условия полного распределения запасов и полного удовлетворения потребностей.Пример 1. На трех складах имеется мука в количестве 60, 130, 90 т., которая должна быть доставлена четырем хлебозаводам в количестве 30, 80, 60, 110 т соответственно. Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей  ▼ Рабочий лист Excel для примера 2.30  В правой части табл. 2.30 указана подсказка:  Приведем последовательность ввода данных задачи и формул в соответствующие ячейки. A1:F5 — вводится транспортная таблица примера. I3 — вычисляется сумма по строкам по формуле: =СУММ(F2:F4). I4 — вычисляется сумма по столбцам по формуле: =СУММ(B5:E5). Из сравнения значений делается сообщение о типе модели (закрытая, открытая) и типе ограничений (=, < =) в окне Поиск решения. A7:F11 — составляется начальная матрица перевозок (вначале копируется транспортная таблица, затем редактируется) В8:Е10 — производится резервирование и обнуление изменяемых переменных (начальная матрица перевозок). F8:F10 и B11:E11 — подсчитываются суммы Σ по строкам и столбцам начальной матрицы перевозок. С13 — вычисляется стоимость начального плана L по формуле: =СУММПРОИЗВ(B2:E4;B8:E10). Далее нужно выполнить команду Поиск решения. В диалоговом окне Поиск решения: • установить целевую ячейку L равной минимальному значению; • в качестве изменяемых ячеек ввести матрицу перевозок xij; • установить ограничение для всех отправителей и всех потребителей; • выбрать метод решения: Поиск решения лин. задач симплекс-методом. Заполненное диалоговое окно Поиск решения имеет следующий вид  Равенство $B$11:$E$11 = $B$5:$E$5 означает условие полного удовлетворения потребностей. Равенство $F$8:$F$10 = $F$2:$F$4 означает условие полного распределения запасов. После выполнения программы работы «Поиск решения» получим
Оптимальное решение  ,  усл. ед. Таким образом, из первого склада следует отправить муку на 2-й хлебозавод в количестве 60 т., из второго склада — на 3-й и 4-й хлебозаводы в количестве 20 и 110 т. соответственно, из третьего склада — на 1-й, 2-й и 3-й хлебозаводы в количестве 30, 20 и 40 т. соответственно. При этом минимальные транспортные расходы составят 1550 усл. ед ▲ Упражнение 1. На предприятии имеются три группы станков, каждая из которых может выполнять пять операций по обработке деталей (в любом порядке). Максимальное время работы каждой группы станков соответственно равно 100, 250, 180 ч. Каждая операция должна выполняться соответственно 100, 120, 70, 110, 130 ч. Производительность каждой группы станков на каждую операцию задана матрицей  Определить, сколько времени и на какую операцию нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей. Ответ. Оптимальное решение  ,  шт. Таким образом, на первой группе станков целесообразно выполнять операции 1 и 4 продолжительностью 40 и 60 ч соответственно, на второй группе — операции 1, 2 и 3 продолжительностью 60, 120 и 70 ч соответственно, на третьей группе — операции 4 и 5 продолжительностью 50 и 130 ч соответственно. При этом максимальное число обработанных деталей составит 5170 шт. II. Открытая модель,  .Для открытой модели может быть два случая: a) суммарные запасы превышают суммарные потребности:  ; b) суммарные потребности превышают суммарные запасы:  . В Excel открытая задача решается путем изменения ограничений по предложению (если предложение превышает спрос) или по спросу (если спрос превышает предложение), т.е. система ограничений будет иметь вид: a)  - условия неполного распределения запасов и полного удовлетворения потребностей;b)  - условия полного распределения запасов и неполного удовлетворения потребностей.Пример 1. Три торговых склада могут поставлять некоторое изделие в количестве 9, 4, 8 т. Величина спроса трех магазинов розничной торговли на это изделие равна 3, 5, 6 т соответственно. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю заданы матрицей  Требуется составить такой план перевозок, при котором спросы на изделия в магазины были бы выполнены при минимальной стоимости всех перевозок. ▼ Рабочий лист Excel и заполненное диалоговое окно Поиск решения имеют вид   Неравенство $E$8:$E10< = $E$2:$E$4 означает условие неполного распределения запасов. После выполнения программы работы «Поиск решения» получим
Оптимальное решение  ,  ▲ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
