Файл: Контрольная работа по Методам оптимизации.docx

( 1′)

(2′)

(3′)

(4′)

(5′)

(6′)

(7′)

Если , то получаем точку (из (1′)…(3′),(7′)).

Остальные «симметричные» точки здесь и далее приводить не будем.

Если , , , то:

(1′),(2′) 

(2′),(3′) 

(7′) 

Из (6′) получаем точки и . , . Для значение , для значение .

Если , :

( 1′′)

(2′′)

(3′′)

(4′′)

(5′′)

Если , то (2′′),(3′′) ; (4′′) .

Следовательно, и . Но , пришли к противоречию.

Значит, .

(1′′)+(2′′)+(3′′):

Последнее слагаемое равно нулю согласно (4′′).

Поэтому, .

С другой стороны,

(по (5′′))

Следовательно, .

Если , то (1′′)…(3′′) .

Разделим на : . Но если , то их произведение не может быть равно . Значит, .

Если , получаем систему:

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

Предположив , получим те же результаты.

Найдены следующие точки:

, , ;

, , , ;

, , , ;

, , , .

Запишем второй дифференциал обобщенной функции Лагранжа.

, ,

является активным ограничением только для точки .

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

Подставив и во второй дифференциал функции Лагранжа, получим:

Запишем матрицу квадратичной формы относительно приращений:

Для «верхнего» знака матрица . Для «нижнего» знака элементы матрицы меняют знак. Согласно критерию Сильвестра, в этой точке нет экстремума.

Сравним значения функции в остальных точках:

Точкой глобального минимума является , значение функции в этой точке .

Проверим справедливость оценки для точки , .

Возьмем вектор , ему соответствуют множители Лагранжа .

Следовательно, .

Перепишем условие задачи, введя приращение :

И з первых трех уравнений получаем .

Подставим в последнее уравнение: , .

.

.

Возьмем, например, .

.

Проверим для :

С другой стороны, .

2. Решить задачу максимизации квадратичной функции при условиях и .

Решение.

Перепишем условие следующим образом:

Функция Лагранжа имеет вид:

Необходимые и достаточные условия минимума:

Получаем систему уравнений и неравенств:

Для решения промежуточной задачи ЛП воспользуемся средствами MS Excel.

Введем формулы, соответствующие системе:

Зададим начальное приближение:

Заполним поля диалога «Поиск решения»:

В окне «Параметры» установим флажок «Неотрицательные значения».

Результат поиска решения:

Найдена седловая точка функции Лагранжа: (х* ,λ*) = (15;0;0;30). Оптимальное решение задачи: х* (15;0;0), f(x*) = 152 = 225.

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

Модель задачи линейного программирования

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

Математическая модель задачи линейного программирования (ЗЛП) включает в себя:

1) целевую функцию , оптимальное значение которой (максимум или минимум) требуется отыскать:

(1)

2) ограничения в виде системы линейных уравнений или неравенств (функциональные ограничения задачи):

(2)

3) требование неотрицательности переменных (тривиальные ограничения задачи):

(3)

В (1), (2), (3) ( ) – заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (1) при соблюдении ограничений (2) и (3).

Вектор , удовлетворяющий ограничениям (2) и (3), называется допустимым решением (планом) ЗЛП.

План , имеющий не более m компонентов, отличных от нуля, называется допустимым базисным планом ЗЛП.

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

Итого, математическая модель ЗЛП в векторно-матричной форме принимает вид:

,

где – оптимизируемый вектор параметров;

– целевой вектор;

– вектор ограничений;

– технологическая матрица.

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

Рассмотрим некоторые теоремы (без доказательства), отражающие фундаментальные свойства ЗЛП и лежащие в основе методов их решения.

Теорема.  Множество всех планов ЗЛП выпукло (если оно не пусто).

Таким образом, множество всех решений ЗЛП является выпуклым многогранником (многогранником решений).

Теорема. Целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений. Если целевая функция принимает минимальное (максимальное) значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Итак, если целевая функция ЗЛП ограничена на многограннике решений, то существует такая угловая точка многогранника решений, в которой линейная функция ЗЛП достигает своего оптимума.

Теорема. Каждый допустимый базисный план яв­ляется угловой точкой множества допустимых пла­нов.

