Метод ветвей и границ решение задач целочисленного программирования

 

Министерство образования  и науки Калужской области

 

Государственное бюджетное  образовательное учреждение

среднего профессионального  образования Калужской области

«Сосенский радиотехнический техникум»

(ГБОУ СПО «СРТ»)

 

 

 

 

 

 

 

 

КУРСОВОЙ ПРОЕКТ

 

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

 

 

 

 

 

Разработал:

Группа:

Специальность: 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»

 

 

 

 

Руководитель:    

 

 

 

 

2013

 

Содержание

 

 

Введение

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

Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. Особый интерес к задачам ЦП вызван тем, что во многих практических задачах необходимо находить целочисленное решение ввиду дискретности ряда значений искомых переменных.

Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля  и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение. Поэтому разработаны специальные методы решения целочисленных задач.

Рекомендации по формулировке и решению ЦП

1. Количество целочисленных переменных уменьшать насколько возможно. Например, целочисленные переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные.
2. В отличие от общих задач ЛП, добавление новых ограничений особенно включающих целочисленные переменные, обычно уменьшают время решения задач ЦП.
3. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%. Тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы между верхней и нижней границ к верхней границы меньше 0,03.

Метод ветвей и границ можно применять для решения  задач нелинейного программирования

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

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

 

 

Основная часть

1.Теоретические основы

Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые  переменные должны принимать целые  значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. Особый интерес к задачам ЦП вызван тем, что во многих практических задачах необходимо находить целочисленное решение ввиду дискретности ряда значений искомых переменных.

В некоторых задачах линейного  программирования результат вычислений должен выражаться целым числом. Например, количество изготовленных автомобилей, изданных книг, собранных холодильников и т.д. Целевая функция и условия ограничений в таких задачах также выражаются целыми числами. Попытки решить задачу целочисленного программирования симплексным методом (или другими методами) приводят к тому, что решение получается в виде дробных чисел. Попытка округлить полученный результат до ближайшего целого числа приводит к тому, что найденное решение либо выходит за область допустимых решений, либо находится внутри этой области, и, как следствие, является или недопустимым или неоптимальным.

На рисунке 1 найдено решение  задачи линейного программирования в точке Х(5,6;4,8). При округлении до ближайшего целого числа получим решение

 Х(6;5),которое будет находиться  вне области допустимых решений.  При округлении полученного результата  в другую сторону получим Х(5;4),которое  не будет оптимальным. Очевидно, что оптимальное решение будет  в точке (5;5).

Учитывая то, что все целочисленные значения вектора решений лежат внутри области допустимых решений (ОДР) и, соответственно, имеют большие значения, нежели значения в вершинах ОДР, то и значение целевой функции будет несколько большим.

(0.1)

Математическая модель задач целочисленного программирования, наложенных ограничениях: при - целое, , .(0.2)

Задачу целочисленного программирования решают одним из методов

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

где символом ^ обозначена дробная часть числа, а символом ~ целая часть числа.

Если  - дробное число, а все - целые числа, то задача не имеет целочисленного решения.

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

Использование этого метода предполагает нахождение опорного решения одним  из методов линейного программирования, например симплексным методом. Затем поочередно одну из полученных нецелочисленных переменных, входящую в вектор решения, переводят в целочисленное значение и т.д., пока все переменные не примут целочисленное значение. При переводе каждой из переменных в целочисленное значение добавляют по одному ограничению и решают две задачи. Деление на две задачи не выполняется, если получено целочисленное решение или значение целевой функции получило меньшее значение, чем ранее зафиксированное значение. Метод «ветвей и границ» заканчивает свою работу, когда рассмотрены все нецелочисленные переменные, входящие в вектор решения, т.е. дальнейшее ветвление алгоритма невозможно.

Математическая модель задачи метода «ветвей и границ» представлена выражениями:

целевая функция:

при ограничениях: при - целое, , .

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

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

(0.3)

Во второй задаче дополнительное ограничение содержит округление до ближайшего большего целого значения:

(0.4)

Где символом обозначена дробная часть числа, а символом  ~ целая часть числа.

Суть метода ветвей и  границ – в направленном частичном  переборе допустимых решений. Будем рассматривать задачу линейного программирования.

 Рекомендации по формулировке и решению ЦП

Количество целочисленных  переменных уменьшать насколько  возможно. Например, целочисленные  переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные.

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

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

 Вначале она решается без ограничений на целочисленность. При этом находится верхняя граница F(x), так как целочисленное решение не может улучшить значение функции цели.

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

Ветвление производится последовательным введением дополнительных ограничений. Пусть x_k – целочисленная переменная, значение которой в оптимальном решении получилось дробным. Интервал [β_k] ≤ x_k ≤ [β_k ]+1 не содержит целочисленных компонентов решения. Поэтому допустимое целое значение x_k должно удовлетворять одному из неравенств x_k≥[β_k]+1 или x_k≤[β_k]. Это и есть дополнительные ограничения. Введение их в методе ветвей и границ на каждом шаге порождает две не связанные между собой подзадачи. Каждая подзадача решается как задача линейного программирования с исходной целевой функцией. После конечного числа шагов будет найдено целочисленное оптимальное решение.

 

