Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата

(7.86)

Неизвестные х1, х2, ..., хr - базисные неизвестные, набор {х1, х2,
..., хr} называется базисом, а остальные неизвестные {xr+1, хr+2, …, хn} - свободные. Подставляя (7.86) в (7.81), выразим функцию f через свободные неизвестные:

(7.87)

Положим все свободные неизвестные равными нулю:

(7.88)

Найдем из системы (7.86) значения базисных неизвестных

(7.89)

Полученное таким образом допустимое решение

отвечает базису x1, x2, ..., хr, т.е. является базисным решением.
Допустим для определенности, что мы ищем минимум f. Теперь нужно отданного базиса перейти к другому с таким расчетом, чтобы значение линейной функции f при этом уменьшилось. Проследим идею симплекс-метода на примере.

Пример 1. Дана система ограничений

Требуется минимизировать линейную функцию f = х2 – х3. В качестве свободных переменных выберем х2 и x3. Тогда данная система ограничений преобразуется к виду

Таким образом, базисное решение (3, О, О, 1). Так как линейная функция уже записана в свободных неизвестных, то ее значение для данного базисного решения f = 0. Для уменьшения этого значения можно уменьшить х2 или увеличить х3. Но х2 в данном базисе равно нулю и потому его уменьшать нельзя. Попробуем увеличить x3. Первое из уравнений имеет ограничение х3 =
1 (из условия х1( 0), второе - не дает ограничений. Далее, берем х3= 1, х2 не меняем и получаем новое допустимое решение (О, О, 1, 3), для которого f
= (1 - уменьшилось. Найдем базис, которому соответствует это решение (он состоит, очевидно, из переменных x3, х4). От предыдущей системы ограничений переходим к новой:

а форма в новых свободных переменных имеет вид

Теперь попробуем повторить предыдущую процедуру. Для уменьшения f надо уменьшить либо x1, либо х2, но это невозможно, так как в этом базисе x1 = О, х2 = 0.

Таким образом, данное базисное решение является оптимальным, и min f=
(1 при x1 = О, х2 = 0, хз = 1, x4 = 3.

Приведем алгоритм симплекс-метода в общем виде. Обычно все вычисления по симплекс-методу сводят в стандартные таблицы.

Запишем систему ограничений в виде

(7.90)

а функцию f

(7.91)

Тогда очередной шаг симплекс-процесса будет состоять в переходе от старого базиса к новому таким образом, чтобы значение линейной функции, по крайней мере, не увеличивалось.

Данные о коэффициентах уравнений и линейной функции занесем в табл.
7.12.

Таблица 7.12

Симплекс-таблица

|Базис|Св.чл.|[pic|… |[pic|… |[pic|[pic]|… |[pic]|… |[pic]|
| | |] | |] | |] | | | | | |
|[pic]|[pic] |1 | … |0 |… |0 |[pic]|… |[pic]|… |[pic]|
|… | … |… |… |… |… |… |… |… |… |… |… |
|[pic]|[pic] |0 |… |1 |… |0 |[pic]|… |[pic]|… |[pic]|
|… |… |… |… |… |… |… |… |… |… |… |… |
|[pic]|[pic] |0 |… |0 |… |1 |[pic]|… |[pic]|… |[pic]|
|[pic]|[pic] |0 |… |0 |… |0 |[pic]|… |[pic]|… |[pic]|

Рекомендуем скачать другие рефераты по теме: рефераты бесплатно скачать, сообщения бесплатно.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата