Составление симплексных таблиц. Критерий оптимальности

Симплексный метод удобно применять, используя построение симплексных таблиц. Первая симплексная таблица, соответствующая начальному плану, имеет вид:

Базис Составление симплексных таблиц. Критерий оптимальности - student2.ru В Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru  
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru  
 
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru  
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru  

Здесь приняты следующие обозначения.

Столбец «Базис» – это базисные переменные.

Столбец « Составление симплексных таблиц. Критерий оптимальности - student2.ru » – это коэффициенты при базисных переменных в целевой функции.

Столбец «В» – правые части ограничений;

Составление симплексных таблиц. Критерий оптимальности - student2.ru – коэффициенты при переменных в ограничениях;

Составление симплексных таблиц. Критерий оптимальности - student2.ru – коэффициенты при переменных в целевой функции.

Последняя строка в таблице ( Составление симплексных таблиц. Критерий оптимальности - student2.ru ) – это проверочная или оценочная строка.

Составление симплексных таблиц. Критерий оптимальности - student2.ru – значение целевой функции, соответствующее построенному начальному плану. Его находят так: каждый элемент столбца Составление симплексных таблиц. Критерий оптимальности - student2.ru умножают на соответствующий элемент столбца В и произведения складывают, т.е.

Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Составление симплексных таблиц. Критерий оптимальности - student2.ru – называют оценками или симплексными разностями и находят так: элементы столбца Составление симплексных таблиц. Критерий оптимальности - student2.ru умножают на соответствующие элементы столбца Составление симплексных таблиц. Критерий оптимальности - student2.ru , складывают результаты и вычитают Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Например,

Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Оценки ( Составление симплексных таблиц. Критерий оптимальности - student2.ru ) базисных переменных всегда равны нулю.

Признак оптимальности опорного плана состоит в следующем:

Опорный план будет оптимальным тогда и только тогда, когда все оценки

Составление симплексных таблиц. Критерий оптимальности - student2.ru для задачи на max и

Составление симплексных таблиц. Критерий оптимальности - student2.ru для задачи на min.

Если критерии оптимальности не выполняются, то нужно перейти к нехудшему опорному плану, т.е. исключить из базиса некоторую переменную и ввести вместо нее новую из числа свободных переменных.

Переменная, которую нужно ввести в базис, соответствует той оценке Составление симплексных таблиц. Критерий оптимальности - student2.ru , которая не удовлетворяет условию оптимальности. Если таких оценок несколько, то среди них выбирают наибольшую по абсолютной величине и соответствующую ей переменную вводят в базис. Столбец с этой переменной называют разрешающим.

Для определения переменной, которую нужно вывести из базиса, поступают так: элементы столбца В делят только на положительные элементы разрешающего столбца и находят симплексные отношения Составление симплексных таблиц. Критерий оптимальности - student2.ru . Выбирают из Составление симплексных таблиц. Критерий оптимальности - student2.ru наименьшее. Оно называет ту переменную, которую нужно ввести в базис. Соответствующая строка таблицы называется разрешающей.

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.

Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере.

Пример. Решить симплексным методом задачу линейного программирования.

Составление симплексных таблиц. Критерий оптимальности - student2.ru max

Составление симплексных таблиц. Критерий оптимальности - student2.ru

Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства.

Составление симплексных таблиц. Критерий оптимальности - student2.ru max

Составление симплексных таблиц. Критерий оптимальности - student2.ru

Составление симплексных таблиц. Критерий оптимальности - student2.ru

2) Определяем базисные переменные – это Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru 3) Заполняем первую таблицу

Базис Составление симплексных таблиц. Критерий оптимальности - student2.ru В Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru ––
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru –2 Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru –3 Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru  

Здесь Составление симплексных таблиц. Критерий оптимальности - student2.ru и Составление симплексных таблиц. Критерий оптимальности - student2.ru не удовлетворяют условию оптимальности, т.к. они меньше нуля. Выбираем среди них большее по модулю. Это Составление симплексных таблиц. Критерий оптимальности - student2.ru . Следовательно, столбец переменной Составление симплексных таблиц. Критерий оптимальности - student2.ru – разрешающий. Значит, в новый базис нужно ввести переменную Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Находим Составление симплексных таблиц. Критерий оптимальности - student2.ru : Составление симплексных таблиц. Критерий оптимальности - student2.ru ; Составление симплексных таблиц. Критерий оптимальности - student2.ru ; Составление симплексных таблиц. Критерий оптимальности - student2.ru

