Оптимизация решений 5й вариант. Оптимизация решений. Решение Необходимо найти максимальное значение целевой функции f 2x 1 4x 2
 Скачать 55.86 Kb.
|
|
Анализ оптимального плана. Из 1-го склада необходимо груз направить к 2-у потребителю (20 ед.), к 4-у потребителю (20 ед.). Из 2-го склада необходимо груз направить к 1-у потребителю (15 ед.), к 3-у потребителю (15 ед.). Из 3-го склада необходимо груз направить к 1-у потребителю (15 ед.), к 2-у потребителю (5 ед.). 3. Решить задачу ЛП симплексным методом F=10x1+3x2+x3 max при ограничениях 2x1+x2+x3 6 5x1+x211 x1 0, x2 0, x3 0 . Решение: Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. 2x1+x2+x3+x4 = 6 5x1+x2+x5 = 11 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x4, x5 Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,0,6,11) Базисное решение называется допустимым, если оно неотрицательно.
Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (6 : 2 , 11 : 5 ) = 21/5 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x1. Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А∙В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Получаем новую симплекс-таблицу:
Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (13/5 : 1 , - ) = 13/5 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x3. Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Таким образом, в новом плане 2 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Получаем новую симплекс-таблицу:
|