Производственная задача

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

Производственная задачазадача линейного программирования: определение плана производства изделий с максимальной стоимостью при заданных ограничениях по объемам ресурсов.

Содержание

[править] Постановка задачи

Имеется n видов изделий и m видов ресурсов. Пусть заданы нормы aij расхода i-го ресурса на производство j-го изделия и объёмы bi запасов i-го ресурса, i=1,2,…,m, j=1,2,…,n. Пусть известна для j-го изделия цена cj, j=1,2,…,n. Необходимо определить план производства изделий с максимальной стоимостью. Производственная задача (ПЗ) формулируется следующим образом:

[math]L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max[/math]
[math]\begin{cases}\sum\limits_{j=1}^n a_{ij}x_j \le b_i, \ \forall i\in N_m \\ x_j \ge 0, \forall j\in N_n\end{cases}[/math]

или

[math]L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max[/math]
[math]\begin{cases}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n \le b_1 \\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n \le b_2 \\ \ldots \\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n \le b_m \\ x_1 \ge 0, \ x_2 \ge 0, \ldots, \ x_n \ge 0 \end{cases}[/math]

где xj — объём выпуска j-го изделия, j=1,2,…,n.

[править] Постановка эквивалентной задачи

Для решения производственной задачи необходимо иметь ограничения в форме равенств. Введём новые переменные xj – остатки неиспользуемых ресурсов (j-n)-го вида, j=n+1,n+2,…,n+m. Добавим эти переменные к соответствующим ограничениям, и в результате получим эквивалентную задачу.

Математическая модель эквивалентной задачи принимает следующий вид:

[math]L^+(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max[/math]
[math]\begin{cases}\sum\limits_{j=1}^n a_{ij}x_j+x_{n+i}=b_i, \ \forall i\in N_m \\ x_j \ge 0, \forall j\in N_{n+m}\end{cases}[/math]

или

[math]L^+(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max[/math]
[math]\begin{cases}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n+x_{n+1}=b_1 \\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n+x_{n+2}=b_2 \\ \ldots \\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n+x_{n+m}=b_m \\ x_1 \ge 0, \ x_2 \ge 0, \ldots, \ x_{n+m} \ge 0 \end{cases}[/math]

[править] Метод решения

Эквивалентная производственная задача решается симплекс-методом.

Начальная симплекс-таблица для эквивалентной задачи имеет вид:

ПЗ041.JPG

[править] Пример решения

ПЗ05.JPG

ПЗ06.JPG

ПЗ07.JPG

Оптимальное решение эквивалентной задачи x1=54, x2=24, x3=0, x4=0, x5=77, L*=2880.

Оптимальное решение производственной задачи x1=54, x2=24, L=2880.

[править] Другие задачи:

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты