Задача целочисленного программирования — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
|||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
[[файл:ЗЦП01.JPG|thumb|300|[[Математическая модель]] ЗЦП]] | [[файл:ЗЦП01.JPG|thumb|300|[[Математическая модель]] ЗЦП]] | ||
| − | |||
'''Задача целочисленного программирования''' — это основная задача целочисленного программирования. | '''Задача целочисленного программирования''' — это основная задача целочисленного программирования. | ||
| − | |||
== [[Математическая модель]] == | == [[Математическая модель]] == | ||
Математическая модель задачи целочисленного программирования имеет следующий вид: | Математическая модель задачи целочисленного программирования имеет следующий вид: | ||
| Строка 11: | Строка 9: | ||
[[файл:ЗЦП02.JPG]] | [[файл:ЗЦП02.JPG]] | ||
| − | |||
== Метод решения == | == Метод решения == | ||
Задача целочисленного программирования решается '''методом Гомори'''. | Задача целочисленного программирования решается '''методом Гомори'''. | ||
| Строка 30: | Строка 27: | ||
Повторяя процедуру добавления ограничения отсечения и решения вспомогательной задачи, в конце получаем оптимальное целочисленное решение. | Повторяя процедуру добавления ограничения отсечения и решения вспомогательной задачи, в конце получаем оптимальное целочисленное решение. | ||
| − | |||
== Пример решения == | == Пример решения == | ||
Задача целочисленного программирования имеет вид: | Задача целочисленного программирования имеет вид: | ||
| Строка 67: | Строка 63: | ||
Оптимальное решение задачи целочисленного программирования '''x<sub>1</sub>=5, x<sub>2</sub>=2, L<sup>ц </sup>=38'''. | Оптимальное решение задачи целочисленного программирования '''x<sub>1</sub>=5, x<sub>2</sub>=2, L<sup>ц </sup>=38'''. | ||
| − | |||
== Другие задачи: == | == Другие задачи: == | ||
| − | + | {{Список ЗМП}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Ссылки == | == Ссылки == | ||
* Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование, «Наука», М., 1969. | * Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование, «Наука», М., 1969. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Целочисленное программирование]][[Категория:Линейное программирование]] | [[Категория:Целочисленное программирование]][[Категория:Линейное программирование]] | ||
Текущая версия на 12:50, 29 сентября 2016
Задача целочисленного программирования — это основная задача целочисленного программирования.
Математическая модель
Математическая модель задачи целочисленного программирования имеет следующий вид:
или
Метод решения
Задача целочисленного программирования решается методом Гомори. Суть метода состоит в первоначальном решении симплекс-методом вспомогательной задачи линейного программирования (без ограничения целочисленности) вида:
или
.
Затем для нецелочисленной переменной оптимального решения вспомогательной задачи составляется ограничение отсечения и вновь решается вспомогательная задача, но уже М-методом. Причём если в r-ой строке последней симплекс-таблицы базисная переменная не является целочисленной (а она должна быть целочисленной по условию задачи), то составляется ограничение отсечения вида:
, где
{arj}=arj-[arj] - дробная часть числа.
Повторяя процедуру добавления ограничения отсечения и решения вспомогательной задачи, в конце получаем оптимальное целочисленное решение.
Пример решения
Задача целочисленного программирования имеет вид:
Строим вспомогательную задачу линейного программирования (без ограничения целочисленности):
Вспомогательную задачу приводим к каноническому виду:
Решаем первую вспомогательную задачу симплекс-методом:
Составляем первое ограничение отсечения (в ограничении используются десятичные дроби):
Решаем вторую вспомогательную задачу М-методом:
Составляем второе ограничение отсечения (в ограничении используются правильные дроби):
Решаем третью вспомогательную задачу М-методом:
Оптимальное решение последней вспомогательной задачи x1=5, x2=2, x3=0, x4=7, x5=4, x6=1, x7=0, x8=0, L=38.
Оптимальное решение задачи целочисленного программирования x1=5, x2=2, Lц =38.
Другие задачи:
Ссылки
- Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование, «Наука», М., 1969.
- Участник:Logic-samara
