Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение cимплекс-методом
|
|
Представим коэффициенты, стоящие в левой части системы ограничений, в матричной форме. За обозначения столбцов примем переменные, которым они соответствуют. Значения правой части ограничений запишем в отдельном столбце матрицы справа. За обозначения строк примем обозначения соответствующих переменных, которые являются базисными (имеющими ненулевые значения) переменными в начальной крайней точке (начале координат). Наконец, введем в таблицу дополнительную строку, соответствующую коэффициентам целевой функции 
. Существует несколько немного отличных друг от друга вариантов решения задачи симплекс-методом. В том из них, который излагается ниже, требуется вводить коэффициенты целевой функции с отрицательным знаком. Полученная в результате применения данной процедуры матрица называется симплекс-таблицей, а сама эта процедура представляет собой Шаг 1 в алгоритме симплекс-метода.
Таблица 1.2.
Первая симплекс-таблица
| Базисные переменные | Переменные x y s1 s2 s3. | Правая часть b |
| s1 s2 s3 | 3 0 1 0 0 0 2 0 1 0 1 1 0 0 1 | |
| Целевая функция, P | -2 –1 0 0 0 |
Шаг 2. В строке коэффициентов целевой функции найдем наибольшее отрицательное значение (-2). Столбец, соответствующий этому значению, называется ведущим. Разделим значения правой части на соответствующие значения ведущего столбца. В результате получим ряд отношений.
Таблица 1.3.
Первая симплекс-таблица с учетом отношений
| Базисные переменные | Переменные x y s1 s2 s3 | Правая Часть b | Отношения b/ элемент ведущего столбца |
| S1 S2 S3 | 3* 0 1 0 0 0 2 0 1 0 1 1 0 0 1 | 27/3 = 9  ведущая строка
30/0 = 
20/1 = 20
| |
| Целевая функция P | -2 -1 0 0 0 |
Ведущий столбец х
Шаг 3. Выберем среди полученных отношений наименьшее положительное отношение. В нашем случае оно равно 9. Соответствующая ему строка s1 является ведущей. Пересечение ведущего столбца и ведущей строки дает ведущий элемент 3, в приведенной выше табл. 1.3 он отмечен знаком " *".
Шаг 4. Разделим все элементы ведущей строки на ведущий элемент, 3. Заменим все элементы ведущей строки на полученные новые значения (табл. 1.4) Обозначение ведущей строки s1 заменим на обозначение ведущего столбца x. Новые переменные, соответствующие обозначениям строк, — это базисные переменные второго базисного решения.
Таблица 1.4.
Вторая симплекс-таблица
| Базисные переменные | Переменные X y s1 s2 s3 | Правая часть b | |
| x s2 s3 | 1 0 1/3 0 0 0 2 0 1 0 0 1 -1/3 0 1 | Новая R1 = прошлая R1 + ведущий элемент (3) Новая R2 = прошлая R2 – 0 х Новая R1 Новая R3 = прошлая R3 – 1 х Новая R1 | |
| Целевая функция P | 0 -1 2/3 0 0 | Новая P = прошлая P – -- (-2) х Новая R1 |
Шаг 5. Применив к строкам матрицы арифметические операции (строчные операции в матричной алгебре), приведем все остальные элементы ведущего столбца х к нулю. В качестве базиса в этих арифметических операциях должна использоваться только ведущая строка.
Обозначим через Ri i-ю строку. Соотношение " Новая R3 = Прошлая R3 - Новая R1" означает, что новые элементы строки 3 были получены вычитанием элементов новой ведущей строки (строка 1) из соответствующих элементов ведущей строки 3 предыдущего шага. Выполненные операции перечислены в крайнем правом столбце табл. 1.4.
Шаг 6. Шаги 2-5 повторяются до тех пор, пока не будет достигнута неотрицательность всех элементов в строке целевой функции.
Таблица 1.5.
Вторая симплекс-таблица с отношениями
| Базисные переменные | Переменные x y s1 s2 s3 | Правая часть b | Отношения b/ элемент ведущего столбца |
| x s2 s3 | 1 0 1/3 0 0 0 2 0 1 0 0 1* -1/3 0 1 | 9/0 = 
30/2 = 15
11/1 = 11  ведущая строка
| |
| Целевая функция P | 0 -1 2/3 0 0 |
Ведущий столбец у
Таблица 1.6.
Третья, итоговая, симплекс-таблица
| Базисные переменные | Переменные x y s1 s2 s3 | Правая часть b | |
| x s2 y | 1 0 1/3 0 0 0 0 2/3 1 -2 0 1 -1/3 0 1 | Новая R1=Прошлая R1 – – 0 x Новая R3 Новая R2=Прошлая R2 – – 2 x Новая R3 Новая R3 = Прошлая R3 ¸ ¸ ведущий элемент (1) | |
| Целевая функция P | 0 0 1/3 0 1 | Новая P =Прошлая P- -(-1) x Новая R3 |
Теперь все элементы в строке целевой функции либо положительны, либо равны нулю, следовательно, представленное в данной таблице решение является оптимальным.
Чтобы дать интерпретацию итоговой симплекс-таблице, обратим сначала внимание на значения ее крайних элементов.
Таблица 1.7.
|
|