- •IV. Методические указания к решению задач
- •Симплексный метод решения задачи линейного программирования
- •Математическую модель задачи запишем следующим образом:
- •2. Составление первого опорного плана
- •3. Проверка плана на оптимальность
- •4. Определение ведущих столбца и строки
- •5. Построение нового опорного плана
- •6. Полученный новый опорный план опять проверяется на оптимальность в соответствии с этапом 3 алгоритма
- •Двойственная задача.
- •Транспортная задача линейного программирования
- •Проверка условия оптимальности
- •5. Построение нового опорного плана
- •Замечания
- •Экономическая интерпретация основных и двойственных задач.
Экономическая интерпретация основных и двойственных задач.
Пусть для производства некоторого продукта имеется n-различных технологий. При этом используются m-ингредиентов (различные виды сырья и другие производственные ф-ры), причем по j-технологии расходуется в единицу времени Aij-единиц i-ингредиента, общий запас кот.равен Bi и производится Cj-единиц продукта, а Xj-время в течении кот.произ-во ведется по j-технологиям. Тогда при решении задачи X=(X1, X2,XN) будет произведено Z(X)= Столько продукта израсходовано. Постановка задачи: Отыскать такой оптимальный план, при кот.из имеющихся запасов ингредиентов выпускалось бы max-кол-во продуктов. Мат.модель: максимизировать линейную форму, переменные кот.удовлетворяют ограничениям: i=(1,m) Z(x)= , Xj , j=(1,n). Прямая задача при ограничениях и условиях. Для эконом.интерпритации двойственной задачи ЛП принимаем стоимость единицы выпускаемого продукта. Обозначим соот-щее этому масштабу цен ст-ть единицы i-го ингредиента через Ui, i=(1,m). тогда весь запас ингредиента будет стоить: , а стоимость затрат в единицу времени произв-ва по j-технологии определяется Стоимость Cj-продукта произведенного по J-технологии в единицу времени не может превышать стоимости затраченных ингредиентов, т.е. , j=(1,n) и чем меньше произведенных затрат произ-ва по j-технологии , тем ближе это неравенство к строгому равенству, тем точнее стоимость затрат, воплощается в стоимости произведенного продукта. Таким образом, рентабельность плана X=(X1,X2,…..Xn) должна означать точное воплощение в стоимость произведенного по этому плану продукта всей стоимости запаса ингредиента. В рентабельном плане стоимость всех затрат произ-ва должна равняться стоимости, произведенного продукта. . По основной теореме двойственности и ее следствию заключаем, что рентабельность и только рентабельному плану соотв-т такой набор: стоимостей , затрач.ингредиентов, что X' и U' явл-ся оптим-ми решениями двойственных задач. Основная задача закл-ся в выборе решения плана X’ макс-щего выпуск продукции: (1) При затратах ингредиентов, не превышающих их запасов (2) И двойств.задача в нахождении набора чисел U’=(U1’, U2’,…Un’) стоимости ингредиентов, минимизирующих стоимость (2) , j=(1,n) (3) (4), (5), Ui (6). Стоимость ингридиентов мин-я подается использованию запасов, подлежащих использованию запасов ингредиетов, не превышающего стоимости продукта, произведенного по каждой технологии.