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

Рассмотрим задачу оптимального планирования производства [1]. Пусть предприятие выпускает n изделий, для производства которых используется m ингредиентов. Ингредиенты это – детали определенного сортамента, станки, работники, электроэнергия и т.д., иначе говоря, все что требуется для осуществления производственного цикла. Запасы ингредиентов задаются вектором b=(b₁, b₂,…, b_m ), где b_i - запас i-го ингридиента (i=1,…,m). Задана матрица А, элемент которой a_ij определяет расход i-го ингридиента для производства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, задан вектор рыночных цен изделий p=(p₁, p₂,…, p_n), где p - цена j-го изделия (j=1,…,n).

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

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

Z= p₁x₁ + p₂x₂+ … + p_nx_n

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

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

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

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

Сформулируем двойственную к (1)-(1') задачу о приобритении ингридиентов по минимальной рыночной стоимости. Пусть то же самое предприятие, что и в задаче (1)-(1'), собирается приобрести на рынке m ингридиентов для производства тех же n изделий. При этом количество приобретаемых ингридиентов определяется вектором b=(b₁, b₂, …, b_m). Задана та же матрица А, элемент которой aij определяет расход i-го ингридиента для производства j-го изделия. Кроме того задан вектор цен p=(p₁, p₂, …, p_n) на продукцию предприятия. Требуется отыскать вектор цен ингридиентов u=(u₁, u₂, …, u_m), где u_i - цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялись условия:

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

W=b₁u₁ + … + b_mu_m

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

Условие несвободности u_j³0 означает, что j-й ингредиент либо бесплатен (u_j=0), либо стоит положительное количество рублей (u_j >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=p₁x₁ + p₂x₂ + … + p_nx_n

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

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

a_1j u₁ + a_2j u₂ + … + a_mj u_m =p_j

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

Условие несвободности отдельных или всех переменных здесь не отмечено. Обозначения:

a_{i, n+1} = b_i (i=1, …, m),

a_{m+1, j} = -p_j (j=1, …, n)

a_{m+1, n+1} = 0.

Таким образом, матрицу а мы дополнили столбцом свободных членов и строкой коэффициентов целевой функции, изменив знаки этих коэффициентов на противоположные. Тогда задачу (4) можно представить в виде таблицы. 1:

Прямая задача Таблица 1

Номера свободных переменных запоминаются отдельно.

Совместим таблицу двойственной задачи с таблицей. 1 и получим таблицу. 2.

Прямая и двойственная задачи Таблица 2

v_j - вспомогательные переменные двойственной задачи.

Тогда j-е ограничение из таблицы имеет вид:

v_j = a_1j u₁ + a_2j u₂ + … + a_mj u_m + a_{m+1, j} ³ 0, если x_j ³ 0

Если переменная x_j свободна, то ей соответствует ограничение-равенство двойственной задачи:

0=a_1j u₁ + a_2j u₂ + … + a_mj u_m + a_{m+1, j}

т.е. вместо v_j фактически будет нуль.

Кроме того первые k переменных двойственной задачи свободны, а остальные несвободны.

Целевая функция двойственной задачи

W= a_{1, n+1} u₁ + a_{2, n+1} u₂ + … + a_m, n+1 u_m + a_{m+1, n+1}

Совмещение в одной таблице прямой и двойственной задачи неслучайно. Решая прямую задачу, мы получаем о дновременно решение двойственной задачи, причем

max Z = min W = a_{m+1, n+1}

Сделаем замену переменных в таблице 1 , перебросив вспомогательную переменную y_r на верх таблицы со знаком минус, а основную пременную x_s на бок таблицы (a_rs¹0). Это означает движение из вершины x=(0, …, 0) в другую вершину многогранника W по его ребру. Элемент а_rs называется разрешающим, строка r - разрешающей строкой, столбец s - разрешающим столбцом. Такая замена переменных носит название модифицированных жордановых исключений (МЖИ). Элементы матрицы а, не принадлежащие разрешающему столбцу или разрешающей строке, назовем рядовыми.