 |
|
Пример решения задачи
Задача взята из учебника И. Л. Акулич «Математическое программирование в примерах и задачах» (стр. 175).
Перейдем к канонической форме.
В 1-м неравенстве вводим базисную переменную x3. В 2-м неравенстве вводим базисную переменную x4. В 3-м неравенстве вводим базисную переменную x5 со знаком минус.
-3x1 + 14x2 + 1x3 + 0x4 + 0x5 = 78
5x1-6x2 + 0x3 + 1x4 + 0x5 = 26
1x1 + 4x2 + 0x3 + 0x4-1x5 = 25
Введем искусственные переменные.В 3-м равенстве вводим переменную x6.
-3x1 + 14x2 + 1x3 + 0x4 + 0x5 + 0x6 = 78
5x1-6x2 + 0x3 + 1x4 + 0x5 + 0x6 = 26
1x1 + 4x2 + 0x3 + 0x4-1x5 + 1x6 = 25
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = 5x1+7x2+Mx6 → min
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Из уравнений выражаем искусственные переменные: x6 = 25-x1-4x2+x5
Подставим в целевую функцию:
F(X) = 5x1 + 7x2 + M(25-x1-4x2+x5) → min
F(X) = (5-M)x1+(7-4M)x2+(M)x5+(25M) → min
Матрица коэффициентов A этой системы уравнений имеет вид:
| | |||||||||||||||||||
|
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
3. Определение новой свободной переменной.
Вычислим значения по строкам как частное от деления: bi / ai2
и из них выберем наименьшее. 1-ая строка является ведущей.
4. Пересчет симплекс-таблицы.
Представим расчет каждого элемента в виде таблицы. Получаем новую симплекс-таблицу:
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент .
3. Определение новой свободной переменной.
Вычислим значения по строкам как частное от деления: bi / ai2
и из них выберем наименьшее. 3-ая строка является ведущей.
4. Пересчет симплекс-таблицы.
Представим расчет каждого элемента в виде таблицы:
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи. Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
x2 = 5,88
x1 = 1,46
F(X) = 7*5,88+ 5*1,46 = 48,5
Методом Гомори
В полученном оптимальном плане присутствуют дробные числа.
По 1 уравнению с переменной x2, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 0,88, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4 - q15•x5≤0
q1 = b1 - [b1] = 5,88 - 5 = 0,88
q11 = a11 - [a11] = 0 - 0 = 0
q12 = a12 - [a12] = 1 - 1 = 0
q13 = a13 - [a13] = 0,04 - 0 = 0,04
q14 = a14 - [a14] = 0 - 0 = 0
q15 = a15 - [a15] = 1-0,12 = 0,88
Дополнительное ограничение имеет вид: 0,88-0,04x3-0,88x5 ≤ 0
Преобразуем полученное неравенство в уравнение: 0,88-0,04x3-0,88x5 + x6 = 0
Коэффициенты уравнения введем дополнительной строкой в оптимальную симплексную таблицу:
1. Проверка критерия оптимальности.
План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю. (-3,5)
Ведущей будет 4-ая строка (1), а переменную x6 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение соответствует 5-му столбцу, т.е. переменную x5 необходимо ввести в базис.
4. Пересчет симплекс-таблицы.
Решение получилось целочисленным.
Оптимальный целочисленный план можно записать так:
x2 = 6, x4 = 52, x1 = 2, x5 = 1
F(X) = 7*6 + 5*2 = 52