Автор работы: Пользователь скрыл имя, 07 Ноября 2014 в 23:25, реферат
Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики - главным образом в работах американских математиков Дж.Данцига и Р.Гомори. Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации ,прежде всего линейного программирования. Однако, в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.
Введение.
1.Целочисленное программирование. Общие понятия.
2.Метод Гомори.
3.Метод ветвей и границ.
4.Циклический алгоритм целочисленного программирования.
5.Полностью целочисленный алгоритм.
6.Задача о рюкзаке.
7.Задача о назначении.
8.Задача коммивояжера.
Заключение.
Список используемой литературы.
Другое замечание касается того, что если величина λ, получаемая указанным выше способом, может быть увеличена так, чтобы [a0/λ] и [aj/λ] (аj > 0) оставались без изменения, то отсечение Гомори можно усилить, несмотря на то, что нулевой столбец -уменьшится на ту же величину.
Выпишем производящую строку
Чем больше величина λ, тем меньше абсолютная величина коэффициентов отсечения. Естественно, что мы хотели бы иметь абсолютную величину [a0/λ] большой, а абсолютные величины [aj/λ] — малыми. Если значение λ (полученное по приведенному выше правилу) может быть увеличено так, чтобы значения [aj/λ [] и [a0/λ] не изменялись, то используется большее значение для λ. Тем самым по возможности уменьшится абсолютная величина [aj/λ] для некоторых j, и отсечение станет сильнее.
Например, пусть целевая функция имеет вид
X0= - 20 – x1- 2x2 – 3x2 – x4 ,
И производящая строка
X= -20+ (-7) (-x1)+ (-8) (-x2)+ (-15) (-x3)+18 (-x4).
Используя описанную выше процедуру выбора λ, получим λ = 7. Соответствующее отсечение
s = -3 + x1 + 2x2 + Зx3 — 2x4≥ 0.
Если использовать λ = 9 вместо λ = 7, получим отсечение
s* = -3 + x1 + x2 + 2x3 — 2x4 ≥ О,
являющееся более сильным .
Интересная особенность полностью целочисленного алгоритма состоит в том, что для его использования не обязательно требовать целочисленности всех аij. Пусть задача целочисленного программирования имеет вид
максимизировать
при условиях
xn+i= ai0 - ∑aijxj ≥0 (i=1,………,m)
где a 00 и cj — целые, аi0 о и аij могут быть произвольными действительными числами. Таблица 14.1 содержит в первых n + 1 строках только целые числа.
Выпишем произвольную производящую строку (опуская обозначение строки)
Вне зависимости от того, являются ли a0 и aj целыми ли действительными, коэффициенты отсечения сегда целые, а ведущий элемент равен —1. В результате итерации с таким ведущим элементом первые n+1 строк таблицы останутся целочисленными. Заметим, что переменная s — неотрицательная целая. В силу приведенных рассуждений доказательство конечности в данном случае мало чем отличается от описанного выше. Когда в нулевом столбце ai0 == 1, . . ., n)становятся неотрицательными целыми, а остальные элементы нулевого столбца — неотрицательными, то получается оптимальное решение.
В последних главах были обсуждены два алгоритма целочисленного программирования, первый из которых называется циклическим алгоритмом (λ = 1), а второй — полностью целочисленным (λ > 1).
Задача о рюкзаке
Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса.
Модель задачи примет вид:
при ограничениях на вместимости отсеков
условии неотрицательности
условии целочисленности
- целые .
Когда для перевозки имеется один отсек и каждый вид продукции может быть взят или нет, то модель задачи принимает вид:
.
Задача о назначении
Имеет n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-й работы . Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должне быть закреплен только один исполнитель.
Математическая модель задачи примет вид:
Каждый исполнитель назначается только на одну работу:
На каждую работу назначается только один исполнитель:
Условия неотрицательности и целочисленности
, .
Задача коммивояжера
Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.
Математическая модель задачи:
Условия неотрицательности и целочисленности
, .
Добавляется условие прохождение маршрута через все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках.
Заключение.
В данной работе была рассмотрена сущность целочисленного программирования. Затронуты специальные методы решения целочисленных задач. Такие задачи возникают при моделировании разнообразных производственно-экономических, технических, военных и других ситуаций. В то же время ряд проблем самой математики может быть сформулирован как целочисленные экстремальные задачи.
Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций , возникающих в экономике, технике, военном деле и других областях. Эти задачи интересны и с математической точки зрения. С появлением ЭВМ, ростом их производительности повысился интерес к задачам такого типа и к математике в целом.
Список использованной литературы:
1 Символ (≡) означает «сравнимость».
2 Если λ > 1, то для получения отсечения (10) из (4) требуется только неотрицательность левой части уравнения (4). Следовательно, любая положительная линейная комбинация строк таблицы может служить производящей строкой.