Задача математического программирования

Методы оптимизации

Математическая модель

Математическая модель — описание решаемой задачи в математических терминах.

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

W = f (X, Y),

где X = (x ₁,…, x_n) — управляемые переменные,

Y = (y ₁,…, y _m) — неуправляемые переменные(исходные данные).

Связь между переменными X и исходными данными Y выражается с помощью ограничений

j (X, Y) £ 0.

Виды моделей

· детерминированные;

· вероятностные;

· игровые;

· неполные (задачи в условиях неопределенности).

 

Исследованием детерминированных моделей занимается математическое программирование (МП).

 

Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).

 

Задача оптимизации

(

)

Задача математического программирования

Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f (x) на множестве всех допустимых решений.

Задачи математического программирования

 

 

История математического программирования

Б.Т. Поляк, Институт проблем управления, Москва

История математического программирования в СССР: попытка анализа

 

История математического программирования

1. Леонард Эйлер, 1707-1783, первый ученый, занимавшийся оптимизацией в России

2. Чебышев П.Л., 1821-1894, основы выпуклой оптимизации, решал практические оптимизационные задачи: построение наименее искаженной географической карты, оптимальный раскрой, наилучший выбор параметров механических устройств

3. А.А. Марков, 1856-1922, известны работы в теории чисел и теории вероятностей (Марковские цепи, Марковские процессы)

4. А.М. Ляпунов, 1857-1918, разработал теорию устойчивости для дифференциальных обыкновенных уравнений, тем самым внес огромный вклад в развитие непрерывной оптимизации, предложил инструмент для проверки сходимости численных методов оптимизации

История математического программирования

5. Л.В. Канторович, 1912-1986, в 1975г. получил Нобелевскую премию в области экономики, один из основателей численного анализа в нашей стране, одним из первых признал информатику как новую ветвь в математике.

Отец новой науки ОПТИМИЗАЦИИ, которая включает стандартное математическое программирование.

С именем Канторовича Л.В.связаны следующие достижения:

Линейное программирование, 1939:

Опубликована книга (67 стр.), в которой рассматривался новый тип оптимизационных задач. Формы записи этих задач были иными, чем стандартная формулировка задачи ЛП, причем модель, рассматриваемая в западной литературе - частный случай модели Канторовича.

Общие условия оптимальности, 1940

Техника функционального анализа, 1939-1948

 

История математического программирования

6. Г.Ш. Рубинштейн, ученик Канторовича Л.В., учитель д.т.н., проф. УГАТУ Мухачевой Э.А.

В 1961г. вышла книга Канторовича Л.В. и Рубинштейна Г.Ш., в которой давались математические формулировки задачи ЛП и приводились численные методы ее решения, были введены понятия двойственных переменных, которые назывались «объектно-обусловленными оценками».

7. В 50-е годы – интенсивные исследования в области ЛП.

Стали известны работы западных ученых: Дж. Данцига, Г.Куна, А. Таккера и др. по ЛП.

Выпущен первый учебник на русском языке по ЛП Юдиным Д.Б., Гольштейном Е.Г.

8. 60-е годы

Появилась общая теория двойственности для задач выпуклой оптимизации (Гольштейн Е.Г.), появились труды по стохастической оптимизации.

Литература

1.Канторович Л.В. Математические методы организации и планирования производства. Л.: Изд-во Ленинградский университет, 1939, 64с.

2. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. М.: Советское радио. 1964, 491с.

3. Карманов В.Г. Математическое программирование. М.: Наука, 1975, 272с.

4. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Изд-во «Наука», Сибирское отделение, 1987, 272с.

5. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение АСУ. М.: Машиностроение, 1984,174с.

6. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа: УГАТУ, 1998, 217с.

7. Мухачева Э.А., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. Москва: Изд-во МАИ, 2004, 192с.

Задача об оптимальной смеси

Цель – подобрать оптимальный состав коктейля из трех компонентов: коньяка, шампанского и сока. Стоимости ингредиентов смеси соответственно: с1=50, с2=100, с3=20; Содержание в них алкоголя: а1=0,4; а2=0,5; а3=0,0; Вкусовые качества в баллах: в1=4, в2=8, в3=10.

