Общая задача математического программирования. Задача линейного программирования. Прямая и двойственная задачи линейного программирования

Математическая модель задачи – это отражение оригинала в виде функций, уравнений, неравенств, цифр и т.д. Модель задачи математического программирования включает: совокупность неизвестных величин х1, х2, …, хn ; целевую функцию; налагаемых на неизвестные величины ограничений, совокупность которых образует область допустимых решений (Ω). Можно записать математическую модель:

F=f(х1, х2, …, хn)→max (min) (i= )

Суть принципа оптимальности состоит в стремлении выбрать такое планово-управленческое решение , где (j= ) — его компоненты, которое наилучшим образом учитывало бы внутренние возможности и внешние условия производственной деятельности хозяйствующего субъекта.

Традиционные критерии оптимальности: «максимум прибыли», «минимум затрат», «максимум рентабельности» и др.

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

Общей формой записи задачи линейного программирования называют задачу максимизации или минимизации линейной функции

f = max (min) при линейных ограничениях

и при условиях , , , где J1 J2 =( j= ) и аij, bi, cj — постоянные числа.

Симметричной формой записи задачи линейного программирования называют задачу максимизации линейной функции (2.1.), при линейных ограничениях (2.2.), когда все ограничения имеют смысл неравенства вида «≤» и все переменные неотрицательны, т.е.

f = max

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

f = max

Общей формой записи ЗЛП называют задачу максимизации или минимизации линейной функции

при линейных ограничениях

и при условиях .

На практике часто приходится одну форму записи ЗЛП преобразовывать в другую. При этом пользуются следующими соображениями:

1) Задачу максимизации можно заменить задачей минимизации и наоборот. Экстремум этих функций достигается в одной точке: minf = -max(-f ). После решения задачи max(-f ) необходимо изменить на противоположный знак оптимум функции.

2) Если на какую-либо переменную не наложено условие неотрицательности (например хk), то её можно заменить разностью двух новых неотрицательных переменных (хk’ и xk”), т.е. хk=хk’–xk”.

3) Любое неравенство задачи линейной оптимизации вида “ ”, можно преобразовать в равенство добавлением к его левой части дополнительной неотрицательной переменной, а неравенство, вида “ ” – вычитанием из его левой части дополнительной неотрицательной переменной.

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

Примером симметричных задач, например, являются задачи, где в прямой речь идет о нахождении оптимального плана выпуска продукции при ограничениях ресурсов из условия максимизации выручки, а в двойственной – о нахождении системы внутренних цен на используемые в производстве ресурсы, из условия минимизации стоимости всех запасов имеющихся на предприятии. Система двойственных оценок (у_i) тесно связана с конкретными условиями данного производства. С изменением этих условий меняется и система этих оценок.

В общем виде модели симметричных двойственных задач имеют сле­дующий вид:

Прямая или исходная	Двойственная
f = max (I)	φ = min (II)

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

1. Коэффициентами целевой функции двойственной задачи, являются свободные члены ограничений прямой задачи, а свободными членами ограничений двойственной задачи - коэффициенты целевой функции прямой задачи. В двойственной задаче будет столько переменных, сколько ограничений в прямой и столько ограничений, сколько переменных в прямой задаче. Таким образом, каждому ограничению задачи отвечает соответствующая пе­ременная двойственной задачи и наоборот.

2. Матрицы коэффициентов при переменных в двойственных задачах взаимно транспонированы.

3. Каждому ограничению-неравенству в двойственной задаче отвечает неотрицательная переменная, а каждому ограничению равенству ─ переменная произвольного знака и наоборот: каждой неотрицательной переменной ─ ограничение неравенство, а каждой переменной произвольного знака ─ ограничение равенство. При этом в задаче максимизации ограничения-неравенства имеют смысл« », ав задаче минимизации ─ « ».

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

Несимметричные двойственные задачи:

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

При этом выполняются следующие правила:

1. Если на переменную x_i прямой задачи наложено условие неотрицательности, то i-е условие системы ограничений двойственной задачи является неравенством и наоборот.

2. Если на переменную xi прямой задачи не наложено условие неотрицательности, то i-е ограничение двойственной задачи записывается в виде строгого равенства.

3. Если в прямой задаче имеются ограничения равенства, то на соответствующие переменные двойственной задачи не накладывается условие неотрицательности.

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

1) Сформулировать эк-ко-математическую модель задачи;

2) Привести задачу к симметричной форме (смысл ограничений неравенств должен быть ≤0 по прямой задаче по критерию max)

3) Транспонировать матрицу исходной задачи

4) Поменять ролями вектор-столбец B с вектором строкой C.

5) Условие max-ии целевой функции изменить на условия min-ии;

6) Смысл неравенств ограничений ≤ заменить на смысл неравенств ≥;

7) Если j-ая переменная исходной задачи произвольная (отсутствует), то j-ое ограничение двойственной задачи выполняется как строгое равенство и наоборот: если i-ое ограничение двойственной задачи выполняется как строгое равенство, то i-ая переменная прямой задачи отсутствует.

24. Применение методов теории графов в сетевом планировании и управлении

Сетевые методы – это совокупность математических методов, в основе которых лежит графическое представление комплекса работ в виде сетевого графика (сети).

Таким образом, основным элементом систем СПУ является сетевая модель, которая моделирует процесс выполнения комплекса работ для достижения определенной цели (в дальнейшем комплекс работ для достижения определенной цели будем называть проектом). Графическое изображение сетевой модели называется сетевым графиком.

Сетевой график с математической точки зрения представляет собой ориентированный граф без петель и контуров. Обозначим его G = ( ), где Е – непустое конечное множество вершин, а – конечное множество ориентированных дуг, соединяющих некоторые пары вершин.

Дугам на сетевом графике соответствуют работы, а вершинам – события.

(в мировой практике встречается и другое представление: работы – вершины; события – дуги).

Работа – это любые действия, трудовые процессы, сопровождающиеся затратами времени или (и) ресурсов и приводящие к определенным результатам.

Все работы можно разделить на действительные работы, ожидания, фИТивные (зависимости). Под действительными работами следует понимать любой трудовой процесс, требующий ресурсов и имеющий некоторую продолжительность (на графике изображаются сплошными стрелками). Ожидание – это некоторый процесс, не требующий ресурсов, но имеющий некоторую продолжительность (на графике – штрих-пунктирными стрелками). ФИТивные работы (зависимости) не требуют ресурсов и имеют нулевую продолжительность, они используются для обозначения логических зависимостей между действительными работами (на графике изображаются пунктирными стрелками).

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

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

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

Любая работа сетевой модели соединяет два события: начальное событие работы и конечное событие работы. Для однозначного обозначения работ используют идентификаторы (i, j), где i – номер начального события работы, j – номер конечного события работы. Обычно на сетевых графиках события упорядочены, то есть i < j.