1. Исследование функции на безусловный экстремум 3

• Название: 1. Исследование функции на безусловный экстремум 3
• Дата: 20.12.2018
• Размер: 0.69 Mb.
• Имя файла: 1541130846473078.docx
• Тип: Исследование; #61169
• страница: 4 из 6

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Задача



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

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

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

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

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

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

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

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

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

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

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

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

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

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