Найти наименьшее целое А для всех x1,x2,x3 >=0
(4x1-5x2+6x3<A)v(2x1+3x2-4x3>9)v(-x1+3x2+x3>8)v(-2x1-x2+x3<5) = 1
Симплекс-метод. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 4x1-5x2+6x3 при следующих условиях-ограничений. 2x1+3x2-4x3≤9 -x1+3x2+x3≤8 -2x1-x2+x3≥5
Для построения первого опорного плана систему неравенств
приведем к системе уравнений путем введения дополнительных переменных
(переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4.
В 2-м неравенстве смысла (≤) вводим базисную переменную x5.
В 3-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус.
2x1+3x2-4x3+x4 = 9
-x1+3x2+x3+x5 = 8
-2x1-x2+x3-x6 = 5
Расширенная матрица системы ограничений-равенств данной задачи:
x1 x2 x3 x4 x5 x6
2 3 -4 1 0 0 9
-1 3 1 0 1 0 8
-2 -1 1 0 0 -1 5
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной можно выбрать x5.
3. В качестве базовой переменной можно выбрать x6.
Получаем новую матрицу:
x1 x2 x3 x4 x5 x6 B
--------------------
2 3 -4 1 0 0 9
-1 3 1 0 1 0 8
2 1 -1 0 0 1 -5
--------------------- 4 -5 6 0 0 0 0 --------------------- Переобразование по Жордану-Гауссу строки целевой функции ---------------------- 16 1 0 0 0 0 -30 <= Строка целевой функции
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,5,6). Выразим базисные переменные через остальные: x4 = -2x1-3x2+4x3+9 x5 = x1-3x2-x3+8 x6 = -2x1-x2+x3-5 Подставим их в целевую функцию: F(X) = 4x1-5x2+6x3 Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным. Вместо переменной x6 следует ввести переменную x3. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. Базис B x1 x2 x3 x4 x5 x6 x4 29 -6 -1 0 1 0 -4 x5 3 1 4 0 0 1 1 x3 5 -2 -1 1 0 0 -1 F(X0) -30 16 1 0 0 0 6 Выразим базисные переменные через остальные: x4 = 6x1+x2+4x6+29 x5 = -x1-4x2-x6+3 x3 = 2x1+x2+x6+5 Подставим их в целевую функцию: F(X) = 4x1-5x2+6(2x1+x2+x6+5) или F(X) = 16x1+x2+6x6+30 -6x1-x2+x4-4x6=29 x1+4x2+x5+x6=3 -2x1-x2+x3-x6=5
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: A = -6 -1 0 1 0 -4 1 4 0 0 1 1 -2 -1 1 0 0 -1 Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x4, x5, x3 Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,5,29,3,0) Базисное решение называется допустимым, если оно неотрицательно. Базис B x1 x2 x3 x4 x5 x6 x4 29 -6 -1 0 1 0 -4 x5 3 1 4 0 0 1 1 x3 5 -2 -1 1 0 0 -1 F(X0) 0 -16 -1 0 0 0 -6
Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (- , 3 : 1 , - ) = 3 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки. Базис B x1 x2 x3 x4 x5 x6 min x4 29 -6 -1 0 1 0 -4 - x5 3 1 4 0 0 1 1 3 x3 5 -2 -1 1 0 0 -1 - F(X1) 0 -16 -1 0 0 0 -6 0
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x1. Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x5 плана 0 н а разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы: Получаем новую симплекс-таблицу: Базис B x1 x2 x3 x4 x5 x6 x4 47 0 23 0 1 6 2 x1 3 1 4 0 0 1 1 x3 11 0 7 1 0 2 1 F(X1) 48 0 63 0 0 16 10
1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы: Базис B x1 x2 x3 x4 x5 x6 x4 47 0 23 0 1 6 2 x1 3 1 4 0 0 1 1 x3 11 0 7 1 0 2 1 F(X2) 48 0 63 0 0 16 10 Оптимальный план можно записать так: x1 = 3, x2 = 0, x3 = 11 F(X) = 4•3 -5•0 + 6•11 = 78
No comments:
Post a Comment