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

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

Если в задаче (1),(2) на условный экстремум ограничение (2) в виде равенства заменяется на ограничение g(xltx2) < 0 в виде неравенства, то мы получаем частный случай задачи математического программирования:

fixvx2) -> max (Лхгх2) -> min) (1)

при условии

-0. (15) В случае функции двух переменных задача математического программирования (для определенности задача на максимум) имеет вид((1),(16.1)-(16.т),(17))

Лхгх2) -> max (1)

при условиях

S.fr.^-O (16.1)

g^',x2)<0 (Іб.т) „,_0, х2>0 (17)

ФункциюДх,,х2) принято называть целевой, неравенства (16.1)-(16.т) специальными ограничениями задачи математического программирования, неравенства хх > 0, х2 > 0 общими ограничениями задачи математического программирования.

Точка (jCpXj), удовлетворяющая специальным и общим ограничениям, называется допустимым решением задачи математического программирования.

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

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

Точка (х{0,х2°) называется оптимальным решением ЗМП, если, во-первых, она есть допустимое решение этой ЗМП и если, во-вторых, на этой точке целевая функция достигает глобального максимума (в случае задачи максимизации) или глобального минимума (в случае задачи минимизации) среди всех точек, удовлетворяющих ограничениям, т.е. для всех (хгх2), удовлетворяющих неравенствам (16.1)-(16.т), (17), справедливо неравенство

Дх,0,*/) >Дхх,хЛ (в случае задачи максимизации), Дх,°,х2°) <Дх,,х2) (в случае задачи минимизации).

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

В экономической теории часто ЗМП сводится к задаче на условный экстремум. В качестве иллюстрации приведем пример задачи потребительского выбора (задачи рационального поведения потребителя на рынке) в виде ЗМП (задача потребительского выбора подробно описана в следующей главе)

j/(jc,,Xj) -» max ; (18)

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

рххх + р2х2<1 (19) х, >0, х2>0. (20)

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

„ / „ Эм(х,,х_) Эм(х,,х,)

полезности и(х,,х2) по переменнымх, и х2, т.е. И v 1 2/и — 1 2 ,

Эх, Эх,

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

Дадим геометрическую интерпретацию задачи потребительского выбора (см. рис. 8.8).

Заштрихованный треугольник на рис. 8.8 показывает множество потребительских наборов (х,,х2), которые доступны индивидууму, однако только на единственном потребительском наборе (хДх^) потребитель максимизирует свою функцию полезности ы(х,^). В точке (хДх/) бюджетная прямая рххЛр^^І и линия безразличия касаются. В связи с тем, что /^х," + р2х2 = I, оптимальное решение (хДх/) ЗМП совпадает с решением (х,°,х2°) следующей (более простой) задачи на условный (глобальный) экстремум

ы(х,,х,) -> max (18)

при условии

5* pxxx+P2x2-I=Q. (21)

Таким образом, задача потребительского выбора может быть описана как в виде ЗМП (18) -(20), так и в виде задачи на условный экстремум (18),(21). С математической точки зрения это разные задачи, однако они имеют одно и то же решение (х,0,х20) потребительский набор, который максимизирует (глобально) функцию полезности и(хрх2) и удовлетворяет бюджетному ограничению ріхі+р7х2йІ как равенству: рхх^+р2х1°=1. На рис. 8.8 также показаны градиенты функции полезности и(хрх2) и функции ограничения р^+p^-I в точке (х,0^0): grad^t,0^0) и (р{,р2). Эти градиенты расположены на одной прямой, проходящей через точку (х,0^0), что, как уже отмечалось, эквивалентно касанию линии безразличия и бюджетной прямой в точке (хДх").

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

Если в ЗМП все функции Дх,,х2), g(x,,x,), gm(xvx2) линейны, имеем задачу линейного программирования (ЗЛП), если хотя бы одна из функций Дхрх2), g,(xpx2), g (х х2) нелинейная, имеем задачу нелинейного программирования (ЗНЛП).

ЗЛП на максимум в случае двух переменных х, и х2 имеет вид

при условиях

(22)

(23.1)

а ,х,+а -Х^<Ь , (23.т)

ml 1 ml 2 ш' 4 '

х,>0, х2>0 (24) (ЗЛП в стандартной форме)

или такой вид

cix]+c2x~v -> max (22)

при условиях

апхі+аЛ=Ьі (25) х, > 0, х2 > О

(ЗЛП в канонической форме).

В ЗЛП числа сгс2,ЬгЬ2,...,Ьт,аИ,а ат1,ат2 заданы.

В случае п переменных хр...,хп ЗЛП на максимум имеет вид

с,х,+...+с x(i=v -> max (26)

при условиях

а,,х,+...+а, х <Ь. (27.1)

а .х.+...+a х <А (27.т)

х,>0, х>0 (28)

(ЗЛП в стандартной форме на максимум)

или такой вид

c.x.+...+сх =v -» max (26)

при условиях

0..*.+--ЧЛ=А, (29-1)

а .х+...+a х=/> (29.m)

ml I m» и in V /Ло<

x,>0,...,x>0 (28)

(ЗЛП в канонической форме на максимум, здесь т<п).

ЗЛП на минимум имеет вид

при условиях

с.х,+...+с х =w -» min її а и

а..х,+...+а. х >b. и і і а и і

a ,x.+...+a x >b

ml I inn и in

x, >0, xn >0 (ЗЛП в стандартной форме на минимум)

или такой вид

с^+.-.+сх.=w -» min

при условиях

аіЛ+-+°іЛ=*і

х, >0, ...,х >0 (ЗЛП в канонической форме на минимум, здесь т<п). Следующая ЗЛП (в стандартной форме на минимум)

ЪР + + bj>m = w -> min (ЗО)

при условиях

впР| + + а.А.гс1 (ЗЫ)

р*0, ...,/>_ О (32) называется сопряженной (или двойственной) к ЗЛП (26), (27.1) -(27.т), (28), которая называется исходной. Обе ЗЛП (исходная (26), (27.1) (27.т), (28) и сопряженная (30), (31.1) (З1.п), (32)) образуют двойственную пару ЗЛП. Сопряженная ЗЛП к сопряженной ЗЛП (30), (31.1) (З1.п), (32) совпадает с исходной ЗЛП (26), (27.1)

(27.т), (28). ЗЛП, сопряженная к ЗЛП (26), (29.1) (29.т), (28) в канонической форме, имеет вид (30), (31.1) (31.п). Здесь общие ограничения (32) не используются. Сопряженная к ЗЛП (30), (31.1)

(З1.п) совпадает с исходной ЗЛП (26), (29.1) (29.ni), (28).

Вопросы к главе 8

Что такое задача на условный экстремум?

Сопоставьте задачи на условный и абсолютный экстремум.

Напишите функцию Лагранжа.

Сформулируйте необходимое условие локального условного экстремума (аналитическая форма).

Сформулируйте необходимое условие локального условного экстремума (геометрическая форма).

Приведите формулировку задачи математического программирования.

Приведите формулировку задачи линейного программирования.