6. Однокритериальные оптимизационные методы в принятии решений. 7. Метод линейного программирования.

ольшое число экономических задач сводится к линейным математическим моделям. Традиционно их называют моделями линейиого программирования Этот термин появился в конце 30-х годов XX в , когда компью- юрнос программирование еще не было развито Под линейным программированием понимается линейное планирование, т с. получение оптимального плана-решения в задачах с линейной структурой Обычно его используют специалисты штабных подразделений для разрешения производственных трудностей. Типичными примерами применения модели линейного программирования являются следующие —

укрупненное планирование производства (составление графиков производства, минимизирующих общие издержки в связи с изменением ставки процента), —

планирование ассортимента изделий (определение оптимальной структуры производства продуктов питапия для человека); —

маршрутизация производства изделий (определение оптимального технологического маршрута изготовления изделия), —

регулирование запасов (определение оптимального сочетания проектов на складе); —

календарное планирование производства (составление календарных планов, минимизирующих издержки с учетом расходов на содержание запасов, оплату сверхурочной работы и заказов на стороне); —

планирование распределения продукции и др

В самом общем виде линейное программирование сводится к оптимизационной задаче и записывается так-

и = /(X) —> шах; X е IV,

.дс X = (дг,,дг2, . , О.

И'' —область допустимых значений переменныхдГ|,л:2, .. , дг„;

/(X) — целевая функция.

Чтобы решить задачу оптимизации, достаточно пайти сс оптимальное решение, т с указать Х0 е IVтакое, что /(Х0) > }(Х) при любом X е IV, или для случая минимизации —/(Х0) ^ /(X) при любом X е IV.

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

Методы решения оптимизационных задач зависят как от вида целевом функции /(X), так и от строения допустимого множества W. Если целевая функция в задаче является функцией п переменных, то методы решения называют методами математического программирования

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

/W = T.Cj xj -> max (mm); (I)

IaljXj = bt,i e /, /с Л/ = {1,2, ...,m}; (2) I

aljXj

Xj > O.y eJ, Ус {1,2, (4)

При этом система линейных уравнений (2) и неравенств (3), (4), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией, или критерием оптимальности.

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

f(X) = Y.Cj Xj -> min; (5)

Y-a^Xj = b„ i = 1,..., m\ (6)

b, > 0; (7)

^>0,7=1,..,«, (8) то говорят, что задача представлена в канонической форме.

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

Правило приведения задачи линейного программирования к канони ческому виду состоит в следующем- —

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

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1; —

если среди ограничений имеются неравенства, то путем введе«(| ния дополнительных неотрицательных переменных онн преобразуются в равенства; —

если некоторая переменная дг* не имеет ограничений по знаку, то on.i заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: дг* = где 1 — свободный индекс, х'к > 0, дг, > 0.

Обобщая сказанное, можно сделать следующие выводы 1

Ограничения в задачах линейного программирования могут быть иыражены как равенствами, так и неравенствами 2

Линейная функция может стремиться как к максимуму, так и к минимуму. 3

Переменные в модели всегда неотрицательны. 4

От любой задачи линейного программирования можно перейти к канонической (основной) задаче линейного программирования

Каждой задаче линейного программирования можно противопоста- пн гь другую задачу линейного программирования, двойственную по отношению к исходной (прямой).

Рассмотрим задачу линейного программирования следующего вида: / = с,дг, + с^хг + ... + спх„ -> тах, (9)

ДцДГ, +0,2*2 + ... + а,„х„ < 6,

а21х\+а22хг+- + а2пх»

(10)

г, > 0,дг2 >0,...,дгл >0

В задаче требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком <, все переменные дг,, хг, ..., хп неотрицательны. Задача содержит« управляющих переменных и т ограничений. Коэффициенты при переменных в целевой функции: с,, с2,..., с„; свободные члены 6,, Ь2,..., Ьт

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

g = b^y^+b:yг + ... + Ьтут^п1Ш, (11)

аиН+а»у2+...+ат1ут ?с, ОаУ1+«ггУ2+-+«т2Ут йС2

а|,У,+а2->’2+- + а„„у„ <ся у1 >0,у2>0,...,ут >0

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

Коэффициенты целевой функции задачи Ь,, Ьг, ..., Ьт

являются свободными членами исходной задачи линейного программирования, а свободные члены двойственной задачи с,, с2, ..., с„ — коэффициентами целевой функции исходной задачи линейного программирования Матрица коэффициентов двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы — строками.

Задачи (9) — (10) и (11) — (12) образуют пару задач, называемую в линейном программировании двойственной парой

Двойственная задача по отношению к исходной составляется по следующим правилам