Вариант 25. Контрольное задание по теме 3 Линейное программирование. 3
 Скачать 1.21 Mb.
|
Контрольное задание по теме 4.11«Многокритериальная оптимизация»Математическая модель трехкритериальной задачи имеет вид: Z1=25x1+ x2– 3x3→max; Z2= x1+ 3x2– 2x3→min; Z3= –x1+ 2x2+25x3→max; x1+ 3x2+2x3≥1, 2x1–x2+x3≤25, x1+ 2x2≤24, x1, x2, x3 ≥0. Решить задачу методом последовательных уступок, выбрав уступку по первому критерию d1=4, а по второму d2=5. Решение 1. Решим задачу по критерию Z1. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 25x1+x2-3x3 при следующих условиях-ограничениях: x1+3x2+2x3≥1 2x1-x2+x3≤25 x1+2x2≤24 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. 1x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 = 1 2x1-1x2 + 1x3 + 0x4 + 1x5 + 0x6 = 25 1x1 + 2x2 + 0x3 + 0x4 + 0x5 + 1x6 = 24 Введем искусственные переменные x: в 1-м равенстве вводим переменную x7: 1x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 + 1x7 = 1 2x1-1x2 + 1x3 + 0x4 + 1x5 + 0x6 + 0x7 = 25 1x1 + 2x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 = 24 Для постановки задачи на максимум целевую функцию запишем так: F(X) = 25x1+x2-3x3 - Mx7 → max За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается. Полученный базис называется искусственным, а метод решения называется методом искусственного базиса. Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения. Из уравнений выражаем искусственные переменные: x7 = 1-x1-3x2-2x3+x4 которые подставим в целевую функцию: F(X) = 25x1 + x2-3x3 - M(1-x1-3x2-2x3+x4) → max или F(X) = (25+M)x1+(1+3M)x2+(-3+2M)x3+(-M)x4+(-M) → max Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных: x7, x5, x6. Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,25,24,1) Базисное решение называется допустимым, если оно неотрицательно.
Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x7 в план 1 войдет переменная x2 . Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=3. На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x2 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2 . Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
После преобразований получаем новую таблицу:
|