Методы оптимальных решений. ПКЗ мор. Для изготовления продукции двух видовАиВ фирма расходует ресурсы, а от реализации этой продукции получает доход
 Скачать 118.41 Kb.
|
|
Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно. Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности. Подставим оптимальный план прямой задачи в систему ограниченной математической модели: 5*81 + 1*43 = 448 < 746 1*81 + 5*43 = 296 = 296 9*81 + 1*43 = 772 = 772 1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y1 = 0. Неиспользованный экономический резерв ресурса 1 составляет 298 (746-448). Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду). 2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2 ≠ 0). 3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3 ≠ 0). Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными, (они будут иметь самые высокие оценки), какие менее дефицитными и какие совсем недефицитны (избыточны) - они будут равны нулю. Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи. Найдем решение двойственной задачи у*, воспользовавшись второй теоремой двойственности и известным оптимальным планом х*. Поскольку x1>0, 1-е ограничение в двойственной задаче будет равенством. Поскольку x2>0, 2-е ограничение в двойственной задаче будет равенством. Таким образом, решение двойственной задачи сводится к решению уравнений при следующих условиях: y1 = 0 5y1+y2+9y3 = 705 y1+5y2+y3 = 181 746y1+296y2+772y3 → min или y2+9y3 = 705 5y2+y3 = 181 746y1+296y2+772y3 → min Обоснование эффективности оптимального плана. При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим: 5*0 + 1*21 + 9*76 = 705 = 705 1*0 + 5*21 + 1*76 = 181 = 181 1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-й продукт экономически выгодно производить (убытки от производства этого вида продукции отсутствуют), а его использование предусмотрено оптимальным планом прямой задачи (x1>0). 2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-й продукт экономически выгодно производить (убытки от производства этого вида продукции отсутствуют), а его использование предусмотрено оптимальным планом прямой задачи (x2>0). Ситуационная (практическая) задача № 2 Необходимо доставить груз от трех поставщиков пяти потребителям. Предложение поставщиков (ед.)
Спрос потребителей (ед.)
Матрица затрат на доставку единицы груза от каждого поставщика потребителю (руб.)
1. Составить математическую модель оптимизации перевозок. 2. Определить исходный опорный план перевозок. 3. Найти оптимальный план перевозок методом потенциалов и соответствующие ему минимальные транспортные затраты. Решение. Стоимость доставки единицы груза от каждого поставщика каждому потребителю задана матрицей тарифов:
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 67 + 12 + 93 = 172 ∑b = 38 + 41 + 55 + 20 + 56 = 210 Как видно, суммарная потребность груза у потребителей превышает запасы груза у поставщиков. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительного (фиктивного) поставщика с запасом груза, равным 172 – 210 = 38. Тарифы перевозки единицы груза от этого поставщика ко всем потребителям возьмем равными нулю. Занесем исходные данные в распределительную таблицу.
Этап I. Поиск первого опорного плана. 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Искомый элемент равен c14=4. Для этого элемента запасы равны 67, потребности 20. Поскольку минимальным является 20, то вычитаем его. x14 = min(67,20) = 20.
|