ЗНАЕТЕ ЛИ ВЫ?

Критерий разрешимости задачи ЛП



Следствие 1 (Теорема существования)

Для того, чтобы в двойственных задачах 1 и 1* существовали оптимальные векторы х и у, т.е. имел место случай 1 теоремы двойственности, достаточно выполнения одного из следующих условий:

1. в задаче 1 существует оптимальный вектор х

2. в задаче 1* существует оптимальный вектор у

3. в задаче 1 существует допустимый вектор х и функция ограничена сверху

4. в задаче 1* существует допустимый вектор у и функция ограничена снизу

5. в задачах 1 и 1* существуют допустимые векторы х и у

 

Следствие 2 (Необходимый признак оптимальности)

Допустимый признак оптимальности в краткой и развернутых формах является так же необходимым признаком.

Доказательство: пусть имеется оптимальный вектор х в задаче 1 и оптимальный вектор у в задаче 1*. Тогда на основании условий 2 теоремы о существовании имеет место случай 1 теоремы двойственности, то есть .

Экономическая интерпретация двойственных задач

 

Пример.С внедрением новой технологии на некотором предприятии появилась возможность использовать отходы 1,2,3 - го видов производства, получаемых в количестве 70, 30, 15 единиц в сутки соответственно для производства двух видов изделий, пользующихся большим спросом. Известно, что для производства одного изделия первого вида требуется 4, 3, 0 единиц отходов 1, 2, 3-го видов соответственно; для производства одного изделия второго вида требуется 3, 4, 3 единиц отходов 1, 2, 3-го видов. Ожидаемая прибыль от реализации продукции I и II-го видов 12 и 15 рублей соответственно. Требуется составить план производства x= продукции I и II-го видов, обеспечивающий наибольшую прибыль (задача ЛП).   Задача I.Найти :  

Экономическая интерпретация двойственных задач

 

Задача I.Найти : Это же предприятие получило возможность продавать отходы производства, для чего ему необходимо определить их цену. Пусть - цена единицы отходов 1,2,3 - го видов. Естественно, что покупатель стремится к тому, чтобы суммарная цена всех отходов была наименьшей, а предприятию выгодно продавать их лишь в том случае, если выручка от продажи не меньше, чем прибыль от реализации готовых изделий.   Математическая модель задачи I Задача II.Найти : Задачи I и II являются парой двойственных задач.  

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

Общая форма ЛП 1 каноническая форма ЛП 2 каноническая форма ЛП
Задача 1. Максимизировать линейную функцию на множестве векторов х=( х12, …хn,), удовлетворяющих условиям: 1. хj ³0 для jÎJ2 2.   Задача 2. Максимизировать функцию на множестве векторов удовлетворяющих условиям 1. 2. I2=I={1,2,…,m} J2 J2 =J={1,2,…,n}   Задача 3. Максимизировать функцию на множестве векторов удовлетворяющих условиям: 1. 2. I1=I={1,2,…,m} J2 J2 =J={1,2,…,n}  

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

Общая форма ЛП 1 каноническая форма ЛП 2 каноническая форма ЛП
Задача 1*. Минимизировать линейную функцию на множестве векторов y=(y1,y2,…..ym), удовлетворяющих условиям: 1. yi0 для iÎI2 2.   Задача 2*. Минимизировать линейную функцию на множестве векторов , удовлетворяет условиям 1. 2.     Задача 3*. Минимизировать линейную функцию на множестве векторов , удовлетворяет условиям 1. – 2.

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

Для оптимальности допустимого вектора х=(х12…,хn,) достаточно существование m-мерного вектора у=(у12,…,уm), удовлетворяющего условиям:
Общая форма ЛП 1 каноническая форма ЛП 2 каноническая форма ЛП
а) б) в) г) д)   а) б) – в)   а) – б) – в) д) –  

Замечание. Наиболее удобной для решения задач ЛП является 2 каноническая форма

Вторая каноническая форма задачи ЛП в векторной форме

Введем в рассмотрение m-мерные векторы:

Тогда задачи 3 и 3* запишутся в следующей форме:

 

Задача А. Максимизировать линейную функцию на множестве n-мерных векторов х = (х1, х2, . . ., хn), удовлетворяющих условиям 1 . , , 2. Задача А*.Минимизировать линейную функцию на множестве m-мерных векторов y = (y1, y2, . . ., ym), удовлетворяющих системе линейных неравенств 1. - 2. , .

Базисное множество

 

Пусть m-мерное подмножество множества J.

Множество К называют базисным множеством, если отвечающие ему векторы являются линейно не­зависимыми, т.е. образуют базис в пространстве Rm. Число векторов в базисном множестве К равно числу m уравнений в условии 2 задачи А:

max

на множестве n-мерных векторов

х = (х1, х2, . . ., хn),

удовлетворяющих условиям

1 . , ,

2.

Пример. Векторы - линейно независимые, т.к. , К={1,2}.





Последнее изменение этой страницы: 2016-04-26; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.207.108.182 (0.006 с.)