Файл: Решение Необходимо найти минимальное значение целевой функции f 2x 1 4x 2 min, при системе ограничений.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 109
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (16 : 21/2 , - ) = 62/5
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (21/2) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | x3 | x4 | min |
| x3 | 16 | 5/2 | 0 | 1 | 1/2 | 32/5 |
| x2 | 4 | -1/2 | 1 | 0 | 1/2 | - |
| F(X2) | 4 | -3/2 | 0 | 0 | 1/2 | |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 2 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x3 плана 1 на разрешающий элемент РЭ=21/2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 |
| 16 : 21/2 | 21/2 : 21/2 | 0 : 21/2 | 1 : 21/2 | 1/2 : 21/2 |
| 4-(16 • -1/2):21/2 | -1/2-(21/2 • -1/2):21/2 | 1-(0 • -1/2):21/2 | 0-(1 • -1/2):21/2 | 1/2-(1/2 • -1/2):21/2 |
| 4-(16 • -11/2):21/2 | -11/2-(21/2 • -11/2):21/2 | 0-(0 • -11/2):21/2 | 0-(1 • -11/2):21/2 | 1/2-(1/2 • -11/2):21/2 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 |
| x1 | 32/5 | 1 | 0 | 2/5 | 1/5 |
| x2 | 36/5 | 0 | 1 | 1/5 | 3/5 |
| F(X2) | 68/5 | 0 | 0 | 3/5 | 4/5 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 |
| x1 | 32/5 | 1 | 0 | 2/5 | 1/5 |
| x2 | 36/5 | 0 | 1 | 1/5 | 3/5 |
| F(X3) | 68/5 | 0 | 0 | 3/5 | 4/5 |
Оптимальный план можно записать так:
x1 = 62/5, x2 = 71/5
F(X) = 1*62/5 + 1*71/5 = 133/5
Примечание:
1. По какому методу пересчитываются симплекс-таблицы?
Используется правило прямоугольника (метод жордановских преобразований).
2. Обязательно ли каждый раз выбирать максимальное значение из индексной строки?
Можно не выбирать, но это может привести к зацикливанию алгоритма.
3. В индексной строке в n-ом столбце нулевое значение. Что это означает?
Нулевые значения должны соответствовать переменным, вошедшим в базис. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов.
Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.
Метод Гомори.
В полученном оптимальном плане присутствуют дробные числа.
По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/5, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4≤0
q1 = b1 - [b1] = 62/5 - 6 = 2/5
q11 = a11 - [a11] = 1 - 1 = 0
q12 = a12 - [a12] = 0 - 0 = 0
q13 = a13 - [a13] = 2/5 - 0 = 2/5
q14 = a14 - [a14] = 1/5 - 0 = 1/5
Дополнительное ограничение имеет вид:
2/5-2/5x3-1/5x4 ≤ 0
Преобразуем полученное неравенство в уравнение:
2/5-2/5x3-1/5x4 + x5 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции
, делаем преобразование F(x) = -F(X).
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x1 | 32/5 | 1 | 0 | 2/5 | 1/5 | 0 |
| x2 | 36/5 | 0 | 1 | 1/5 | 3/5 | 0 |
| x5 | -2/5 | 0 | 0 | -2/5 | -1/5 | 1 |
| F(X0) | -68/5 | 0 | 0 | -3/5 | -4/5 | 0 |
1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 3-ая строка, а переменную x5 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2/5).
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x1 | 32/5 | 1 | 0 | 2/5 | 1/5 | 0 |
| x2 | 36/5 | 0 | 1 | 1/5 | 3/5 | 0 |
| x5 | -2/5 | 0 | 0 | -2/5 | -1/5 | 1 |
| F(X0) | -68/5 | 0 | 0 | -3/5 | -4/5 | 0 |
| θ | | - | - | -3/5 : (-2/5) = 11/2 | -4/5 : (-1/5) = 4 | - |