Вариант 25. Контрольное задание по теме 3 Линейное программирование. 3
 Скачать 1.21 Mb.
|
|
Итерация №2. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент . 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: Следовательно, 4-ая строка является ведущей. Разрешающий элемент равен (13.5) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 3 войдет переменная x2 Строка, соответствующая переменной x2 в плане 3, получена в результате деления всех элементов строки x9 плана 2 на разрешающий элемент РЭ=13.5 На месте разрешающего элемента в плане 3 получаем 1. В остальных клетках столбца x2 плана 3 записываем нули. Таким образом, в новом плане 3 заполнены строка x2 и столбец x2 . Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника. После преобразований получаем новую таблицу:
1. Проверка критерия оптимальности. Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Оптимальный план можно записать так: x1 = 14.65 x2 = 4.3 F(X) = 1 • 14.65 + 3 • 4.3 = 27.56296296296 В соответствии с условием задачи величина уступки  . Дополнительное ограничение будет иметь вид  , то есть  . 3. Решаем задачу по критерию Z3 Z3= –x1+ 2x2+25x3→max; x1+ 3x2+2x3≥1, 2x1–x2+x3≤25, x1+ 2x2≤24,  x1, x2, x3 ≥0. В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. В 4-м неравенстве смысла (≥) вводим базисную переменную x7 со знаком минус. В 5-м неравенстве смысла (≥) вводим базисную переменную x8 со знаком минус. 1x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 + 0x7 + 0x8 = 1 2x1-1x2 + 1x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 = 25 1x1 + 2x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 = 24 25x1 + 1x2-3x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 = 370.6 1x1 + 3x2-2x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 = 22.56 Введем искусственные переменные x: в 1-м равенстве вводим переменную x9; в 4-м равенстве вводим переменную x10; в 5-м равенстве вводим переменную x11; 1x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 = 1 2x1-1x2 + 1x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 25 1x1 + 2x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 24 25x1 + 1x2-3x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 + 0x9 + 1x10 + 0x11 = 370.6 1x1 + 3x2-2x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 + 0x9 + 0x10 + 1x11 = 22.56 Для постановки задачи на максимум целевую функцию запишем так: F(X) = -1x1+2x2+25x3 - Mx9 - Mx10 - Mx11 → max За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается. Полученный базис называется искусственным, а метод решения называется методом искусственного базиса. Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения. Из уравнений выражаем искусственные переменные: x9 = 1-x1-3x2-2x3+x4 x10 = 370.6-25x1-x2+3x3+x7 x11 = 22.56-x1-3x2+2x3+x8 которые подставим в целевую функцию: F(X) = -x1 + 2x2 + 25x3 - M(1-x1-3x2-2x3+x4) – - M(370.6-25x1-x2+3x3+x7) - M(22.56-x1-3x2+2x3+x8) → max или F(X) = (-1+27M)x1+(2+7M)x2+(25-3M)x3+(-M)x4+(-M)x7+(-M)x8+ +(-394.16M) → max Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных: x9, x5, x6, x10, x11. Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,25,24,0,0,1,370.6,22.56)
Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 1 войдет переменная x1 Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x9 плана 0 на разрешающий элемент РЭ=1 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x1 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 . Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. После преобразований получаем новую таблицу:
Итерация №3. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 5 войдет переменная x3 Строка, соответствующая переменной x3 в плане 5, получена в результате деления всех элементов строки x6 плана 4 на разрешающий элемент РЭ=2.37 На месте разрешающего элемента в плане 5 получаем 1. В остальных клетках столбца x3 плана 5 записываем нули. Таким образом, в новом плане 5 заполнены строка x3 и столбец x3 . Все остальные элементы нового плана 5, включая элементы индексной строки, определяются по правилу прямоугольника. После преобразований получаем новую таблицу:
1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Оптимальный план можно записать так: x1 = 14.67; x3 = 0.31; x2 = 4.66; F(X) = -1 • 14.67 + 25 • 0.31 + 2 • 4.66 = 2.46. Список использованной литературы
|