48151 (597384), страница 3
Текст из файла (страница 3)
.
Переменные 
базисные. Приравниваем их к правым частям ограничений: 
Все остальные переменные – свободные, приравниваем их к нулю: 
Запишем теперь начальный опорный план
(0; 0; 0; 0; 16; 4; 0).
2) Составление симплексных таблиц. Критерий оптимальности.
Симплексный метод удобно применять, используя построение симплексных таблиц. Первая симплексная таблица, соответствующая начальному плану, имеет вид:
| Базис |
| В |
|
| … |
|
| ||||||
|
|
| … |
| ||||||||||
|
|
|
|
|
| … |
| |||||||
|
|
|
|
|
| … |
| |||||||
| … | … | … | … | … | … | … | |||||||
|
|
|
|
|
| … |
| |||||||
|
|
|
|
| … |
| ||||||||
Здесь приняты следующие обозначения.
Столбец «Базис» – это базисные переменные.
Столбец «
» – это коэффициенты при базисных переменных в целевой функции.
Столбец «В» – правые части ограничений;
– коэффициенты при переменных в ограничениях;
– коэффициенты при переменных в целевой функции.
Последняя строка в таблице (
) – это проверочная или оценочная строка.
– значение целевой функции, соответствующее построенному начальному плану. Его находят так: каждый элемент столбца умножают на соответствующий элемент столбца В и произведения складывают, т.е.
.
– называют оценками или симплексными разностями и находят так: элементы столбца умножают на соответствующие элементы столбца 
, складывают результаты и вычитают .
Например,
.
Оценки ( ) базисных переменных всегда равны нулю.
Признак оптимальности опорного плана состоит в следующем:
Опорный план будет оптимальным тогда и только тогда, когда все оценки
для задачи на max и
для задачи на min.
Если критерии оптимальности не выполняются, то нужно перейти к нехудшему опорному плану, т.е. исключить из базиса некоторую переменную и ввести вместо нее новую из числа свободных переменных.
Переменная, которую нужно ввести в базис, соответствует той оценке , которая не удовлетворяет условию оптимальности. Если таких оценок несколько, то среди них выбирают наибольшую по абсолютной величине и соответствующую ей переменную вводят в базис. Столбец с этой переменной называют разрешающим.
Для определения переменной, которую нужно вывести из базиса, поступают так: элементы столбца В делят только на положительные элементы разрешающего столбца и находят симплексные отношения 
. Выбирают из 
наименьшее. Оно называет ту переменную, которую нужно ввести в базис. Соответствующая строка таблицы называется разрешающей.
На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.
Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере.
Пример. Решить симплексным методом задачу линейного программирования.
max
Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства.
max
2) Определяем базисные переменные – это 
.
3
) Заполняем первую таблицу
| Базис |
| В | 2 | 3 | 0 | 0 | 0 | 0 |
|
|
|
|
|
|
|
| ||||
|
| 0 | 18 | 1 | 3 | 1 | 0 | 0 | 0 |
|
|
| 0 | 16 | 2 | 1 | 0 | 1 | 0 | 0 |
|
|
| 0 | 5 | 0 | 1 | 0 | 0 | 1 | 0 |
|
|
| 0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | – |
|
| 0 | –2 | –3 | 0 | 0 | 0 | 0 | ||
Здесь 
и 
не удовлетворяют условию оптимальности, т. к. они меньше нуля. Выбираем среди них большее по модулю. Это . Следовательно, столбец переменной 
– разрешающий. Значит, в новый базис нужно ввести переменную .
Находим : 
; 
; 
Наименьшее из этих чисел – это число 5, что соответствует строке базисной переменной 
. Значит, строка базисной переменной – разрешающая, следовательно, из базиса нужно вывести переменную . Элемент 
=1 – разрешающий. Новый базис: 
.
Заполнение следующей таблицы начинаем со столбцов «Базис» и « ». Потом заполняем разрешающую строку, разделив каждый ее элемент на разрешающий, т.е. на 1. Все элементы разрешающего столбца будут нулями, кроме разрешающего, который всегда равен 1. Столбцы под 
переписываем без изменения, т. к. эти переменные остались в базисе. Остальные элементы новой таблицы находим по правилу прямоугольника. Например, элемент 
найдем из прямоугольника
= 
Или элемент 
=
из прямоугольника
Оценки для новой таблицы можно находить по этому же правилу.
В
целом, решение данной задачи симплексным методом в виде таблиц будет иметь вид
| Базис |
| В | 2 | 3 | 0 | 0 | 0 | 0 |
|
|
|
|
|
|
|
| ||||
|
| 0 | 18 | 1 | 3 | 1 | 0 | 0 | 0 | 6 |
|
| 0 | 16 | 2 | 1 | 0 | 1 | 0 | 0 | 16 |
|
| 0 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | 5 |
|
| 0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | – |
|
| 0 | –2 | –3 | 0 | 0 | 0 | 0 | таб. 1 | |
|
| 0 | 3 | 1 | 0 | 1 | 0 | –3 | 0 | 3 |
|
| 0 | 11 | 2 | 0 | 0 | 1 | –1 | 0 | 5,5 |
|
| 3 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | – |
|
| 0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | 7 |
|
| 15 | –2 | 0 | 0 | 0 | 3 | 0 | таб. 2 | |
| Базис |
| В | 2 | 3 | 0 | 0 | 0 | 0 |
|
|
|
|
|
|
|
| ||||
|
| 2 | 3 | 1 | 0 | 1 | 0 | –3 | 0 | – |
|
| 0 | 5 | 0 | 0 | –2 | 1 | 5 | 0 | 1 |
|
| 3 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | 5 |
|
| 0 | 12 | 0 | 0 | –3 | 0 | 9 | 1 |
|
|
| 21 | 0 | 0 | 2 | 0 | –3 | 0 | таб. 3 | |
|
| 2 | 6 | 1 | 0 | –0,2 | 0,6 | 0 | 0 | |
|
| 0 | 1 | 0 | 0 | –0,4 | 0,2 | 1 | 0 | |
|
| 3 | 4 | 0 | 1 | 0,4 | –0,2 | 0 | 0 | |
|
| 0 | 3 | 0 | 0 | 0,6 | –1,8 | 0 | 1 | |
|
| 24 | 0 | 0 | 0,8 | 0,6 | 0 | 0 | таб. 4 | |
О ценочная строка четвертой таблицы показывает, что получен оптимальный план, так как все .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
