Файл: Решение Необходимо найти минимальное значение целевой функции f 2x 1 4x 2 min, при системе ограничений.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 111
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
F(X) = x1+2x2+3x3+4x4
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x7 следует ввести переменную x3.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 |
| x5 | 3 | -1 | 2 | 0 | 0 | 1 | 0 | 0 | 0 |
| x6 | -12 | 0 | -2 | 0 | 4 | 0 | 1 | 1 | 0 |
| x3 | 7/3 | 0 | 0 | 1 | -4/3 | 0 | 0 | -1/3 | 0 |
| x8 | 5 | 1 | 0 | 0 | 4 | 0 | 0 | 0 | 1 |
| F(X0) | -7 | 1 | 2 | 0 | 8 | 0 | 0 | 1 | 0 |
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 |
| 3-(-7 • 0):-3 | -1-(0 • 0):-3 | 2-(0 • 0):-3 | 0-(-3 • 0):-3 | 0-(4 • 0):-3 | 1-(0 • 0):-3 | 0-(0 • 0):-3 | 0-(1 • 0):-3 | 0-(0 • 0):-3 |
| -5-(-7 • 3):-3 | 0-(0 • 3):-3 | -2-(0 • 3):-3 | 3-(-3 • 3):-3 | 0-(4 • 3):-3 | 0-(0 • 3):-3 | 1-(0 • 3):-3 | 0-(1 • 3):-3 | 0-(0 • 3):-3 |
| -7 : -3 | 0 : -3 | 0 : -3 | -3 : -3 | 4 : -3 | 0 : -3 | 0 : -3 | 1 : -3 | 0 : -3 |
| 5-(-7 • 0):-3 | 1-(0 • 0):-3 | 0-(0 • 0):-3 | 0-(-3 • 0):-3 | 4-(4 • 0):-3 | 0-(0 • 0):-3 | 0-(0 • 0):-3 | 0-(1 • 0):-3 | 1-(0 • 0):-3 |
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x6 следует ввести переменную x2.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 |
| x5 | -9 | -1 | 0 | 0 | 4 | 1 | 1 | 1 | 0 |
| x2 | 6 | 0 | 1 | 0 | -2 | 0 | -1/2 | -1/2 | 0 |
| x3 | 7/3 | 0 | 0 | 1 | -4/3 | 0 | 0 | -1/3 | 0 |
| x8 | 5 | 1 | 0 | 0 | 4 | 0 | 0 | 0 | 1 |
| F(X1) | -19 | 1 | 0 | 0 | 12 | 0 | 1 | 2 | 0 |
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 |
| 3-(-12 • 2):-2 | -1-(0 • 2):-2 | 2-(-2 • 2):-2 | 0-(0 • 2):-2 | 0-(4 • 2):-2 | 1-(0 • 2):-2 | 0-(1 • 2):-2 | 0-(1 • 2):-2 | 0-(0 • 2):-2 |
| -12 : -2 | 0 : -2 | -2 : -2 | 0 : -2 | 4 : -2 | 0 : -2 | 1 : -2 | 1 : -2 | 0 : -2 |
| 21/3-(-12 • 0):-2 | 0-(0 • 0):-2 | 0-(-2 • 0):-2 | 1-(0 • 0):-2 | -11/3-(4 • 0):-2 | 0-(0 • 0):-2 | 0-(1 • 0):-2 | -1/3-(1 • 0):-2 | 0-(0 • 0):-2 |
| 5-(-12 • 0):-2 | 1-(0 • 0):-2 | 0-(-2 • 0):-2 | 0-(0 • 0):-2 | 4-(4 • 0):-2 | 0-(0 • 0):-2 | 0-(1 • 0):-2 | 0-(1 • 0):-2 | 1-(0 • 0):-2 |
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x5 следует ввести переменную x1.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 |
| x1 | 9 | 1 | 0 | 0 | -4 | -1 | -1 | -1 | 0 |
| x2 | 6 | 0 | 1 | 0 | -2 | 0 | -1/2 | -1/2 | 0 |
| x3 | 7/3 | 0 | 0 | 1 | -4/3 | 0 | 0 | -1/3 | 0 |
| x8 | -4 | 0 | 0 | 0 | 8 | 1 | 1 | 1 | 1 |
| F(X2) | -28 | 0 | 0 | 0 | 16 | 1 | 2 | 3 | 0 |
Представим расчет каждого элемента в виде таблицы:
| B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 |
| -9 : -1 | -1 : -1 | 0 : -1 | 0 : -1 | 4 : -1 | 1 : -1 | 1 : -1 | 1 : -1 | 0 : -1 |
| 6-(-9 • 0):-1 | 0-(-1 • 0):-1 | 1-(0 • 0):-1 | 0-(0 • 0):-1 | -2-(4 • 0):-1 | 0-(1 • 0):-1 | -1/2-(1 • 0):-1 | -1/2-(1 • 0):-1 | 0-(0 • 0):-1 |
| 21/3-(-9 • 0):-1 | 0-(-1 • 0):-1 | 0-(0 • 0):-1 | 1-(0 • 0):-1 | -11/3-(4 • 0):-1 | 0-(1 • 0):-1 | 0-(1 • 0):-1 | -1/3-(1 • 0):-1 | 0-(0 • 0):-1 |
| 5-(-9 • 1):-1 | 1-(-1 • 1):-1 | 0-(0 • 1):-1 | 0-(0 • 1):-1 | 4-(4 • 1):-1 | 0-(1 • 1):-1 | 0-(1 • 1):-1 | 0-(1 • 1):-1 | 1-(0 • 1):-1 |
Выразим базисные переменные через остальные:
x1 = 4x4+x5+x6+x7+9
x2 = 2x4+1/2x6+1/2x7+6
x3 = 4/3x4+1/3x7+21/3
x8 = -8x4-x5-x6-x7-4
Подставим их в целевую функцию:
F(X) = (4x4+x5+x6+x7+9)+2(2x4+1/2x6+1/2x7+6)+3(4/3x4+1/3x7+21/3)+4x4
или
F(X) = 16x4+x5+2x6+3x7+28
x1-4x4-x5-x6-x7=9
x2-2x4-1/2x6-1/2x7=6
x3-4/3x4-1/3x7=21/3
8x4+x5+x6+x7+x8=-4
При вычислениях значение Fc = 28 временно не учитываем.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
| 1 | 0 | 0 | -4 | -1 | -1 | -1 | 0 |
| 0 | 1 | 0 | -2 | 0 | -1/2 | -1/2 | 0 |
| 0 | 0 | 1 | -4/3 | 0 | 0 | -1/3 | 0 |
| 0 | 0 | 0 | 8 | 1 | 1 | 1 | 1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x1, x2, x3, x8
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (9,6,21/3,0,0,0,0,-4)
Базисное решение называется допустимым, если оно неотрицательно.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 |
| x1 | 9 | 1 | 0 | 0 | -4 | -1 | -1 | -1 | 0 |
| x2 | 6 | 0 | 1 | 0 | -2 | 0 | -1/2 | -1/2 | 0 |
| x3 | 7/3 | 0 | 0 | 1 | -4/3 | 0 | 0 | -1/3 | 0 |
| x8 | -4 | 0 | 0 | 0 | 8 | 1 | 1 | 1 | 1 |
| F(X0) | 0 | 0 | 0 | 0 | -16 | -1 | -2 | -3 | 0 |
Переходим к основному алгоритму симплекс-метода.
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 |
| x1 | 9 | 1 | 0 | 0 | -4 | -1 | -1 | -1 | 0 |
| x2 | 6 | 0 | 1 | 0 | -2 | 0 | -1/2 | -1/2 | 0 |
| x3 | 7/3 | 0 | 0 | 1 | -4/3 | 0 | 0 | -1/3 | 0 |
| x8 | -4 | 0 | 0 | 0 | 8 | 1 | 1 | 1 | 1 |
| F(X1) | 0 | 0 | 0 | 0 | -16 | -1 | -2 | -3 | 0 |