Факультет экономики и управления
Кафедра математических методов и моделей в экономике
Отчет по лабораторной работе №5 по курсу Методы оптимальных решений по теме «Решение задачи целочисленного программирования методом Гомори»
- Постановка задачи
Решить задачу методом Гомори
Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования.
Пусть найдено решение задачи ЛП:
.
Решение Li будет целым числом, если
т.е. .
Данное соотношение определяет правильное отсечение Гомори
Математическая модель задачи целочисленного программирования:
при условиях:
Условие целочисленности разности:
- Решение задачи
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 2x1 + x2
4x1 + x2≤16
x1 + x2≤11
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4.
4x1 + 1x2 + 1x3 + 0x4 = 16
1x1 + 1x2 + 0x3 + 1x4 = 11
Решим систему уравнений относительно базисных переменных: x3, x4,
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,16,11)
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
x3 |
16 |
4 |
1 |
1 |
0 |
|
x4 |
11 |
1 |
1 |
0 |
1 |
|
F(X0) |
0 |
-2 |
-1 |
0 |
0 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю, 1-ая строка является ведущей. Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
min |
|
x3 |
16 |
4 |
1 |
1 |
0 |
4 |
|
x4 |
11 |
1 |
1 |
0 |
1 |
11 |
|
F(X1) |
0 |
-2 |
-1 |
0 |
0 |
0 |
Вместо переменной x3 в план 1 войдет переменная x1.
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
x1 |
4 |
1 |
1/4 |
1/4 |
0 |
|
x4 |
7 |
0 |
3/4 |
-1/4 |
1 |
|
F(X1) |
8 |
0 |
-1/2 |
1/2 |
0 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю, 2-ая строка является ведущей. Разрешающий элемент равен (3/4) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
min |
|
x1 |
4 |
1 |
1/4 |
1/4 |
0 |
16 |
|
x4 |
7 |
0 |
3/4 |
-1/4 |
1 |
91/3 |
|
F(X2) |
8 |
0 |
-1/2 |
1/2 |
0 |
0 |
Вместо переменной x4 в план 2 войдет переменная x2.
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
x1 |
12/3 |
1 |
0 |
1/3 |
-1/3 |
|
x2 |
91/3 |
0 |
1 |
-1/3 |
11/3 |
|
F(X2) |
122/3 |
0 |
0 |
1/3 |
2/3 |
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
x1 |
12/3 |
1 |
0 |
1/3 |
-1/3 |
|
x2 |
91/3 |
0 |
1 |
-1/3 |
11/3 |
|
F(X3) |
122/3 |
0 |
0 |
1/3 |
2/3 |
Оптимальный план можно записать так:
x1 = 12/3
x2 = 91/3
F(X) = 2•12/3 + 1•91/3 = 122/3
Анализ оптимального плана.
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение 1/3 в столбце x3 означает, что теневая цена (двойственная оценка) равна 1/3.
Значение 2/3 в столбце x4 означает, что теневая цена (двойственная оценка) равна 2/3.
Метод Гомори.
В полученном оптимальном плане присутствуют дробные числа.
По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4≤0
q1 = b1 - [b1] = 12/3 - 1 = 2/3
q11 = a11 - [a11] = 1 - 1 = 0
q12 = a12 - [a12] = 0 - 0 = 0
q13 = a13 - [a13] = 1/3 - 0 = 1/3
q14 = a14 - [a14] = -1/3 + 1 = 2/3
Дополнительное ограничение имеет вид:
Преобразуем полученное неравенство в уравнение:
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F(x) = -F(X).
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x1 |
12/3 |
1 |
0 |
1/3 |
-1/3 |
0 |
|
x2 |
91/3 |
0 |
1 |
-1/3 |
11/3 |
0 |
|
x5 |
-2/3 |
0 |
0 |
-1/3 |
-2/3 |
1 |
|
F(X0) |
-122/3 |
0 |
0 |
-1/3 |
-2/3 |
0 |
Ведущей будет 3-ая строка, а переменную x5 следует вывести из базиса.
Минимальное значение 0соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент, равный (-2/3).
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x1 |
12/3 |
1 |
0 |
1/3 |
-1/3 |
0 |
|
x2 |
91/3 |
0 |
1 |
-1/3 |
11/3 |
0 |
|
x5 |
-2/3 |
0 |
0 |
-1/3 |
-2/3 |
1 |
|
F(X0) |
-122/3 |
0 |
0 |
-1/3 |
-2/3 |
0 |
|
0 |
0 |
- |
- |
-1/3 : (-1/3) = 1 |
-2/3 : (-2/3) = 1 |
- |
Пересчет симплекс-таблицы.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x1 |
2 |
1 |
0 |
1/2 |
0 |
-1/2 |
|
x2 |
8 |
0 |
1 |
-1 |
0 |
2 |
|
x4 |
1 |
0 |
0 |
1/2 |
1 |
-11/2 |
|
F(X0) |
-12 |
0 |
0 |
0 |
0 |
-1 |
Решение получилось целочисленным. Нет необходимости применять метод Гомори. Оптимальный целочисленный план можно записать так:
x1 = 2 х2 = 8 x4 = 1
F(X) = 12
Скачать: