Метод искусственного базиса — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
|||
| Строка 1: | Строка 1: | ||
[[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]] | [[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]] | ||
[[файл:МИБ01.JPG|thumb|300|Математическая модель вспомогательной КЗ]] | [[файл:МИБ01.JPG|thumb|300|Математическая модель вспомогательной КЗ]] | ||
| − | |||
'''Метод искусственного базиса''' — метод нахождения опорного решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств. | '''Метод искусственного базиса''' — метод нахождения опорного решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств. | ||
| − | + | == Описание метода == | |
Суть метода искусственного базиса состоит в построении вспомогательной задачи с базисом и переходе к новому базису, подходящему для исходной задачи. | Суть метода искусственного базиса состоит в построении вспомогательной задачи с базисом и переходе к новому базису, подходящему для исходной задачи. | ||
| − | |||
== [[Каноническая задача]] == | == [[Каноническая задача]] == | ||
Математическая модель канонической задачи имеет следующий вид: | Математическая модель канонической задачи имеет следующий вид: | ||
| Строка 14: | Строка 12: | ||
[[файл:СМ02.JPG]] | [[файл:СМ02.JPG]] | ||
| − | |||
== Постановка вспомогательной задачи == | == Постановка вспомогательной задачи == | ||
Для нахождения опорного решения задачи канонического вида необходимо составить вспомогательную задачу. Введём новые (искусственные) переменные '''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: | ||
[[файл:МИБ02.JPG]] | [[файл:МИБ02.JPG]] | ||
| − | |||
== Метод решения == | == Метод решения == | ||
Вспомогательная задача решается [[симплекс-метод]]ом. | Вспомогательная задача решается [[симплекс-метод]]ом. | ||
| Строка 35: | Строка 31: | ||
Далее, заменив в симплекс-таблице коэффициенты целевой функции на значения исходной задачи и пересчитав значения оценок '''Δ<sub>j</sub>''', можно решать исходную задачу симплекс-методом. | Далее, заменив в симплекс-таблице коэффициенты целевой функции на значения исходной задачи и пересчитав значения оценок '''Δ<sub>j</sub>''', можно решать исходную задачу симплекс-методом. | ||
В случае если оптимальное значение целевой функции вспомогательной задачи не равно нулю, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений. | В случае если оптимальное значение целевой функции вспомогательной задачи не равно нулю, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений. | ||
| − | |||
== Другие методы: == | == Другие методы: == | ||
*[[Симплекс-метод]]; | *[[Симплекс-метод]]; | ||
*[[М-метод]]. | *[[М-метод]]. | ||
| − | |||
== Ссылки == | == Ссылки == | ||
* Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963. | * Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]] | [[Категория:Линейное программирование]] | ||
Версия 05:40, 14 января 2016
Метод искусственного базиса — метод нахождения опорного решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.
Содержание
Описание метода
Суть метода искусственного базиса состоит в построении вспомогательной задачи с базисом и переходе к новому базису, подходящему для исходной задачи.
Каноническая задача
Математическая модель канонической задачи имеет следующий вид:
или
Постановка вспомогательной задачи
Для нахождения опорного решения задачи канонического вида необходимо составить вспомогательную задачу. Введём новые (искусственные) переменные xj – остатки ресурсов (j-n)-го ограничения, j=n+1,n+2,…,n+m. Добавим эти переменные к соответствующим ограничениям, введём новую целевую функцию равную сумме остатков ресурсов ограничений, в результате получим вспомогательную задачу.
Математическая модель вспомогательной задачи имеет следующий вид:
.
или
Метод решения
Вспомогательная задача решается симплекс-методом.
Начальная симплекс-таблица для вспомогательной задачи имеет вид:
Если оптимальное значение целевой функции вспомогательной задачи равно нулю, то получено решение, которое при отбрасывании искусственных переменных совпадает с опорным решением исходной задачи канонического вида, причём расширенная матрица коэффициентов симплекс-таблицы вспомогательной задачи в части без искусственных переменных совпадает с расширенной матрицей коэффициентов симплекс-таблицы исходной задачи. Далее, заменив в симплекс-таблице коэффициенты целевой функции на значения исходной задачи и пересчитав значения оценок Δj, можно решать исходную задачу симплекс-методом. В случае если оптимальное значение целевой функции вспомогательной задачи не равно нулю, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений.
Другие методы:
Ссылки
- Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
- Участник:Logic-samara
