Решение задачи. Рассмотрим пример. Пусть имеется ряд предметов П1, П2, Пn - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Решение задачи. Рассмотрим пример. Пусть имеется ряд предметов П1, П2, Пn - страница №1/1

Тема 5 Целочисленное программирование


План

  1. Постановка задачи

  2. Метод ветвления

1 Постановка задачи


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

Рассмотрим пример. Пусть имеется ряд предметов П1, П2, ..., Пn, которые необходимо вывести в случае аварийной ситуации. Известны стоимости этих предметов С1, С2, ..., Сn и их массы m1, m2, ..., mn. Количество предметов, которые мы можем вывести лимитируется грузоподъемностью транспортного средства Q. Требуется из всего набора предметов выбрать наиболее ценный набор (с максимальной суммарной стоимостью предметов), вес которого укладывается в грузоподъемность Q.

Введем переменные x1, x2, ..., xn, определяемые условиями:



  • xj=1, если мы берем предмет Пj;

  • xj= 0, если не берем.

Условие ограниченной грузоподъемности запишется в виде неравенства

(4.1)

Теперь запишем общую стоимость предметов, которую мы хотим максимизировать



(4.2)

Таким образом, задача на вид почти не отличается о задачи линейного программирования. Формулируется она следующим образом: найти неотрицательные целые значения переменных x1, x2, ..., xn, которые удовлетворяют линейным неравенствам-ограничениям и обращают линейную функцию этих переменных в максимум (минимум)



(4.3)

Существуют задачи смешанно-целочисленного программирования (частично-целочисленного программирования) – это задачи с требованием целочисленности только для некоторых переменных.

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

2 Метод ветвления


Суть метода заключается в следующем:

  • отбросив условие целочисленности, решаем задачу линейного программирования;

  • накладываем условие целочисленности на элементы решения с последующей проверкой результатов по количественным значениям целевой функции и выполнением ограничений (FЦ – значение целевой функции для задачи целочисленного программирования, FЛ – значение целевой функции для задачи линейного программирования).

Метод ветвления рассмотрим на примере решения одной из задач конструкторского проектирования. Предположим, что в распоряжении конструктора есть два вида блоков (Б1 и Б2), реализующих одни и те же вычислительные функции, но имеющих различный монтаж и разные показа­тели качества. Известно, что для конструирования прибора требуется не менее N таких блоков.

Первый блок Б1 имеет длину сигнальных цепей а11 и длину цепей питания а21. Показатель качества блоков Б1 составляет K1. Второй блок Б2 имеет длину сигнальных цепей а12 и длину цепей питания а22. Его показатель каче­ства равен К2. Требуется определить, каких блоков и сколь­ко нужно взять, чтобы качество прибора было максималь­ным.

На решение задачи наложены ограничения по длинам сигнальных цепей и цепей питания. Общая длина сигналь­ных цепей, определяющих быстродействие прибора, не должна превышать Ll, а цепей питания – L2.

Математическое описание задачи состоит из целевой функции



(4.4)

и ограничений



(4.5)

где x1 – число блоков Б1;



x2 – число блоков Б2.

По условиям задачи известны следующие значения: N = 7; K1 = 0,9; K2 = 0,95; L1 = 32; L2 = 24; a11 = 5,3; a12 = 2; a21 = 1,7; a22 = 3. Подставив численные значения в (4.4) и (4.5), получим следующую задачу:



(4.6)

Отбросим условие целочисленности и решим задачу линейного программирования графическим методом (Рис. 4.1). Оптимальным решением задачи линейного программирования являются х1опт = 3,8 и х2опт = 5,8 – не целые числа.

Находим значение целевой функции для задачи линейного программирования

Целочисленные решения должны иметь меньшее значение целевой функции, т. е. .

Метод ветвления является итерационным. На каждой итерации следует задаться целыми значениями элементов решения и проверить условия выполнимости решения, при котором .



Первая итерация. Задаемся значениями х1 = 3 и х1* = 4, значение х2 = 5,8 оставим неизменным. Проверяем выполнимость решения задачи:

Значение х1* отбрасывает, так как .



Вторая итерация. Принимаем значение х1 = 3, полагаем х2 = 5 или х2* = 6 и проверяем выполнимость решения задачи:

Оба полученных решения выполнимы. Принимаем то из них, которое дает наибольшее значение целевой функции. Следовательно, решением задачи является х1 = 3, х2 = 6, которое обеспечивает максимальное значение целевой функции К = 8,4.

Алгоритм метода ветвления изображен на рисунке 4.2.



ММОКЕОЗ, Тема 4