Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Задачи целочисленного программирования

Во многих практических задачах линейного программирования переменные по своему физического смыслу должны принимать только целочисленные значения. Такие задачи называют задачами целочисленного программирования.

Пусть требуется найти такое решение X=(x1, x2,…xn), при котором линейная функция принимает максимальное или минимальное значение при ограничениях

(2.54)

Методы целочисленной оптимизации можно разделить на 3 группы: методы отсечения, комбинаторные методы, приближенные методы. Из методов отсечения наиболее часто используется метода Гомори, из комбинаторных методов – метод ветвей и границ. Рассмотрим подробнее алгоритм метода отсечения Гомори.

1. Задача линейного программирования решается симплексным методом без учета условия целочисленности.

2. Если все компоненты оптимального решения целые, то решение является оптимальным и для задачи целочисленного программирования.

3. Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляют новое ограничение, удовлетворяющее следующим условиям: оно должно быть линейным, должно отсекать найденный оптимальный нецелочисленный план, не должно отсекать ни одного целочисленного решения. Такое ограничение называется правильным отсечением.

Пусть задача линейного программирования имеет конечный оптимум и на последнем шаге ее решения симплексным методом получены уравнения, выражающие основные переменные x1, x2,…xm через неосновные xm+1, xm+2,…xn оптимального решения:

(2.55)

Пусть в оптимальном решении – нецелая компонента. Тогда неравенство

(2.56)

где {} – дробная часть числа, обладает свойствами правильного отсечения.

4. Введением дополнительной неотрицательной переменной неравенство (2.56) преобразуется в уравнение

(2.57)

и включается в систему ограничений (2.54). Это равносильно добавлению уравнения (2.57) к системе (2.55).

5. Полученная расширенная задача решается симплексным методом. Если её оптимальное решение будет целочисленным, исходная задача решена. В противном случае алгоритм повторяется с п.3.

Если задача разрешима в целых числах, то оптимальный целочисленный план будет найден за конечное число шагов.

Если в процессе решения появится уравнение, выражающее основную переменную через неосновные, с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. Следовательно, и вся задача не имеет целочисленного оптимального решения.

Пример 12. Пусть имеется определенная сумма денег (20000 р.) и её можно потратить на покупку топлива. Поставщик продает топливо в емкостях двух различных объёмов: больших бочках по 200 литров и канистрах по 20 литров. Стоимость пустой тары: бочка – 600 р., канистра – 100 р. Стоимость литра топлива – 25 р. Необходимо определить оптимальное количество бочек и канистр, чтобы количество литров топлива в них было максимальным.



Решение. Составим математическую модель задачи.

Пусть x1 – количество бочек, x2 – количество канистр. Целевая функция: . Запишем ограничения:

(2.58)

Решая задачу симплексным методом без учета целочисленности переменных x1 и x2, получаем:

(2.59)

Решение является оптимальным, но нецелочисленным: .

Строим правильное отсечение:

. (2.60)

После добавления неравенства (2.60) к решению (2.59) и введения дополнительной переменной x4, имеем:

(2.61)

Продолжая решение симплексным методом, получаем:

(2.62)

Решение является оптимальным, но нецелочисленным: .

Строим правильное отсечение по уравнению, соответствующему нецелочисленной компоненте решения:

. (2.63)

После добавления неравенства (2.63) к решению (2.62) и введения дополнительной переменной x5, имеем:

(2.64)

Продолжая решение симплексным методом, получаем:

(2.65)

Получено оптимальное целочисленное решение: , Fmax=700.

Ответ: для покупки максимального количества топлива нужно купить 3 бочки и 5 канистр.

Замечание: неосновная переменная x4 не входит в выражение целевой функции на оптимальном решении, следовательно, ее изменение не изменяет значения Fmax. Но для того, чтобы решение оставалось допустимым, переменная x4 может принимать значения от 0 до ½. Только при x4=0 решение задачи является целочисленным.

Тема 3. Транспортная задача

<== предыдущая лекция | следующая лекция ==>
| Задачи целочисленного программирования

Дата добавления: 2014-01-06; Просмотров: 252; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.80.41.188
Генерация страницы за: 0.09 сек.