Для выполнения лабораторной работы № 4

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

__________________________________

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

КОЛОМЕНСКИЙ ИНСТИТУТ

"УТВЕРЖДЕНО" Учебно-методическим Советом КИ МГОУ Председатель Совета _____________________            А.М. Липатов "___"__________1999 г.

Трушков А.С.

ИНСТРУКЦИЯ

Для выполнения лабораторной работы № 4

По математическому программированию

РЕШЕНИЕ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО

ПРОГРАММИРОВАНИЯ

Г. Коломна

Г.

Содержание

1.	Введение ………………………………………………………………………...	2
2.	Метод отсекающих плоскостей (метод Гомори) ……………………………..	2
3.	Метод ветвей и границ …………………………………………………………	7
4.	Задание к лабораторной работе ………………………………………………..	8
5.	Типовой отчет к лабораторной работе ………………………………………..	9
6.	Литература ………………………………………………………………………	17

Введение

Лабораторная работа выполняется с помощью программы "Решение и моделирование задач линейного программирования" /1/ и "Решение задач целочисленного программирования". Программы написаны на алгоритмическом языке Visual Basic for Application (VBA) и оформлены в виде модуля табличного процессора Excel 97. Программа "Решение за"Решение и моделирование задач линейного программирования" дач целочисленного программирования" позволяет решать задачи линейного целочисленного программирования методом отсечений Гомори. Целью лабораторной работы в курсе “Математического программирования” является решение задач целочисленного программирования методом ветвей и границ с помощью программы "Решение и моделирование задач линейного программирования", а также освоение программы "Решение задач целочисленного программирования".

 

Метод отсекающих плоскостей (метод Гомори)

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

 

 

Пример:

           max z = 7x₁ + 9x₂

                 -x₁ + 3x₂ £ 6

                 7x₁ + x₂ £ 35

                   x_i ³ 0 - целые

Решаем задачу без условия целочисленности. Получаем следующую оптимальную симплекс-таблицу:

 

БП	х1	х2	х3	х4	Решение
z	0	0	28/11	15/11	63
х2	0	1	7/22	1/22	7/2
х1	1	0	-1/22	3/22	9/2

В качестве производящей строки отсечения Гомори можно выбрать любую с нецелым значением базисной переменной. Обычно выбирается та, которой соответствует max {f_i}, где f_i - дробные части значений базисных переменных. Для полученной таблицы:

f₁ = [ х₁ ] = 1/2; f₂ = [ х ₂ ] = f₂ = 1/2.

Выберем переменную x₂ и связанную с ней строку в качестве производящей. Уравнение, связанное с переменной x₂  имеет вид:

x₂  + 7/22 x₃ + 1/22 x₄ = 7/2.

Составим отсечение Гомори:

S_i - å f_ij w_j = -f_i,

где f₂₃ = 7/22; f₂₄ = 1/22. Таким образом, получаем следующее уравнение:

S_i - 7/22 x₃ -1/22 x₄ = -1/2.

Включаем это отсечение в симплекс-таблицу. Новая таблица имеет вид:

 

БП	х1	x 2	x3	x4	S1	Реш.
z	0	0	28/11	15/11	0	63
x 2	0	1	7/22	1/22	0	7/2
x 1	1	0	-1/22	3/22	0	9/2
S 1	0	0	-7/22	-1/22	1	-1/2

Двойственным симплекс-методом находим оптимальное решение задачи (за 1 итерацию):

 

БП	х1	x 2	x3	x4	S1	Реш.
z	0	0	0	1	8	59
x 2	0	1	0	0	1	3
x 1	1	0	0	1 /7	-1/7	32/7
x 3	0	0	1	1/7	-22/7	11/4

Для переменной х₁ нарушается условие целочисленности. В качестве производящей выбирается связанная с х₁ строка. Ей соответствует уравнение:

х₁ + 1/7х₄ - 1/7S₁  = 32/7.

Дробные части коэффициентов равны:

f₁₄ = 1/7; f_1S = 6/7; f₁ = 4/7.

