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

Математическая модель ПЗ

Математическая модель эквивалентной ПЗ

Производственная задача — это задача линейного программирования определения плана производства изделий с максимальной стоимостью.

Постановка задачи

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

или

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

Постановка эквивалентной задачи

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

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

.

или

Метод решения

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

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

Пример решения

Оптимальное решение эквивалентной задачи x₁=54, x₂=24, x₃=0, x₄=0, x₅=77, L*=2880.

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

Другие задачи:

• Каноническая задача;
• Производственная задача;
• Общая прямая задача линейного программирования;
• Общая двойственная задача линейного программирования;
• Задачи транспортного типа;
• Задача целочисленного программирования;
• Задача о рюкзаке;
• Задача распределения средств;
• Задача замены оборудования.

Ссылки

• Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
• Участник:Logic-samara