2818_Основы_мат_моделирования. Задача 1 Решить задачу с помощью симплексного метода Найти максимум целевой функции при данной системе ограничений
 Скачать 46.16 Kb.
|
1 2 Задача 1Решить задачу с помощью симплексного метода: Найти максимум целевой функции при данной системе ограничений  Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.  Определим максимальное значение целевой функции F(X) = 18x1+12x2+8x3 при следующих условиях-ограничений. 5x1+7x2+4x3≤24 5x1+2x2+x3≤10 2x1+x2+x3≤6 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).  В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. 5x1+7x2+4x3+x4 = 24 5x1+2x2+x3+x5 = 10 2x1+x2+x3+x6 = 6 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x4, x5, x6 Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,0,24,10,6) Базисное решение называется допустимым, если оно неотрицательно.
Переходим к основному алгоритму симплекс-метода. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (24 : 5 , 10 : 5 , 6 : 2 ) = 2 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x1. Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
Получаем новую симплекс-таблицу:
Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (14 : 5 , 2 : 0.4 , 2 : 0.2 ) = 2.8 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x2. Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Таким образом, в новом плане 2 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
Получаем новую симплекс-таблицу:
Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (2.8 : 0.6 , - , 1.44 : 0.48 ) = 3 Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (0.48) и находится на пересечении ведущего столбца и ведущей строки.
Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 3 войдет переменная x3. Строка, соответствующая переменной x3 в плане 3, получена в результате деления всех элементов строки x6 плана 2 на разрешающий элемент РЭ=0.48. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Таким образом, в новом плане 3 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника. Получаем новую симплекс-таблицу:
Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Оптимальный план можно записать так: x1 = 1, x2 = 1, x3 = 3 F(X) = 18*1 + 12*1 + 8*3 = 54 1 2 |