Значит уравнение для отсечения Гомори имеет вид:

S₂ - 1/7x₄ - 6/7S₁ = - 4/7

Включаем это отсечение в симплекс-таблицу. Новая таблица имеет вид:

БП	x 1	x 2	x3	x4	S1	S2	Реш.
z	0	0	0	1	8	0	59
x2	0	1	0	0	1	0	3
x1	1	0	0	1/7	-1/7	0	32/7
x3	0	0	1	1/7	-22/7	0	11/7
S 2	0	0	0	-1/7	-6/7	1	-4/7

Двойственным симплекс-методом находим оптимальное решение задачи (за 1 итерацию):

БП	x 1	x 2	x3	x4	S1	S2	Реш.
z	0	0	0	0	2	7	55
x2	0	1	0	0	1	0	3
x1	1	0	0	0	-1	1	4
x3	0	0	1	0	-4	1	1
x 4	0	0	0	1	6	-7	4

Целочисленность переменных достигнута. Следовательно, данная таблица содержит решение задачи: z = 55, x ₁ = 4, x ₂ =3.

Метод ветвей и границ.

 

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

Сначала решается ЗЛП без условия целочисленности переменных. Пусть переменная x_r - целочисленная переменная, которая в оптимальном решении ЗЛП без условия целочисленности принимает дробное значение x_r ^*. Очевидно, что интервал значений [x_r ^* ] < x_r < [x_r ^* ] + 1 не содержит оптимального решения задачи. Значит оптимальное решение задачи должно удовлетворять одному из неравенств:

x_r £ [x_r ^* ] или x_r ³ [x_r ^* ] + 1.

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

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

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

Пример. Решить полностью целочисленную задачу:

           max z=2x₁ + 3x₂

           5x₁  + 7x₂ £ 35

           4x₁  + 9x₂ £ 36                                                                                      

            x_i ³ 0 - целые

Сначала решаем ЗЛП без условия целочисленности. Получим следующее оптимальное решение:

z = 14 ⁶/₁₇; x₁ = 3 ¹²/₁₇; x₂ = 2 ⁶/₁₇.

 Представим дальнейшие вычисления в виде следующей схемы:

 

1 z = 14 6/17 x1 = 3 12/17 x2 = 2 6/17

 

 

 

 

 

2 z = 14 6/17 x1 = 3 12/17 x2 = 2 6/17

3 z = 13 1/2 x1 = 2 1/4 x2 = 3

 

4 z = 14 x1 = 4 x2 = 2

5 z = 14 2/7 x1 = 5 x2 = 1 3/7

 

Использовался следующий порядок расчета:

1. Вершина (1) - решение исходной ЗЛП.  

2. Вершина (2) - решение исходной ЗЛП с ограничением x₂ £ 2.

3. Вершина (3) - решение исходной ЗЛП с ограничением x₂ ³ 3.

4. Вершина (4) - решение исходной ЗЛП с ограничениями x₂ £ 2; x₁ £ 4. Так как решение задачи целочисленное, то значение целевой функции данного решения объявляется текущей границей: z _г = 14.

5. Вершина (5) - решение исходной ЗЛП с ограничениями x₂ £ 2; x₁ ³ 5. Так как значение целевой функции z может быть в этой задаче только целочисленным, а при ветвлении значение z только ухудшится, то лучшее целое значение целевой функции на ветке (5) z = 14, то есть улучшить текущую границу z _г на этой ветке не удастся. Следовательно, данная ветка прозондирована.

6. Вершина (3) считается прозондированной, так как значение целевой функции в этой вершине z = 13 ¹/₃ меньше текущей границы, а при ветвлении ее значение не возрастает.

Так как все подзадачи прозондированы, то решение, соответствующее текущей границе является оптимальным, то есть z = 14; x₁ = 4; x₂ = 2.

 

Задание к лабораторной работе

 

Задания к лабораторной работе берутся из сборника вариантов контрольных работ /4/. С помощью программы "Решение задач целочисленного программирования" необходимо решить задачу 1а своего варианта. С помощью метода ветвей и границ по программе "Решение задач линейного программирования" найти решение задачи 1а. Типовой отчет по лабораторной работе приведен ниже.

