Производственная задача — различия между версиями
Строка 1: | Строка 1: | ||
[[файл:ПЗ01.JPG|thumb|300|[[Математическая модель]] ПЗ]] | [[файл:ПЗ01.JPG|thumb|300|[[Математическая модель]] ПЗ]] | ||
[[файл:ПЗ03.JPG|thumb|300|Математическая модель эквивалентной ПЗ]] | [[файл:ПЗ03.JPG|thumb|300|Математическая модель эквивалентной ПЗ]] | ||
− | + | '''Производственная задача''' — задача [[линейное программирование|линейного программирования]]: определение плана производства изделий с максимальной стоимостью. | |
− | '''Производственная задача''' — задача линейного программирования: определение плана производства изделий с максимальной стоимостью. | + | |
− | + | ||
== Постановка задачи == | == Постановка задачи == | ||
Имеется '''n''' видов изделий и '''m''' видов ресурсов. Пусть заданы нормы '''a<sub>ij</sub>''' расхода '''i'''-го ресурса на производство '''j'''-го изделия и объёмы '''b<sub>i</sub>''' запасов '''i'''-го ресурса, '''i=1,2,…,m, j=1,2,…,n'''. Пусть известна для '''j'''-го изделия цена '''c<sub>j</sub>, j=1,2,…,n'''. Необходимо определить план производства изделий с максимальной стоимостью. Производственная задача (ПЗ) формулируется следующим образом: | Имеется '''n''' видов изделий и '''m''' видов ресурсов. Пусть заданы нормы '''a<sub>ij</sub>''' расхода '''i'''-го ресурса на производство '''j'''-го изделия и объёмы '''b<sub>i</sub>''' запасов '''i'''-го ресурса, '''i=1,2,…,m, j=1,2,…,n'''. Пусть известна для '''j'''-го изделия цена '''c<sub>j</sub>, j=1,2,…,n'''. Необходимо определить план производства изделий с максимальной стоимостью. Производственная задача (ПЗ) формулируется следующим образом: | ||
Строка 14: | Строка 12: | ||
где '''x<sub>j</sub>''' — объём выпуска '''j'''-го изделия, '''j=1,2,…,n'''. | где '''x<sub>j</sub>''' — объём выпуска '''j'''-го изделия, '''j=1,2,…,n'''. | ||
− | |||
== Постановка эквивалентной задачи == | == Постановка эквивалентной задачи == | ||
Для решения производственной задачи необходимо иметь ограничения в форме равенств. Введём новые переменные '''x<sub>j</sub>''' – остатки неиспользуемых ресурсов '''(j-n)'''-го вида, '''j=n+1,n+2,…,n+m'''. Добавим эти переменные к соответствующим ограничениям, и в результате получим эквивалентную задачу. | Для решения производственной задачи необходимо иметь ограничения в форме равенств. Введём новые переменные '''x<sub>j</sub>''' – остатки неиспользуемых ресурсов '''(j-n)'''-го вида, '''j=n+1,n+2,…,n+m'''. Добавим эти переменные к соответствующим ограничениям, и в результате получим эквивалентную задачу. | ||
Строка 25: | Строка 22: | ||
[[файл:ПЗ04.JPG]] | [[файл:ПЗ04.JPG]] | ||
− | |||
− | |||
== Метод решения == | == Метод решения == | ||
Эквивалентная производственная задача решается [[симплекс-метод]]ом. | Эквивалентная производственная задача решается [[симплекс-метод]]ом. | ||
Строка 33: | Строка 28: | ||
[[файл:ПЗ041.JPG]] | [[файл:ПЗ041.JPG]] | ||
− | |||
== Пример решения == | == Пример решения == | ||
[[файл:ПЗ05.JPG]] | [[файл:ПЗ05.JPG]] | ||
Строка 44: | Строка 38: | ||
Оптимальное решение производственной задачи '''x<sub>1</sub>=54, x<sub>2</sub>=24, L=2880'''. | Оптимальное решение производственной задачи '''x<sub>1</sub>=54, x<sub>2</sub>=24, L=2880'''. | ||
− | |||
== Другие задачи: == | == Другие задачи: == | ||
*[[Каноническая задача]]; | *[[Каноническая задача]]; | ||
Строка 56: | Строка 49: | ||
*[[Задача целочисленного программирования]]; | *[[Задача целочисленного программирования]]; | ||
*[[Задача о рюкзаке]]. | *[[Задача о рюкзаке]]. | ||
− | |||
== Ссылки == | == Ссылки == | ||
* Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963. | * Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]] | [[Категория:Линейное программирование]] |
Версия 05:23, 14 января 2016
Производственная задача — задача линейного программирования: определение плана производства изделий с максимальной стоимостью.
Содержание
Постановка задачи
Имеется n видов изделий и m видов ресурсов. Пусть заданы нормы aij расхода i-го ресурса на производство j-го изделия и объёмы bi запасов i-го ресурса, i=1,2,…,m, j=1,2,…,n. Пусть известна для j-го изделия цена cj, j=1,2,…,n. Необходимо определить план производства изделий с максимальной стоимостью. Производственная задача (ПЗ) формулируется следующим образом:
или
где xj — объём выпуска j-го изделия, j=1,2,…,n.
Постановка эквивалентной задачи
Для решения производственной задачи необходимо иметь ограничения в форме равенств. Введём новые переменные xj – остатки неиспользуемых ресурсов (j-n)-го вида, j=n+1,n+2,…,n+m. Добавим эти переменные к соответствующим ограничениям, и в результате получим эквивалентную задачу.
Математическая модель эквивалентной задачи принимает следующий вид:
или
Метод решения
Эквивалентная производственная задача решается симплекс-методом.
Начальная симплекс-таблица для эквивалентной задачи имеет вид:
Пример решения
Оптимальное решение эквивалентной задачи x1=54, x2=24, x3=0, x4=0, x5=77, L*=2880.
Оптимальное решение производственной задачи x1=54, x2=24, L=2880.
Другие задачи:
- Каноническая задача;
- Общая прямая задача линейного программирования;
- Общая двойственная задача линейного программирования;
- Транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Трёхиндексная транспортная задача;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Ссылки
- Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
- Участник:Logic-samara