Алгоритм метода ветвей и границ

1.Получить опорное решение.

2.Проверить, является ли полученное  решение целочисленным? Если «да», то перейти к шагу 11. Если «нет»,  то присвоить значению целевой  функции большое отрицательное значение и перейти к шагу 3.

3.Из вектора решения выбрать  переменную, имеющую наибольшее  нецелочисленное значение.

4.Определить дополнительное ограничение  для выбранной переменной и  выполнить ветвление алгоритма  на две задачи.

5.Выбрать очередную из двух задач. Проверить, просмотрен ли весь список задач? Если «да», то перейти к шагу 11. Если «нет», то перейти к шагу 6.

6.Найти оптимальное решение  очередной задачи.

7.Проверить полученное оптимальное  решение. Если найденное решение  лучше ранее зафиксированного результата, то перейти к шагу 9. Если найденное решение хуже ранее зафиксированного результата, то перейти к шагу 8.

8.Отказаться от дальнейшего  ветвления и перейти к шагу 5.

9.Проверить, является ли полученное  решение целочисленным. Если «да», то перейти к шагу 10. Если «нет», то перейти к шагу 3.

10.Запомнить вектор решения и  значение целевой функции и  перейти к шагу 5.

11.Проверить, равно ли значение  целевой функции ранее установленному  большому отрицательному значению (на шаге 2)? Если «да», то задача не имеет целочисленного решения. Если «нет», то перейти к шагу 12.

12.Вывести вектор решения и  значение целевой функции.[1]

Применение метода ветвей и границ рассмотрим на конкретном примере.

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

2.1Построить экономико-математическую  модель задачи:

Экономико-математическую модель данной задачи мы не строим, так  как она нам дана в условии  данной задачи.

Найти целочисленное  решение методом Ветвей и границ, если целевая функция  и ограничения

2.2 Математическая модель.

Целевая функция:

При ограничениях:

2.3 Входные данные.

Задача целочисленного программирования метода «Ветвей и  границ», предполагает, что входными данными в данной задачи являются: количество уравнений, количество переменных, стремление целевой функции(max или min).

2.4 Выходные данные.

 

На выходе данной задачи мы должны иметь значения переменных X(x1;x2;x3;x4); F(x).

2.5 Функциональные тесты

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

Решение: 1.Приведем задачу к каноническому виду

2.Найдем опорное решение  с помощью симплексного метода.

1 столбец {9}- 9*2=18

2 столбец {4,6; 6}- 4,5*3=13,5

3 столбец {4,5; 12}- 4,5*4=18

4 столбец {4}- 4*7=28 – max

Ведущий элемент 

 

1 столбец {9(min)}- 9*2=18

3 столбец {18, }- 18* -max

Ведущий элемент 

2 столбец {-4,5; (min)} (max)

Ответ: { }

F(x)=2*0+3*16,5+4*21+7*0=133,5

F(x)=133,5

Проверим  наш симплекс- метод в программе Microsoft Excel.

Переход к КЗЛП. 
F(X) = 2x₁ + 3x₂ + 4x₃ + 7x₄ → max при ограничениях: 
x₁ - 2x₂ + 2x₃ + x₄ <= 9 
2x₂ - x₃ + 3x₄ <= 12 
Для приведения ЗЛП к канонической форме необходимо: 
В 1-м неравенстве смысла ( <= ) вводим базисную переменную x₅. В 2-м неравенстве смысла ( <= ) вводим базисную переменную x₆.  
1x₁-2x₂ + 2x₃ + 1x₄ + 1x₅ + 0x₆ = 9 
0x₁ + 2x₂-1x₃ + 3x₄ + 0x₅ + 1x₆ = 12 
F(X) = 2x₁ + 3x₂ + 4x₃ + 7x₄ 
Переход к СЗЛП. 
Расширенная матрица системы ограничений-равенств данной задачи:

