Обзор задач дискретного программирования

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент  равен (1) и находится на пересечении  ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	min
x1	12/3	1	2/3	1/3	0	21/2
x4	2	0	1	0	1	2
F(X2)	-81/3	0	2/3	-12/3	0	0

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

Базис	B	x1	x2	x3	x4
x1	1/3	1	0	1/3	-2/3
x2	2	0	1	0	1
F(X2)	-92/3	0	0	-12/3	-2/3

 

Конец: индексная  строка не содержит положительных элементов - найден оптимальный план

Оптимальный план можно записать так:

x₁ = ¹/₃

x₂ = 2

F(X) = -5•¹/₃ + -4•2 = -9²/₃

Метод Гомори.

В полученном оптимальном  плане присутствуют дробные числа.

Для переменной x, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью ²/₃, составляем дополнительное ограничение:

q₃ - q₃₁•x₁ - q₃₂•x₂ - q₃₃•x₃ - q₃₄•x₄≤0

Дополнительное  ограничение имеет вид:

^-2/₃-¹/₃x₃-¹/₃x₄≤0

Преобразуем полученное неравенство в уравнение:

^-2/₃-¹/₃x₃-¹/₃x₄ + x₅ = 0

коэффициенты  которого введем дополнительной строкой  в оптимальную симплексную таблицу.

Базис	B	x1	x2	x3	x4	x5
x1	1/3	1	0	1/3	-2/3	0
x2	2	0	1	0	1	0
x5	2/3	0	0	-1/3	-1/3	1
F(X0)	-92/3	0	0	-12/3	-2/3	0

 

В полученном оптимальном  плане присутствуют дробные числа.

Для переменной x₅, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью ²/₃, составляем дополнительное ограничение:

q₃ - q₃₁•x₁ - q₃₂•x₂ - q₃₃•x₃ - q₃₄•x₄ - q₃₅•x₅≤0

Дополнительное  ограничение имеет вид:

²/₃-²/₃x₃-²/₃x₄≤0

Преобразуем полученное неравенство в уравнение:

²/₃-²/₃x₃-²/₃x₄ + x₆ = 0

коэффициенты  которого введем дополнительной строкой в оптимальную симплексную таблицу.

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

 

План 0 в симплексной  таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении  ведущих строки и столбца находится  разрешающий элемент (РЭ), равный (^-2/₃).

Базис	B	x1	x2	x3	x4	x5	x6
x1	1/3	1	0	1/3	-2/3	0	0
x2	2	0	1	0	1	0	0
x5	2/3	0	0	-1/3	-1/3	1	0
x6	-2/3	0	0	-2/3	-2/3	0	1
F(X)	-92/3	0	0	-12/3	-2/3	0	0
θ	0	-	-	-12/3 : (-2/3) = 21/2	-2/3 : (-2/3) = 1	-	-

 

Выполняем преобразования симплексной таблицы.

Базис	B	x1	x2	x3	x4	x5	x6
x1	1	1	0	1	0	0	-1
x2	1	0	1	-1	0	0	11/2
x5	1	0	0	0	0	1	-1/2
x4	1	0	0	1	1	0	-11/2
F(X0)	-9	0	0	-1	0	0	-1

 

Решение получилось целочисленным. Оптимальный целочисленный  план можно записать так:

x₁ = 1

x₂ = 1

x₅ = 1

x₄ = 1

F(X) = -9

 

2.2.Пример  решения задачи методом ветвей  и границ.

Методом ветвей и границ найти решение задачи, состоящей  в определении максимального значения функции

F(X)=2х1+х2 _→ max. 
при условиях

xj – целые (j=1,2,3,4,5)

 

 

Решение.

Находим решение сформулированной задачи симплексным методом без  учета условия целочисленности  переменных. В результате устанавливаем, что такая задача имеет оптимальный план Х0= (18/5, 3/5, 0, 0, 24/5). При этом плане F= (X0)=39/5.

Так как в плане  Х₀ значения трех переменных являются дробными числами, то Х0 не удовлетворяет условию целочисленности, и следовательно, не является оптимальным планом исходной задачи.

Возьмем какую-нибудь переменную, значение которой является дробным  числом, например х1. Тогда эта переменная в оптимальном плане исходной задачи будет принимать значение, либо меньшее или равное трём:Х1≤3, либо больше или равно четырём: Х1≥4, .

Рассмотрим две задачи линейного программирования:

(I)          (II)

Задача (I) имеет оптимальный  план  на котором значение целевой функции  . Задача (II) неразрешима.

Исследуем задачу (I). Так  как среди компонент оптимального плана этой задачи есть дробные числа, то для одной из переменных, например x2, вводим дополнительные ограничения:

Рассмотрим теперь следующие  две задачи:

(III) 

(IV) 

Задача (IV) неразрешима, а  задача (III) имеет оптимальный план 

Х2 (3,1,3,3, 3), на котором значение целевой функции задачи 

Таким образом исходная задача целочисленного программирования имеет оптимальный план Х*= (3, 1, 2, 3, 3). При этом плане целевая функция  принимает максимальное значение  .

Схему реализованного выше вычислительного процесса можно представить в виде дерева, ветвями которого являются соответствующие ограничения на переменные, а вершинами – решения соответствующих задач линейного программирования. Как видно задача (I) имеет оптимальный план            (3, 3/2, 0, 9/2, 3/2), а задача (II) неразрешима. Поскольку среди компонент плана  есть дробные числа, выберем переменную х2 и рассмотрим задачи (III) (IV). Задача (III) имеет оптимальный план            (3, 1, 2, 3, 3) а задача (IV) неразрешима.

Итак, Х*= (3, 1, 2, 3, 3) является оптимальным планом задачи . При этом плане  .

Заключение.

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

Задачи этого  класса обладают следующими особенностями:

1.Нерегулярность,

2.Трудности  при определении окрестности,

3.Трудности нахождения допустимого целочисленного плана в задаче,

4.Невозможность   большого перебора на ЭВМ.

Также была приведена  классификация задач:

1.  Задачи с неделимостями, к которым  относятся задача о ранце

2. Экстремальные комбинаторные  задачи (Задача о назначениях, задача коммивояжёра, Задача о покрытии)

3. Задачи с разрывными целевыми функциями;

4. Задачи на невыпуклых и несвязных областях.

Были  рассмотрены методы решения задач (более подробно автор остановился  на  алгоритме Гомори и методе ветвей и границ, также были решены задачи этими способами).

Итак, дискретное программирование очень  важная часть оптимального программирования, которая имеет широкое практическое применение и заслуживает глубокого изучения.

 

 

Список литературы.

1. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. М.: ФИЗМАТЛИТ, 2007.

2. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.

3. Дроздов Н. Д. Алгоритмы дискретного программирования. Тверь 2000

 

4. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

 

5. Учебно-методические материалы для лабораторных и самостоятельных работ по курсу «Численные методы решения прикладных задач. Дискретное программирование. Комбинаторные методы» / Сост. Н. Д. Дроздов. - Калинин, 1990.