Задание.

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

max z = 18x₁ + 9x₂ + 8x₃

          2x₁ + 21x₂ + 4x₃ £ 15

          6x₁ + 20x₂ + 5x₃ £ 20

          x_i ³ 0

Для приведения задачи к стандартной форме вводим дополнительные переменные:

max z = 18x₁ + 9x₂ + 8x₃

          2x₁ + 21x₂ + 4x₃ + x₄ = 15

          6x₁ + 20x₂ + 5x₃ + x₅ = 20

          x_i ³ 0

Результаты решения задачи с помощью метода отсечений Гомори по программе "Решение задач целочисленного программирования" представлены в следующих таблицах:

Исходные данные

1	Число переменных	5
2	Число ограничений	2
3	Признак оптимизации	1
4	Число этапов моделирования	1

Номера базисных переменных

	огр.1	огр.2
x	4	5

Матрица коэффициентов

	x1	x2	x3	x4	x5	правые части
огр. 1	2	21	4	1	0	15
огр. 2	6	20	5	0	1	20

Номер отсечения Гомори

2

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	правые части
z	0	45	0	0	0	2	8	54
zm	0	0	0	0	0	0	0	0
x4	0	15	0	1	0	6	-4	9
x1	1	3	0	0	0	1	0	3
х3	0	0	1	0	0	-2	1	0
х5	0	2	0	0	1	4	-5	2

 

Решение задачи: x₁ = 3, x₂ = 0, x₃ = 0, z = 54, и целочисленность достигнута за две итерации метода отсечений Гомори.

Результаты решение ЗЛП с помощью метода ветвей и границ по программе /1/ представлены в следующих таблицах:

               Исходные данные

1	Число переменных	5
2	Число ограничений	2
3	Признак оптимизации	1
4	Число этапов моделирования	1

Номера базисных переменных

	огр.1	огр.2
x	4	5

Матрица коэффициентов

	x1	x2	x3	x4	x5	правые части
огр. 1	2	21	4	1	0	15
огр. 2	6	20	5	0	1	20

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	правые части
z	0	51	7	0	3	60
zm	0	0	0	0	0	0.000
x4	0	14.33	2.333	1	-0.333	8.333
x1	1	3.333	0.833	0	0.167	3.333

Номера базисных переменных

	огр.1	огр.2	огр.3
x	4	5	6

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	правые части
огр. 1	2	21	4	1	0	0	15
огр. 2	6	20	5	0	1	0	20
огр. 3	1	0	0	0	0	1	3

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	правые части
z	0	23	0	0	1.6	8.4	57.2
zm	0	0	0	0	0	0	0
x4	0	5	0	1	-0.8	2.8	7.4
x3	0	4	1	0	0.2	-1.2	0.4
х1	1	0	0	0	0	1	3

Номера базисных переменных

	огр.1	огр.2	огр.3
x	5	6	7

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	x7	правые части
огр. 1	2	21	4	0	1	0	0	15
огр. 2	6	20	5	0	0	1	0	20
огр. 3	1	0	0	-1	0	0	1	4

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	правые части
z	0	51	7	0	0	3	0	60
zm	0	3.333	0.833	1	0	0.167	0	-0.667
x5	0	14.333	2.333	0	1	-0.333	0	8.333
x1	1	3.333	0.833	0	0	0.167	0	3.333
х7	0	-3.333	-0.833	-1	0	-0.167	1	0.667

Номера базисных переменных

	огр.1	огр.2	огр.3	огр.4
x	4	5	6	7

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	x7	правые части
огр. 1	2	21	4	1	0	0	0	15
огр. 2	6	20	5	0	1	0	0	20
огр. 3	1	0	0	0	0	1	0	3
огр. 4	0	0	1	0	0	0	1	0

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	правые части
z	0	0	0	0	0.45	15.3	5.75	54.9
zm	0	0	0	0	0	0	0	0
x4	0	0	0	1	-1.05	4.3	1.25	6.9
x2	0	1	0	0	0.05	-0.3	-0.25	0.1
х1	1	0	0	0	0	1	0	3
х3	0	0	1	0	0	0	1	0