1 -2 2 1 1 0 9 0 2 -1 3 0 1 12

 
Поскольку в системе имеется единичная  матрица, то в качестве базисных переменных принимаем X = (1,6). 
Соответствующие уравнения имеют вид: 
x₁ - 2x₂ + 2x₃ + x₄ + x₅ = 9 
2x₂ - x₃ + 3x₄ + x₆ = 12 
Выразим базисные переменные через остальные: 
x₁ = 2x₂ - 2x₃ - x₄ - x₅+9 
x₆ = - 2x₂ + x₃ - 3x₄+12 
Подставим их в целевую функцию: 
F(X) = 2( 2x₂ - 2x₃ - x₄ - x₅+9) + 3x₂ + 4x₃ + 7x₄ 
или 
F(X) = 2x₁ + 3x₂ + 4x₃ + 7x₄+18 → max 
Система неравенств: 
2x₂ - 2x₃ - x₄ - x₅+9 >= 0 
- 2x₂ + x₃ - 3x₄+12 >= 0 
Приводим систему неравенств к следующему виду: 
- 2x₂ + 2x₃ + x₄ + x₅ <= 9 
2x₂ - x₃ + 3x₄ <= 12 
F(X) = 2x₁ + 3x₂ + 4x₃ + 7x₄+18 → max 
Упростим систему. 
- 2x₁ + 2x₂ + x₃ + x₄ <= 9 
2x₁ - x₂ + 3x₃ <= 12 
F(X) = 3x₁ + 4x₂ + 7x₃+18 → max 
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. 
Определим максимальное значение целевой функции F(X) = 3x₁ + 4x₂ + 7x₃+18 при следующих условиях-ограничений. 
При вычислениях значение Fc = 18 временно не учитываем. 
- 2x₁ + 2x₂ + x₃ + x₄ <= 9 
2x₁ - x₂ + 3x₃ <= 12 
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 
В 1-м неравенстве смысла ( <= ) вводим базисную переменную x₅. В 2-м неравенстве смысла ( <= ) вводим базисную переменную x₆.  
-2x₁ + 2x₂ + 1x₃ + 1x₄ + 1x₅ + 0x₆ = 9 
2x₁-1x₂ + 3x₃ + 0x₄ + 0x₅ + 1x₆ = 12 
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =	-2 2 1 1 1 0 2 -1 3 0 0 1

 
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. 
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. 
Решим систему уравнений относительно базисных переменных: 
x₅, x₆, 
Полагая, что свободные переменные равны 0, получим первый опорный план: 
X1 = (0,0,0,0,9,12) 
Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6
x5	9	-2	2	1	1	1	0
x6	12	2	-1	3	0	0	1
F(X0)	0	-3	-4	-7	0	0	0

 
Переходим к основному алгоритму  симплекс-метода. 
Итерация №0. 
1. Проверка критерия оптимальности. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
2. Определение новой базисной переменной. 
В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю. 
3. Определение новой свободной переменной. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 
и из них выберем наименьшее: 
min (9 : 1 , 12 : 3 ) = 4 
Следовательно, 2-ая строка является ведущей. 
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x5	9	-2	2	1	1	1	0	9
x6	12	2	-1	3	0	0	1	4
F(X1)	0	-3	-4	-7	0	0	0	0

 
4. Пересчет симплекс-таблицы. 
Формируем следующую часть симплексной таблицы. 
Вместо переменной x₆ в план 1 войдет переменная x₃. 
Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₆ плана 0 на разрешающий элемент РЭ=3 
На месте разрешающего элемента в плане 1 получаем 1. 
В остальных клетках столбца x₃ плана 1 записываем нули. 
Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃. 
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. 
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. 
НЭ = СЭ - (А*В)/РЭ 
СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. 
Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
9-(12 • 1):3	-2-(2 • 1):3	2-(-1 • 1):3	1-(3 • 1):3	1-(0 • 1):3	1-(0 • 1):3	0-(1 • 1):3
12 : 3	2 : 3	-1 : 3	3 : 3	0 : 3	0 : 3	1 : 3
0-(12 • -7):3	-3-(2 • -7):3	-4-(-1 • -7):3	-7-(3 • -7):3	0-(0 • -7):3	0-(0 • -7):3	0-(1 • -7):3

 
 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x5	5	-22/3	21/3	0	1	1	-1/3
x3	4	2/3	-1/3	1	0	0	1/3
F(X1)	28	12/3	-61/3	0	0	0	21/3

 
Итерация №1. 
1. Проверка критерия оптимальности. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
2. Определение новой базисной переменной. 
В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю. 
3. Определение новой свободной переменной. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 
и из них выберем наименьшее: 
min (5 : 2¹/₃ , - ) = 2¹/₇ 
Следовательно, 1-ая строка является ведущей. 
Разрешающий элемент равен (2¹/₃) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x5	5	-22/3		0	1	1	-1/3
x3	4	2/3	-1/3	1	0	0	1/3	-
F(X2)	28	12/3		0	0	0	21/3	0

 
4. Пересчет симплекс-таблицы. 
Формируем следующую часть симплексной таблицы. 
Вместо переменной x₅ в план 2 войдет переменная x₂. 
Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент РЭ=2¹/₃ 
На месте разрешающего элемента в плане 2 получаем 1. 
В остальных клетках столбца x₂ плана 2 записываем нули. 
Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂. 
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. 
Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
5 : 21/3	-22/3 : 21/3	21/3 : 21/3	0 : 21/3	1 : 21/3	1 : 21/3	-1/3 : 21/3
4-(5 • -1/3):21/3	2/3-(-22/3 • -1/3):21/3	-1/3-(21/3 • -1/3):21/3	1-(0 • -1/3):21/3	0-(1 • -1/3):21/3	0-(1 • -1/3):21/3	1/3-(-1/3 • -1/3):21/3
28-(5 • -61/3):21/3	12/3-(-22/3 • -61/3):21/3	-61/3-(21/3 • -61/3):21/3	0-(0 • -61/3):21/3	0-(1 • -61/3):21/3	0-(1 • -61/3):21/3	21/3-(-1/3 • -61/3):21/3

 
 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x2	21/7	-11/7	1	0	3/7	3/7	-1/7
x3	45/7	2/7	0	1	1/7	1/7	2/7
F(X2)	414/7	-54/7	0	0	25/7	25/7	13/7