Требуется составить такой план производства х=(х1, х2,…, хn), чтобы при выполнение условий

достигался максимум функции

Z= p1x1 + p2x2 + … + pnxn

Функция Z называется целевой.

i-е ограничение из (1) означает, что нельзя израсходовать i-го ингредиента больше, чем имеется в наличии. Ограничения (1) задают множество W. Переменные, удовлетворяющие условию xj³0, называются несвободными. В нашей задаче это означает, что при xj=0 - ничего не производится или при xj>0 производится некоторое количество изделий.

Переменные, на которые условия неотрицательности не накладываются, называются свободными.

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

Сформулируем двойственную к (1)-(1') задачу о приобритении ингридиентов по минимальной рыночной стоимости. Пусть то же самое предприятие, что и в задаче (1)-(1'), собирается приобрести на рынке m ингридиентов для производства тех же n изделий. При этом количество приобретаемых ингридиентов определяется вектором b=(b1, b2, …, bm). Задана та же матрица А, элемент которой aij определяет расход i-го ингридиента для производства j-го изделия. Кроме того задан вектор цен p=(p1, p2, …, pn) на продукцию предприятия. Требуется отыскать вектор цен ингридиентов u=(u1, u2, …, um), где ui - цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялись условия:

при достижении минимума целевой функции

W=b1u1 + … + bmum

j-ое условие (2) означает, что стоимость всех ингридиентов, идущ на производство j-го изделия, не меньше рыночной цены этого изделия.

Условие несвободности uj³0 означает, что j-й ингредиент либо бесплатен (uj=0), либо стоит положительное количество рублей (uj >0).

Опорным решением задачи (1)-(1') называется точка множества W, в которой не менее чем n ограничений из (1) обращается в верное равенство. Это - так называемая, угловая точка множества. Для n=2 это - вершина плоского угла.

Опорным решением задачи (2)-(2') называется точка, в которой не менее чем m ограничений из (2) обращается в верное равенство.

В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не является.

Опорное решение, доставляющее максимум функции (1') или минимум функции (2') называется оптимальным. В работе [1] показано, что оптимальное решение можно всегда искать среди опорных решений.

Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и равенства. Тогда условимся писать эти равенства первыми. Если их количество равно k, то область W запишется в виде:

Требуется найти максимум функции

Z=p1x1 + p2x2 + … + pnxn

В общем случае среди переменных xj могут быть свободные. Номера свободных переменных будем хранить в отдельном массиве.

При формировании двойственной задачи к задаче (3)-(3') i-му ограничению - равенству будет соответствовать свободная переменная ui (i=1,…,k), а свободной переменной xj ограничение - равенство:

a1j u1 + a2j u2 + … + amj um =pj

Введем вспомогательные переменные yi³0 (i=1,…,n) и запишем ограничения (3) и функцию Z в виде: