Решение задачи нахождения минимума целевой функции
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
p>
Запишем систему ограничений в виде равенств, для решения алгебраическим методом.
В результате решения найден оптимальный план задачи: х1 =9/4, х2 = 5/2, F =-41/4. Это решения не отвечает условию целочисленности, поставленному в задаче. Разобьем исходный многоугольник решений на две области, исключив из него область 3<x1<4. Новый многоугольник решений представлен на рисунке ниже.
Измененный многоугольник решений задачи
Составим новые системы ограничений для образовавшихся областей многоугольника решений. Левая область представляет собой четырехугольник (трапецию). Система ограничений для левой области многоугольника решений представлена ниже.
Система ограничений для левой области
Правая область представляет собой точку С.
Система ограничений для правой области решений представлена ниже.
Новые системы ограничений представляют из себя две вспомогательные задачи, которые необходимо решить независимо друг от друга. Решим задачу целочисленного программирования для левой области многоугольника решений.
,
В результате решения найден оптимальный план задачи: х1 = 3, х2 = 3, F = -12. Этот план удовлетворяет условию целочисленности переменных в задаче и может быть принят в качестве оптимального опорного плана для исходной задачи целочисленного линейного программирования. Проводить решение для правой области решений нет смысла. На рисунке ниже представлен ход решения целочисленной задачи линейного программирования в виде дерева.
Ход решения целочисленной задачи линейного программирования методом Гомори.
Во многих практических приложениях представляет большой интерес задача целочисленного программирования, в которой дана система линейных неравенств и линейная форма
Требуется найти целочисленное решение системы (1), которое минимизирует целевую функцию F, причем, все коэффициенты - целые.
Один из методов решения задачи целочисленного программирования предложен Гомори. Идея метода заключается в использовании методов непрерывного линейного программирования, в частности, симплекс-метода.
)Определяется с помощью симплекс-метода решение задачи (1), (2), у которой снято требование целочисленности решения; если решение оказывается целочисленным, то искомое решение целочисленной задачи будет также найдено;
) В противном случае, если некоторая координата - не целая, полученное решение задачи проверяется на возможность существования целочисленного решения (наличие целых точек в допустимом многограннике):
если в какой-либо строке с дробным свободным членом , все остальные коэффициенты окажутся целыми, то в допустимом многограннике нет целых, точек и задача целочисленного программирования решения не имеет;
в противном случае вводится дополнительное линейное ограничение, которое отсекает от допустимого многогранника часть, бесперспективную для поиска решения задачи целочисленного программирования;
) Для построения дополнительного линейного ограничения, выбираем l-тую строку с дробным свободным членом и записываем дополнительное ограничение
где и - соответственно дробные части коэффициентов и свободного
члена . Введем в ограничение (3) вспомогательную переменную :
(4)
Определим коэффициенты и , входящие в ограничение (4):
(5)
где и - ближайшие целые снизу для и соответственно.
) Далее с помощью симплекс-метода снова решается задача линейного программирования при наличии дополнительного ограничения и т.д.
Гомори доказал, что конечное число подобных шагов приводит к такой задаче линейного программирования, решение которой будет целочисленным и, следовательно, искомым.
Решение: Приведем систему линейных ограничений и функцию цели к канонической форме:
Определим оптимальное решение системы линейных ограничений, временно отбросив условие целочисленности. Используем для этого симплекс-метод. Ниже последовательно в таблицах представлены исходное решение задачи, и приведены преобразования исходной таблицы с целью получения оптимального решения задачи:
Решение булевских задач ЛП методом Балаша.
Составить самостоятельно вариант для задачи целочисленного линейного программирования с булевскими переменными с учетом следующих правил: в задаче используется не менее 5 переменных, не менее 4 ограничений, коэффициенты ограничений и целевой функции выбираются произвольно, но таким образом, чтобы система ограничений была совместна. Задание состоит в том, чтобы решить ЗЦЛП с булевскими переменными, используя алгоритм Балаша и определить снижение трудоемкости вычислений по отношению к решению задачи методом полного перебора.
№x4x3x2x1x5Выполнение ограниченийЗначение F0123451000000Fф=020000144300010174000116150010013600101577001103080011174901000-10+++++Fф=-1010010013411010107120101151130110031401101471501110201601111641710000-49+++++Fф=-491810001-51910010-3220100112110100-36221010182310110-19241011125251100-59+++++Fф=-592611001-152711010-42281101122911100-463011101-23111110-29321111115
Фильтрующее ограничение:
Определение снижения трудоемкости вычислений
Решение задачи методом полного перебора составляет 6*25=192 вычисленных выражения. Решение задачи методом Балаша составляет 3*6+(25-3)=47 вычисленных выражений. Итого снижение трудоемкости вычислений по отношению к решению задачи методом полного перебор?/p>