Методы оптимизации (стр. 2 )

Проверить вектор на оптимальность в следующей задаче ЛП: Максимизировать при условиях:

еaijyi + cj, = 0, если хj >0 для jОJ2, iI – условие г) Запишем условие г) признака оптимальности: ( т. к. , следовательно, в первом и третьем ограничении условия 20 двойственной задачи достигается равенство)

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

Проверить вектор на оптимальность в следующей задаче ЛП: Максимизировать при условиях:

д) отсутствует, т. к. ни одно ограничение 20 основной задачи не выполняется как строгое неравенство. Из условия г) находим . Найден вектор . Проверяем его допустимость в двойственной задаче, т. е. выясняем, выполняются ли условия I0 и 20 двойственной задачи. Т. к. все условия выполняются, вектор y является оптимальным в двойственной задаче, а вектор х=(1, 0, 1, 0) - оптимальным в основной задаче.

Основная теорема теории линейного программирования

и ее следствия

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

Теорема двойственности. Каковы бы ни были исходные данные, для задач 1 и 1* имеет место один из следующих взаимоисключающих случаев.

1.  В задачах 1 и 1* имеются оптимальные векторы х и у и , т. е. обе задачи разрешимы.

2.  В задаче 1 существуют допустимые векторы х из некоторого множества Х, но линейная функция на множестве этих векторов не ограничена сверху, т. е., тогда в задаче 1* нет допустимых векторов.

3.  В задаче 1* существуют допустимые векторы , но функция не ограничена снизу на множестве этих векторов, т. е. , тогда в задаче 1 нет допустимых векторов.

4.  В задачах 1 и 1* нет допустимых векторов, то есть

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

Следствие 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. Максимизировать линейную функцию на множестве векторов х=( х1,х2, …х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. yi ≥ 0 для iÎI2 2.	Задача 2*. Минимизировать линейную функцию на множестве векторов , удовлетворяет условиям 1. 2.	Задача 3*. Минимизировать линейную функцию на множестве векторов , удовлетворяет условиям 1.  – 2.

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

Для оптимальности допустимого вектора х=(х1,х2…,хn,) достаточно существование m-мерного вектора у=(у1,у2,…,у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}.

Допустимое базисное множество

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

относительно переменных xk, , имеет единственное решение, отвечающее единственному разложению вектора — по соответствующим базисным векторам. Это решение можно дополнить до вектора х = (х1, х2, . . ., хn), удовлетворя­ющего условию , положив , .

Получаемый таким образом вектор х = (х1, х2, . . ., хn) будет обозначать­ся через х (К).

Т. е. система

(17)

имеет единственное решение.

Если компоненты , то вектор является допустимым вектором в задаче А.

В этом случае К называют допустимым базисным множеством (ДБМ),

=( х1, х2, . . ., хm, 0,…,0).

Двойственно допустимое базисное множество

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

Для любого базисного множества К единственное решение у(К) имеет система: , Если вектор у(К) является допустимым в двойствен­ной задаче А* ( т. е. удовлетворяет условию 2), то множе­ство К называется двойственно допустимым базисным мно­жеством (ДДБМ). Обозначим через , . Если , , то у(К) удовлетворяет условию 2), то есть является допустимым вектором в двойственной задаче А*.

Двойственно допустимое базисное множество

Итак, базисное множество является двойственно допустимым, если величины

, , (18)

удовлетворяют неравенствам

, (19)

Отметим, что величины (18) тесно связаны с коэффици­ентами разложения соответствующих векторов по рассматриваемым базисным векторам, а именно:

, , (20)

где - коэффициенты разложения векторов по рас­сматриваемому базису, т. е. . (21)

Действительно, учитывая (18), (21) , , и свойства скалярного произведения, получаем

. (22)

Лемма 2

Каково бы ни было базисное множество K, для соответствующих векторов х(К) и у (К) имеет место равенство

.

Доказательство. Так как , , , , получаем

,

что и требовалось показать.▄

Следствие из леммы 2 и признака оптимальности

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

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

Теорема. Если базисное множество К является одновременно допустимым и двойственно допустимым базисным множеством, то отвечающие ему векторы и оптимальные соответственно в задачах А и А*.

Доказательство. Пусть К – допустимое базисное множество и двойственно допустимое базисное множество. Это значит, что вектора и - допустимые. На основании леммы 2 , а это достаточно для того, чтобы вектор был оптимальным и вместе с ним и вектор (см. краткую форму достаточного признака оптимальности)▄

Лемма 3

Пусть задано некоторое базисное множество К и от­вечающий ему вектор

х (К) =(х1, х2, . . ., хп). Кроме того, для некоторого известны коэффициенты gk в разложении вектора по соответствующим базисным векторам:

=.

Тогда при любом вектор =() с компонентами

, , , , ,

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

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

Лемма 3

Доказательство. Имеем: = (23)

После умножения соотношения (18) на и переноса всех его членов в левую часть получаем равенство: (24)

Имеем: (25)

Складывая (19) и (20), получаем

. (26)

Следовательно, интересующий нас вектор удовлетворяет требуемому условию . Далее, для вектора выполнены равенства (в силу того, что , , , , и (22))

(27) ▄

Следствие 1 из леммы 3

Вектор должен удовлетворять условию неотрицательности, т. е..

Возможны два случая:

а). Все коэффициенты gk≤0 в

б) среди коэффициентов gk име­ются положительные

Следствие 1. Если имеет место случай а), то векторы , опреде­ляемые в лемме 3, являются допустимыми в задаче А при всех , а линейная функ­ция на множестве таких векторов не ограничена сверху.

Действительно,

По теореме двойственности (слайд 42) в двойственной задаче допустимый вектор не существует, следовательно, вектор х не оптимальный ▄

Следствие 2 из леммы 3

Вектор должен удовлетворять условию неотрицательности, т. е..

Случай б) среди коэффициентов gk име­ются положительные

Следствие 2. Если имеет место случай б), то векторы являются допустимыми в задаче А лишь при , где

,

причем

.

Пусть ; выполняется всегда; . Тогда , чтобы эти неравенства выполнялись одновременно, находят

Метод последовательного улучшения допустимого вектора (МПУ)

МПУ состоит в последователь­ном выполнении идентичных шагов (опишем вычислительные процедуры одного шага). К началу очередного шага пусть имеются некоторое ДБМ К и отвечающий ему допустимый вектор х(K) = (х1, х2, . . ., хп). Над этими исходными данными выполняются следующие процедуры:

I. Определение вектора y(К).

Зная базисные векторы и допустимый базисный вектор =( х1, х2, . . ., хm, 0,…,0), решаем систему линейных уравнений:

Эта система имеет единственное решение , т. к. К – это базисное множество.

Метод последовательного улучшения допустимого вектора (МПУ)

II. Проверка двойственной допустимости ДБМ К. Для найденного вектора у(К) вычисляются величины и проверяются неравенства , .

1.  Находим величины

При этом возможны два случая:

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

б) условие а) нарушается, т. е. К не является двойственно допустимым и вектор не допустимый в задаче А*. Надо найти и перейти к выполнению следующей процедуры.

Метод последовательного улучшения допустимого вектора (МПУ)

III. Вычисление коэффициентов разложения вектора по базисным векторам.