Двойственные задачи линейного программирования

Двойственные задачи линейного программирования

Оглавление

Введение        3

Двойственные задачи линейного программирования        4

Постановка двойственной задачи линейного программирования        5

Построение двойственной задачи линейного программирования на основании прямой задачи линейного программирования        7

Основные свойства оптимальных планов прямой и двойственной задач линейного программирования        9

Заключение        11

Список литературы        12

Введение

Каждой задаче линейного программирования соответствует двойственная задача линейного программирования. Исследование свойств двойственной задачи линейного программирования позволяет глубже изучить экономическую природу исходной задачи.

Настоящая работа ставит своей задачей рассмотреть свойства прямой и двойственной задач линейного программирования и изучить связь между задачами двойственной пары.

Двойственные задачи линейного программирования

Рассмотрим двойственную задачу линейного программирования на примере задачи планирования производства. При планировании производства ставится задача отыскания оптимального плана  который позволяет получить максимальную прибыль от реализации произведенной продукции[pic 1]

[pic 2]

при заданных ограничениях на ресурсы: сырье, используемое на производство продукции, энергоресурсы, расходные материалы, амортизацию станков и оборудования

[pic 3]

где по смыслу задачи переменные не могут быть отрицательными

[pic 4]

В результате производства по оптимальному плану ресурсы используются не одинаково. Часть ресурсов могут быть использованы полностью (быть в дефиците), а другие ресурсы могут быть в достатке, они остаются после производства, т.е. они избыточны.

Следовательно, должна быть разработана некоторая система оценки внутренней стоимости сырья и ресурсов для конкретного производства. Эти оценки связаны с технологическими особенностями (матрицей условий А), со структурой внешних цен (вектор прибылей С). Такие оценки называют расчетными оценками ресурсов.

Пусть имеется некоторое другое предприятие, например, кооператив, который может использовать все или часть имеющихся у первого предприятия видов сырья для выпуска совершенно других изделий по своим технологиям. В результате может быть поставлен вопрос о продаже предприятием кооперативу имеющегося у него сырья по договорным ценам. Возникает актуальный вопрос оценки ценности сырья для своего предприятия.

Пусть оценка  единицы i-го вида ресурса; , …,  – вектор оценки ресурсов;  суммарная оценка всех ресурсов предприятия.[pic 5][pic 6][pic 7][pic 8]

В результате обсуждения цены договора между предприятием и кооперативом возникает конфликт интересов: покупатель сырья стремятся минимизировать путем изменения оценок . Предприятие не может продавать сырье себе в убыток, т.е. предприятие должно учесть, что на производство единицы продукции j-го вида оно должно затратить различные виды ресурсов в количествах , …,  и их суммарная оценка будет равна  [pic 9][pic 10][pic 11][pic 12]

Стратегия предприятия состоит в том, что продавать свои ресурсы покупателю можно только в том случае, если эта сумма будет не меньше той прибыли, которую получит предприятие от реализации единицы готового изделия. Решение по оценке стоимости сырья необходимо рассчитать в виде математической задачи.

Постановка двойственной задачи линейного программирования

Сформулируем новую задачу линейного программирования оценки стоимости сырья:  необходимо найти вектор оценок ресурсов , …,  минимизирующий суммарную оценку всех ресурсов: [pic 13][pic 14]

[pic 15]

при условиях

[pic 16]

где по смыслу задачи                         (6)[pic 17]

В результате сформулирована двойственная задача линейного программирования к задаче (1-3). Расчетные оценки ресурсов, соответствующие оптимальному плану производства, служат компонентами оптимального решения двойственной задачи. Поэтому компонента  оптимального решения двойственной задачи называется двойственной оценкой i-го ресурса.[pic 18]