Симплексный метод (симплекс-метод) решения задачи линейного программирования

Симплексный метод (симплекс-метод) решения задачи линейного программирования Требуется решить задачу линейного программирования Т.е. 1) для функции ищем максимум; 2) все ограничения являются равенствами; 3) правые части всех ограничений неотрицательны; 4) все переменные в задаче неотрицательны. Составление начальной симплекс-таблицы: БП … Порядок заполнения: Записываем матрицу коэффициентов . Обозначим столбцы матрицы А: , , …, Находим в матрице А единичные столбцы вида: - первый единичный столбец - второй единичный столбец - n-ый единичный столбец Число единичных столбцов должно равняться числу строк матрицы. По единичным столбцам матрицы А выбираем базисные переменные (БП). - целевой вектор - часть целевого вектора с, содержит координаты соответственно базисным переменным. - столбец правые части ограничений . Записываем в симплекс-таблицу: БП … … … … … … … … … … … Вычисляем Вычисляем оценки (индексы) переменных: • для базисной переменной ; • для свободной переменной . БП … … … … … … … … … … … … Проверка критериев. Критерий оптимальности опорного плана. Если все оценки переменных , ,…, неотрицательны, то опорный план, записанный в симплекс-таблице, является оптимальным. Ответ: базисные переменные = значениям , свободные переменные = 0, максимальное значение функции =. Критерий неограниченности целевой функции. Если для некоторой переменной оценка и в столбце нет положительных элементов, то целевая функция не ограничена сверху. Ответ: максимальное значение не достигается. Улучшение плана. Если ни один из критериев не выполняется, то план можно улучшить, т.е. увеличить значение целевой функции. Пусть для переменной ее оценка (если для нескольких переменных оценки отрицательны, то из них выбирается наименьшая). Пусть в столбце есть положительное число (если в столбце несколько положительных чисел, то выбираем наименьшее среди отношений элементов столбцов и ). Выбранное положительное число называется разрешающим элементом. БП разр. эл. Составляем новую симплекс-таблицу: Меняем базис: переменную удаляем из базиса, на ее место в базисе ставим переменную . Столбец переменной становится единичным. Остальные базисные переменные и их столбцы не меняются. Все элементы разрешающей строки делим на разрешающий элемент. Остальные числа пересчитываем по правилу прямоугольника . А С В разр. эл. Пример 1 Решить задачу Решение: Выписываем: В задаче 4 переменные - план Целевой вектор с=(3, 4, -1, 0) (координаты = коэффициентам перед переменными в функции f) Матрица А (элементы = коэффициентам перед переменными в левых частях ограничений): Единичные столбцы: Первый единичный столбец –для переменной х2 Второй единичный столбец – для переменной х4 Базисные переменные х2 и х4 Свободные переменные х1 и х3 Вектор 2-я и 4-я координаты вектора с Столбец Записываем в таблицу: БП 4 10 2 1 3 2 1 -1 1 Вычисляем Скобки обозначают сумму произведений элементов столбцов (как в скалярном произведении векторов) Для базисных переменных х2 и х4 оценки равны 0: и Для свободных переменных х1 и х3 : - 1-й столбец матрицы А ( 1-я координата вектора с) - 3-й столбец матрицы А ( 3-я координата вектора с) Записываем в таблицу: БП 4 10 2 1 3 2 1 -1 1 40 5 13 Проверяем критерий оптимальности плана: Все оценки переменных , ,, неотрицательны, следовательно получен оптимальный план. (свободная переменная) (базисная переменная) – см. ниже фрагмент таблицы (свободная переменная) (базисная переменная) БП 10 2 40 Максимальное значение функции Ответ: оптимальный план , Пример 2 Решить задачу Решение: Для решения симплекс-методом ограничения должны быть записаны как равенства. Добавим в левую часть каждого ограничения по одной новой неотрицательной переменной. Новая запись задачи: Выписываем: В задаче 5 переменных - план Целевой вектор с=(10, 3, 0, 0, 0) Единичные столбцы: Первый единичный столбец –для переменной Второй единичный столбец – для переменной х4 Третий единичный столбец – для переменной Базисные переменные Свободные переменные Вектор Столбец Вычисляем: Для базисных переменных оценки равны 0: , , Для свободных переменных : Записываем в таблицу: БП 7 4 2 1 21 1 4 1 4 -3 5 1 -10 -3 Проверяем критерий оптимальности плана – не выполнено, т.к. и Проверяем критерий неограниченности функции – не выполнено, т.к. в каждом столбце с отрицательной ∆ есть положительные элементы. Тогда план можно изменить и увеличить значение функции (сейчас оно равно ). Из отрицательных и выбираем наименьшее - это . Значит, столбец переменной будет разрешающим. В этом столбце два положительных элемента. Делим построчно элементы столбца на эти числа: 7 4 21 1 4 -3 7/4 и 21/1 - меньшее значение 7/4. Значит, разрешающая строка – первая, а разрешающий элемент = 4 Для удобства перепишем таблицу (хотя это не обязательно). Разрешающий элемент выделен цветом. Таблица 1 БП 7 4 2 1 21 1 4 1 4 -3 5 1 -10 -3 Строим новую таблицу: В разрешающей строке в базисе находился х3, исключаем эту переменную из базиса, на ее место в базис ставим х1 (по разрешающему столбцу). Столбец для будет единичный, как был ранее у переменной х3. Другие базисные переменные и их столбцы не меняются. Для базисных переменных в нижней строке пишем ∆=0 Элементы разрешающей строки из первой таблицы делим на разр.элемент (4) и результаты записываем во вторую таблицу. Остальные числа пересчитываем по правилу прямоугольника . (т.е. клетки, в которых находятся А, В, С, разр.эл. должны быть углами прямоугольника) Столбец : Столбец : Столбец : 21 - 7*1 /4 = 77/4 4 - 2*1 /4 = 14/4 0 - 1*1 /4 = -1/4 4 - 7*(-3) /4 = 37/4 5 - 2*(-3) /4 = 26/4 0 - 1*(-3) /4 = 3/4 0 - 7*(-10) /4 = 70/4 -3 - 2*(-10) /4 = 2 0 - 1*(-10) /4 = 10/4 Столбец пересчитывать не нужно. Итого, таблица 2 БП 7/4 1 2/4 1/4 77/4 14/4 -1/4 1 37/4 26/4 ¾ 1 70/4 2 10/4 Проверяем критерий оптимальности плана в таблице 2 – выполнено. Оптимальный план Максимальное значение функции В ответе пишем оптимальный план для исходной задачи с двумя переменными , Другие переменные были вспомогательными. Ответ: оптимальный план , Пример 3 Решить задачу Решение: В первом ограничении в правой части отрицательное число. Умножим обе части неравенства на (-1). Знак неравенства развернется: И в левую часть добавим новую неотрицательную переменную, чтобы получить равенство: Новая запись задачи: Выписываем: В задаче 5 переменных - план Целевой вектор с=(35, -4, 7, 1, 0) Единичные столбцы: Первый единичный столбец –для переменной Второй единичный столбец – для переменной Третий единичный столбец – для переменной Базисные переменные – порядок в базисе определяется по единичным столбцам Свободные переменные Вектор 5-я, 2-я, 3-я координаты вектора с Столбец Вычисляем: Для базисных переменных оценки равны 0: , , Для свободных переменных Записываем в таблицу 1: БП 4 5 -5 1 -4 15 -3 1 -1 7 6 -2 1 3 -18 -37 24 Проверяем критерий оптимальности плана – не выполнено, т.к. Проверяем критерий неограниченности функции – не выполнено, т.к. в столбце с отрицательной есть положительный элемент. Тогда план можно изменить и увеличить значение функции (сейчас оно равно ). Разрешающий столбец – столбец (только ) , разрешающая строка – первая ( в столбце только одно положительное число). Разрешающий элемент = 5. Строим таблицу 2: В базисе исключаем , на ее место ставим . Столбец теперь единичный. Другие базисные переменные и их столбцы не меняются. Для базисных переменных ∆ равны 0. Разрешающую строку делим на 5. Остальные элементы по правилу прямоугольника: Столбец : Столбец : Столбец : 15 - 4*(-3) /5=87/5 -1 - (-5)*(-3) /5= -4 0 - 1*(-3) /5=3/5 6 - 4*(-2) /5=38/5 3 - (-5)*(-2) /5= 1 0 - 1*(-2) /5=2/5 -18 -4*(-37) /5=58/5 24 - (-5)*(-37) /5= -13 0 - 1*(-37) /5=37/5 Итого, таблица 2: БП 4/5 1 -1 1/5 87/5 1 -4 3/5 38/5 1 1 2/5 58/5 -13 37/5 Проверяем критерий оптимальности плана – не выполнено, т.к. Проверяем критерий неограниченности функции – не выполнено, т.к. в столбце с отрицательной есть положительный элемент. Тогда план можно изменить и еще увеличить значение функции (сейчас оно равно ). Разрешающий столбец – столбец (только ), разрешающая строка – третья( в столбце только одно положительное число). Разрешающий элемент = 1. Строим таблицу 3: В базисе исключаем , на ее место ставим. Столбец теперь единичный. Другие базисные переменные и их столбцы не меняются. Для базисных переменных ∆ равны 0. Разрешающую строку делим на 1. Остальные элементы по правилу прямоугольника: Столбец : Столбец : Столбец : 4/5 – 38/5 *(-1) / 1 =42/5 0 – 1 *(-1) / 1 =1 1/5 – 2/5 *(-1) / 1 =3/5 87/5 – 38/5*(-4) / 1 =239/5 0 – 1*(-4) / 1 =4 3/5 – 2/5*(-4) / 1 =11/5 58/5 – 38/5 *(-13) / 1 =552/5 1 – 1 *(-13) / 1 =13 37/5 – 2/5 *(-13) / 1 =63/5 Итого, таблица 3: БП 42/5 1 1 3/5 239/5 1 4 11/5 38/5 1 1 2/5 552/5 13 63/5 Проверяем критерий оптимальности плана в таблице 3 – выполнено, все ∆ неотрицательны. Оптимальный план Максимальное значение функции В ответе пишем оптимальный план для исходной задачи с четырьмя переменными Переменная была вспомогательной. Ответ: оптимальный план ,