Наименьшее из этих чисел – это число 5, что соответствует строке базисной переменной Составление симплексных таблиц. Критерий оптимальности - student2.ru . Значит, строка базисной переменной Составление симплексных таблиц. Критерий оптимальности - student2.ru – разрешающая, следовательно, из базиса нужно вывести переменную Составление симплексных таблиц. Критерий оптимальности - student2.ru . Элемент Составление симплексных таблиц. Критерий оптимальности - student2.ru =1 – разрешающий. Новый базис: Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Составление симплексных таблиц. Критерий оптимальности - student2.ru Заполнение следующей таблицы начинаем со столбцов «Базис» и « Составление симплексных таблиц. Критерий оптимальности - student2.ru ». Потом заполняем разрешающую строку, разделив каждый ее элемент на разрешающий, т.е. на 1. Все элементы разрешающего столбца будут нулями, кроме разрешающего, который всегда равен 1. Столбцы под Составление симплексных таблиц. Критерий оптимальности - student2.ru переписываем без изменения, т.к. эти переменные остались в базисе. Остальные элементы новой таблицы находим по правилу прямоугольника. Например, элемент Составление симплексных таблиц. Критерий оптимальности - student2.ru найдем из прямоугольника

Составление симплексных таблиц. Критерий оптимальности - student2.ru = Составление симплексных таблиц. Критерий оптимальности - student2.ru

 
  Составление симплексных таблиц. Критерий оптимальности - student2.ru

Или элемент Составление симплексных таблиц. Критерий оптимальности - student2.ru = Составление симплексных таблиц. Критерий оптимальности - student2.ru из прямоугольника

Оценки Составление симплексных таблиц. Критерий оптимальности - student2.ru для новой таблицы можно находить по этому же правилу.

Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru В целом, решение данной задачи симплексным методом в виде таблиц будет иметь вид

Базис Составление симплексных таблиц. Критерий оптимальности - student2.ru В Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru ––
Составление симплексных таблиц. Критерий оптимальности - student2.ru –2 –3 таб. 1
Составление симплексных таблиц. Критерий оптимальности - student2.ru –3
Составление симплексных таблиц. Критерий оптимальности - student2.ru –1 5,5
Составление симплексных таблиц. Критерий оптимальности - student2.ru ––
Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru –2 таб. 2
Базис Составление симплексных таблиц. Критерий оптимальности - student2.ru В Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru –3 ––
Составление симплексных таблиц. Критерий оптимальности - student2.ru –2
Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru –3 Составление симплексных таблиц. Критерий оптимальности - student2.ru
Составление симплексных таблиц. Критерий оптимальности - student2.ru –3 таб. 3
Составление симплексных таблиц. Критерий оптимальности - student2.ru –0,2 0,6  
Составление симплексных таблиц. Критерий оптимальности - student2.ru –0,4 0,2  
Составление симплексных таблиц. Критерий оптимальности - student2.ru 0,4 –0,2  
Составление симплексных таблиц. Критерий оптимальности - student2.ru 0,6 –1,8  
Составление симплексных таблиц. Критерий оптимальности - student2.ru 0,8 0,6 таб. 4

Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru Оценочная строка четвертой таблицы показывает, что получен оптимальный план, так как все Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Составление симплексных таблиц. Критерий оптимальности - student2.ru – это значения Составление симплексных таблиц. Критерий оптимальности - student2.ru из столбца В, т.е. Составление симплексных таблиц. Критерий оптимальности - student2.ru , Составление симплексных таблиц. Критерий оптимальности - student2.ru , Составление симплексных таблиц. Критерий оптимальности - student2.ru , Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Свободные (небазисные) переменные Составление симплексных таблиц. Критерий оптимальности - student2.ru .

Итак, Составление симплексных таблиц. Критерий оптимальности - student2.ru = (6; 4; 0; 0; 1; 3),

Составление симплексных таблиц. Критерий оптимальности - student2.ru = Составление симплексных таблиц. Критерий оптимальности - student2.ru = 24.

Примечание: При переходе от таблицы к таблице для контроля сравнивают Составление симплексных таблиц. Критерий оптимальности - student2.ru , которое должно быть не меньше предыдущего для задачи на максимум и не больше предыдущего – для задачи на минимум.

При использовании симплексного метода возможны следующие случаи.

1) Если в оценочной строке симплекс-таблицы оценка Составление симплексных таблиц. Критерий оптимальности - student2.ru = 0 соответствует свободной переменной, то это означает, что ЗЛП имеет не единственный оптимальный план.

2) Если при переходе от одного опорного плана к другому в разрешающем столбце нет положительных элементов, то это означает, что целевая функция ЗЛП является неограниченной и оптимальных планов не существует.

Задания для самостоятельной работы.

Определить оптимальный план задач, используя симплексный метод решения задач линейного программирования:

а) Составление симплексных таблиц. Критерий оптимальности - student2.ru max Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru   б) Составление симплексных таблиц. Критерий оптимальности - student2.ru min Составление симплексных таблиц. Критерий оптимальности - student2.ru Составление симплексных таблиц. Критерий оптимальности - student2.ru

Понятие двойственности

Наши рекомендации