Студопедия

КАТЕГОРИИ:


Архитектура-(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)

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

Читайте также:
  1. I и II задачи имеют решение.
  2. II. Цели, задачи и принципы студенческого самоуправления
  3. Алгоритм решения задачи 2.
  4. Алгоритм решения задачи 3.
  5. Алгоритм решения канонической задачи ЛП симплексным методом.
  6. Алгоритм, записанный на языке программирования называется программой.
  7. Базовые элементы языка программирования.
  8. ВВЕДЕНИЕ. ПРЕДМЕТ И ЗАДАЧИ КУРСА
  9. Виды и задачи аудита
  10. Вопрос 1. Сущность, цели и задачи финансовой политики государства
  11. Вопрос 1. Функции, задачи и цели финансового менеджмента
  12. Вопрос 1: Определить сущность, предмет и задачи педагогики как гуманитарной науки. Сформулировать основные педагогические категории

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

Пусть требуется найти такое решение 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; Просмотров: 295; Нарушение авторских прав?;


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



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


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



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