Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Рассмотрим задачу оптимального планирования производства [1]. Пусть предприятие выпускает n изделий, для производства которых используется m ингредиентов. Ингредиенты это – детали определенного сортамента, станки, работники, электроэнергия и т.д., иначе говоря, все что требуется для осуществления производственного цикла. Запасы ингредиентов задаются вектором b=(b1, b2,…, bm ), где bi - запас i-го ингридиента (i=1,…,m).
Задана матрица А, элемент которой aij определяет расход i-го ингридиента для производства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, задан вектор рыночных цен изделий p=(p1, p2,…, pn), где p - цена j-го изделия
(j=1,…,n).

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

|a11x1 + a12x2 + … + a1nxn (|
|b1 |
|a21x1 + a22x2 + … + a2nxn (|
|b2 |
|…………………………….……………………. |
|am1x1 + am2x2 + … + amnxn (|
|bm |
|xj ( 0, (j=1,…,n). |

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

Z= p1x1 + p2x2 + … + pnxn

Функция Z называется целевой. i-е ограничение из (1) означает, что нельзя израсходовать i-го ингредиента больше, чем имеется в наличии. Ограничения (1) задают множество
(. Переменные, удовлетворяющие условию 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), чтобы выполнялись условия:

|a11u1 + a21u2 + … + am1um (|
|p1 |
|a12u1 + a22u2 + … + am2um (|
|p2 |
|…………………………….……………………. |
|a1nu1 + a2nu2 + … + amnum (|
|pn |
|ui ( 0, (i=1,…,m) |

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

W=b1u1 + … + bmum

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

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

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

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

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

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

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

|a11x1 + a12x2 + … + a1nxn = |
|b1 |
|…………………………….……………………… |
|ak1x1 + ak2x2 + … + aknxn = |
|bk |
|ak+1, 1x1+ak+1, 2x2+…+ak+1, n|
|xn(bk+1 |
|…………………………….……………………… |
|am1x1 + am2x2 + … + amnxn ( |
|bm |
|xj ( 0, (j=1,…,n) |

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

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 в виде:

Рекомендуем скачать другие рефераты по теме: сочинение описание, банк курсовых.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата