Отчет по лабораторной работе №5 по курсу  Методы оптимальных решений по теме «Решение задачи целочисленного программирования методом Гомори»

0

 

 

 

Факультет экономики и управления

Кафедра математических методов и моделей в экономике

 

 

 

 

Отчет по лабораторной работе №5 по курсу  Методы оптимальных решений по теме «Решение задачи целочисленного программирования методом Гомори»

 

 

 

 

 

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

Решить задачу методом Гомори

 

Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования. 
Пусть найдено решение задачи ЛП: 

.

Решение Li будет целым числом, если 

 т.е. .

Данное соотношение определяет правильное отсечение Гомори 

 

 

 

 

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

при условиях:

        

Условие целочисленности разности:

 

 

 

 

 

  1. Решение задачи

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

Определим максимальное значение целевой функции 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 


Скачать: У вас нет доступа к скачиванию файлов с нашего сервера. КАК ТУТ СКАЧИВАТЬ  

Категория: Лабораторные работы / Лабораторные по экономике

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