Теорема. Если – угловая точка множества допустимых планов, то она являет­ся допустимым базисным планом задачи.

Двойственность в линейном программировании

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

Рассмотрим ЗЛП в стандартной форме (прямую задачу):

Задача

называется двойственной к прямой задаче.

Сравнивая прямую задачу и двойственную, можно заметить пять «зеркальных» соотношений между ними:

1) число переменных прямой задачи равно числу функциональных ограничений двойственной задачи и наоборот;

2) технологические матрицы транспонированы по отношению друг к другу;

3) целевой вектор прямой задачи равен вектору ограничений двойственной задачи и наоборот;

4) направления оптимизации противоположны;

5) знаки неравенств в функциональных ограничениях противоположны.

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

В несимметричном случае двойственная задача составляется по тем же правилам, что и в случае симметричной пары, но если функциональное ограничение прямой задачи является равенством, то соответствующая неизвестная двойственной задачи может принимать как положительные, так и отрицательные значения и наоборот. Более того, если в прямой задаче переменная , то соответствующее j-ое ограничение двойственной задачи – неравенство вида «», если двойственная задача решается на минимум, и «», если на максимум.

Смысл теории двойственности раскрывается с помощью двух теорем, из которых первая является основной, а вторая является следствием из первой. Нас в дальнейшем будет интересовать только первая теорема.

Теорема (Первая теорема двойственности).

I. Если одна из задач двойственной пары имеет решение, то и другая имеет решение, причём экстремальные значения целевых функций совпадают: .

II. Если одна из задач не имеет решения из-за неограниченности целевой функции, то другая также не имеет решения из-за противоречивости условий и наоборот.

Замечание. Для первой теоремы двойственности справедливо обращение: если , то планы и – оптимальные.

5. Задача транспортного типа

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

Под транспортной задачей (ТЗ) обычно понимают задачу выбора плана перевозок некоторого товара от m источников (пунктов производства, поставщиков) к n стокам (станциям назначения, пунктам сбыта), обеспечивающего минимальные транспортные затраты. При этом предполагают, что а) мощность i-го источника равна S_i>0, i=1, ..., m; б) мощность j-го стока равна D_j>0, j=1,...,n; в) стоимость перевозки единицы товара от i-го источника к j-му стоку (тариф) равна c_ij (в условных денежных единицах).

Для математического описания транспортной задачи вводятся переменные х_ij, обозначающие объемы поставок товара из i-го источника к j-му стоку (в условных единицах объема товара ).

Таким образом, получаем модель ТЗ в виде задачи линейного программирования

ΣΣc_kjx_kj→ min; (1)

Σх_ij= S_i, (i=1,...,m);

Σх_ij= D_j, (j=1,..., n); (2)

x_ij≥0, i=1,...,m, j=1,..., n

Задача (1) с ограничениями (2) может быть решена стандартным симплекс-методом. Однако, специфика ограничений (каждое неизвестное входит только в два уравнения системы (2) с коэффициентами, равными 1) позволяет разработать специальные методы решения ТЗ и задач, которые сводятся к задачам транспортного типа (задача о назначениях, задача выбора кратчайшего пути, задача о замене оборудования и т.п.).

Формы представления ТЗ.

Задача (1), (2) может быть представлена в виде так называемой транспортной таблицы (матричная форма) (Рис.1 ) или в виде сети с ориентированными ребрами (Рис.2). Узлы сети соответствуют источникам и стокам ТЗ, ребро, соединяющее узлы i и j, – доставке товара из i-го источника к j-му стоку. Для каждого узла указывается его мощность, для каждого ребра – стоимость доставки груза (тариф).

Систему уравнений (2) можно представить в эквивалентном виде

Σх_ij= S_i, (i=1,...,m);

-Σх_ij= -D_j, (j=1,..., n); (2’)

Тогда для представления задачи (1), (2’) удобнее использовать следующую форму транспортной таблицы (Рис. 3). Свободные места в таблице соответствуют нулевым коэффициентам при соответствующих переменных. Источникам соответствуют коэффициенты 1, а стокам - коэффициенты -1. В сетевой форме этой записи задачи будут соответствовать мощности стоков, равные (–D_j ).

Рис.1

Рис.2.