Номера базисных переменных

	огр.1	огр.2	огр.3	огр.4
x	5	6	7	8

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	x7	x8	правые части
огр. 1	2	21	4	0	1	0	0	0	15
огр. 2	6	20	5	0	0	1	0	0	20
огр. 3	1	0	0	0	0	0	1	0	3
огр. 4	0	0	1	-1	0	0	0	1	1

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	x8	правые части
z	0	51	0	7	0	3	0	-7	53
zm	0	0	0	0	0	0	0	1	0
x5	0	14.333	0	2.333	1	-0.333	0	-2.333	6
x1	1	3.333	0	0.833	0	0.167	0	-0.833	2.5
х7	0	-3.333	0	-0.833	0	-0.167	1	0.833	0.5
х3	0	0	1	-1	0	0	0	1	1

Номера базисных переменных

	огр.1	огр.2	огр.3	огр.4	огр.5
x	4	5	6	7	8

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	x7	x8	правые части
огр. 1	2	21	4	1	0	0	0	0	15
огр. 2	6	20	5	0	1	0	0	0	20
огр. 3	1	0	0	0	0	1	0	0	3
огр. 4	0	0	1	0	0	0	1	0	0
огр. 5	0	1	0	0	0	0	0	1	0

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	x8	правые части
z	0	0	0	0	0	18	8	9	54
zm	0	0	0	0	0	0	0	0	0
x4	0	0	0	1	0	-2	-4	-21	9
x5	0	0	0	0	1	-6	-5	-20	2
х1	1	0	0	0	0	1	0	0	3
х3	0	0	1	0	0	0	1	0	0
х2	0	1	0	0	0	0	0	1	0

Номера базисных переменных

	огр.1	огр.2	огр.3	огр.4	огр.5
x	5	6	7	8	9

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	x7	x8	x9	правые части
огр. 1	2	21	4	0	1	0	0	0	0	15
огр. 2	6	20	5	0	0	1	0	0	0	20
огр. 3	1	0	0	0	0	0	1	0	0	3
огр. 4	0	0	1	0	0	0	0	1	0	0
огр. 5	0	1	0	-1	0	0	0	0	1	1

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	x8	x9	правые части
z	-17.14	0	-6.286	0	0.429	0	0	0	0	6.429
zm	0.095	0	0.19	1	0.048	0	0	0	0	-0.286
x2	0.095	1	0.19	0	0.048	0	0	0	0	0.714
x6	4.095	0	1.19	9	-0.952	1	0	0	0	5.714
х7	1	0	0	0	0	0	1	0	0	3
х8	0	0	1	0	0	0	0	1	0	0
х9	-0.095	0	-0.19	-1	-0.048	0	0	0	1	0.286

Литература

1.	Трушков А. С. Решение и моделирование задач линейного программирования. Отчет и программная документация. - КФ МГОУ, г. Коломна, 1998 г., 76 с.
2.	Трушков А. С. Симплексный метод решения задач линейного программирования. Алгоритмы и приложения.// Учебное пособие. Изд-во КФ МГОУ, г. Коломна, 1996 г., 107 с.
3.	Трушков А.С. Методы решения задач математического программирования.// Учебное пособие. Изд-во КФ МГОУ, г. Коломна, 1997 г., 102 с.
4.	Трушков А.С. Контрольная работа “Динамическое программирование”. Контрольная работа “Целочисленное программирование”.// Сборник вариантов контрольной работы. Изд-во КФ МГОУ, г. Коломна, 1997 г., 100 с.

 

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

__________________________________

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

КОЛОМЕНСКИЙ ИНСТИТУТ

"УТВЕРЖДЕНО" Учебно-методическим Советом КИ МГОУ Председатель Совета _____________________            А.М. Липатов "___"__________1999 г.

Трушков А.С.

ИНСТРУКЦИЯ

для выполнения лабораторной работы № 4