Пусть хi(i = 1,2,3) – доля каждого компонента в коктейле (все расчеты ведем на единицу объема). Стоимость коктейля определится функцией: f1(x1, x2, x3)= с1 x1+ с2 x2+ с3 x3 Крепость коктейля определится функцией: f2(x1, x2, x3)= a1 x1+ a2 x2+ a3 x3 Вкус коктейля определится функцией: f3(x1, x2, x3)= в1 x1+ в2 x2+ в3 x3 Естественное желание – получить коктейль минимальной стоимости, максимальной крепости и максимального вкуса (противоречивые критерии!)

Общая форма задачи ЛП

Пусть заданы: множества I ={1,2…m} и J= {1,2…n}, причем I= I₁U I₂, I₁ Ç I₂ = Æ, J= J₁UJ₂, J₁Ç J₂ = Æ, вещественные числа а_ij, iÎI, jÎJ; b_i, iÎI, с_j, jÎJ.

 

ЗАДАЧА 1 (прямая со смешанными ограничениями)

Максимизировать линейную функцию

(1)

на множестве векторов х= (х₁,х₂, …х_n,), (2)

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

 

1. х_j ³0 для jÎJ₂ (3)

2. (4)

 

Двойственная задача ЛП

ЗАДАЧА 1* (двойственная со смешанными ограничениями).

Минимизировать линейную функцию

(5)

на множестве векторов y= (y₁,y₂,…..y_m), (6)

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

1. y_i ≥ 0 для iÎI₂ (7)

2. (8)

 

 

Определение.

Векторы (2), (6), удовлетворяющие условиям (3), (4) и (7), (8) называются допустимым для задачи 1 и задачи 1* соответственно.

Допустимые векторы (2), (6), доставляющие максимум функции (1) и минимум функции (5) соответственно, называются оптимальными.

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

Пример 1. Записать двойственную задачу к следующей задаче линейного программирования. ЗАДАЧА1. Найти х = (х1, х2, х3, х4), удовлетворяющий условиям:

Решение. Заметим, что т.е все переменные связаны условием неотрицательности, и все ограничения выполняются как неравенства. Двойственная задача имеет вид: ЗАДАЧА 1^* Найти удовлетворяющие условиям:

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

Пример 2. ЗАДАЧА 1. Требуется мак­симизировать линейную функцию =2x1 — х2 + Зх3 + х4 — 5x5 на множестве пятимерных векторов х = (х1, х2, х3, х4, х5), удовлетворяющих условиям , , , Зх1 + 2х2 - 5х3 + х5 - 7 0, 3х2 - 4х3 - 2х4 + 1 = 0, 2х1 + 2х3 - 3х4 + х5 0.

Решение. ЗАДАЧА 1^* Требует­ся минимизировать линейную функцию на множестве трехмерных векторов, удовлетворяющих условиям , , 3y1 + 2y3 + 2 0, 2y1 + 3y2 -1 = 0, - 5y1 + 4y2 + 3y3 + 3 0, - 2y2 - 3y3 +1 0, y1 + y3 - 5 = 0.

Связь между задачами 1 и 1^*

 

Связь между парой двойственных задач устанавливает следующая лемма 1:

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

µ(x) £ (у), (9)

причем (9) выполняется как равенство в том и только в том случае, если справедливы следующие соотношения:

(10)

(11)

 

 

Связь между задачами 1 и 1^*

Доказательство. Имеем:

х_j ³0 для jÎJ₂

(12)

 

Суммируя полученные соотношения, получим с учетом того, что (13)

 

 

Связь между задачами 1 и 1^*

Доказательство (продолжение). Имеем:

y_i ≥ 0 для iÎI₂

(14)

(15)

Правые части в соотношени­ях (13) и (15) отличаются лишь порядком суммирова­ния и, следовательно, равны между собой, т.е. выполняется µ(x) £ (у) (9). Для достижения равенства в (9), очевидно, не­обходимо и достаточно, чтобы достигались равенства во всех неравенствах (13) и (15). Последнее эквива­лентно выполнению соотношений (10) и (11) ▄

Доказательство.

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

