Название работы	Кол-во страниц	Размер
Теор., Теорема о предельном переходе в собственном интеграле зависящем...	1	154.85kb.
Пример Пример Пример 3	1	19.5kb.
Основные вопросы программы	1	124.59kb.
Основные теоремы о вычетах	1	127.15kb.
Решение задачи колмогорова-никольского для тригармонических интегралов...	1	59.51kb.
Решение задач оптимизации методом	1	53.98kb.
Исследовать на сходимость ряд	1	8.35kb.
2. Электростатическая теорема Гаусса. Пусть имеется вектор А	1	25.31kb.
Оптимизация windows 7	1	20.88kb.
Формирование у детей дошкольного возраста представлений о форме	1	200.74kb.
Задание 1 Решите следующую задачу методом Миля-Кентрелла: Пример	1	13.99kb.
Целочисленное программирование	3	550.73kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

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

План

1. 
   Постановка задачи
   
2. 
   Метод ветвления
   

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

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

Рассмотрим пример. Пусть имеется ряд предметов П₁, П₂, ..., П_n, которые необходимо вывести в случае аварийной ситуации. Известны стоимости этих предметов С₁, С₂, ..., С_n и их массы m₁, m₂, ..., m_n. Количество предметов, которые мы можем вывести лимитируется грузоподъемностью транспортного средства Q. Требуется из всего набора предметов выбрать наиболее ценный набор (с максимальной суммарной стоимостью предметов), вес которого укладывается в грузоподъемность Q.

Введем переменные x₁, x₂, ..., x_n, определяемые условиями:

• 
  x_j=1, если мы берем предмет П_j;
  
• 
  x_j= 0, если не берем.
  

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

(4.1)

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

(4.2)

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

(4.3)

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

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

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

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

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

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

Первый блок Б₁ имеет длину сигнальных цепей а₁₁ и длину цепей питания а₂₁. Показатель качества блоков Б₁ составляет K₁. Второй блок Б₂ имеет длину сигнальных цепей а₁₂ и длину цепей питания а₂₂. Его показатель каче­ства равен К₂. Требуется определить, каких блоков и сколь­ко нужно взять, чтобы качество прибора было максималь­ным.

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

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

(4.4)

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

(4.5)

где x₁ – число блоков Б₁;

x₂ – число блоков Б₂.

По условиям задачи известны следующие значения: N = 7; K₁ = 0,9; K₂ = 0,95; L₁ = 32; L₂ = 24; a₁₁ = 5,3; a₁₂ = 2; a₂₁ = 1,7; a₂₂ = 3. Подставив численные значения в (4.4) и (4.5), получим следующую задачу:

(4.6)

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

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

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

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

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

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

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

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

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