Рассмотрим некоторый другой оптимальный вектор х′ в задаче 1 (х′≠х), тогда имеем пару векторов х′ и у. Для этой пары допустимых векторов справедлива лемма 1, т. е. m (х′) ≤ n (у) =m (х)и m (х′) ≤m (х). Отсюда следует что х – оптимальный вектор.

Покажем теперь, что вектор у также является оптимальным.

Рассмотрим некоторый другой оптимальный вектор у′ в задаче 1 (у′≠у), тогда имеем пару векторов х и у′. Для этой пары допустимых векторов справедливо лемма 1, т. е. n(у′)≥m(х)= n(у) и n(у)≤ n(у′). Отсюда следует что у – оптимальный вектор.▄

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

 

Как этим признаком пользоваться?

Предположим, что мы имеем допустимый вектор х, т.е. х_j ≥0 и такие, что , .

Тогда попытаемся найти вектор у из уравнений б), г), д). Эта система совместна и имеет единственное решение, если выполняются следующие условия:

1) Количество уравнений в системе m (совпадает с числом переменных);

2) Матрицы при неизвестных – неособенные

 

 

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

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

Решение. Решение задачи необходимо начинать с проверки допустимости данного вектора . Подставляя значения компонент вектора в ограничении I^0 и 2^0, убеждаемся, что все они выполняются. Для проверки остальных условий признака оптимальности составляем двойственную задачу: Требуется найти вектор , удовлетворяющий условиям:

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

 

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

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

→ max

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

х = (х₁, х₂,..., х_n),

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

1. , ,

2.

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

Лемма 2

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

.

 

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

,

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

 

Лемма 3

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

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

= .

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

, , , , ,

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

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

Лемма 3

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

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

Имеем: (25)

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

. (26)

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

(27) ▄

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

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

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

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

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

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

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

 

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

 

 

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

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

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

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

,

причем

.

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

V. Подготовка информации к следующему шагу.

В ка­честве нового допустимого базисного множества принимаем

K' = (K\ (k* }) { j₀ }.

Из базиса удаляется вектор , а вводится в базис вектор .

 

Вычисляем компоненты соответствующего вектора

х (К') = ()

по формулам

, k K' \ { j₀ }, .

При этом

.

 

 

Пример решения задачи ЛП с помощью МПУ

Прямая задача А Двойственная задача А^*

Найдем базис, базисное множество К, построим исходный допустимый вектор x (K)

	α^1	α^2	α^3	α^4	β	y
				-2	y1
	-3			-3	y2
сj

Векторы α³, α⁴ – линейно независимы, базисное множество K ={3,4}.

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

Исходный допустимый вектор: x (K)=(0,0,2,3); m=2

Пример решения задачи ЛП с помощью МПУ

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

Шаг

Единственное решение имеет система: , K ={3,4}.

y (K)=(0,0)

II. Проверка двойственной допустимости ДБМ К

, .

Проверим , ? Ясно, что

Вектор вводим в базис

Пример решения задачи ЛП с помощью МПУ

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

- разложение по базису

IV. Определение .

Определяем, какой вектор удалить из базиса.

Т.к. , К ⁺ ={3}

Исключаем из базиса вектор

 

 

Пример решения задачи ЛП с помощью МПУ

V. Подготовка информации к следующему шагу.

В ка­честве нового допустимого базисного множества принимаем

K' = (K\ (k* }) { j₀ } K' ={2,4}

 

,

k K' \ { j₀ },

.

- допустимый вектор

 

(функция не ухудшилась)

 

2 шаг

…………………

Методы оптимизации

Математическая модель

Математическая модель — описание решаемой задачи в математических терминах.

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

W = f (X, Y),

где X = (x ₁,…, x_n) — управляемые переменные,

Y = (y ₁,…, y _m) — неуправляемые переменные(исходные данные).

Связь между переменными X и исходными данными Y выражается с помощью ограничений

j (X, Y) £ 0.

Виды моделей

· детерминированные;

· вероятностные;

· игровые;

· неполные (задачи в условиях неопределенности).

 

Исследованием детерминированных моделей занимается математическое программирование (МП).

 

Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).

 

Задача оптимизации

(

)

Задача математического программирования

Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f (x) на множестве всех допустимых решений.