Реферат: Курсовая работа по ЭММ

3. заполнить первую симплексную таблицу;

4. проверить план на оптимальность;

5. если план не оптимален, то выбрать разрешающий элемент, произвести пересчет всех элементов симплексной таблицы и перейти к п.4

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

Для построения первой таблицы из векторов `А_j нужно выбрать несколько компонентов, которые образуют единичную матрицу. И если исходная система ограничений, содержит только неравенства £ или ³, то при введении дополнительных переменных, сразу получают базисные векторы, которые образуют первый базис в симплекс-таблицах.

В верхней строке записывают коэффициенты при переменных целевых функций. В столбцы х₁ , х₂ , ..., х _n - заносят элементы векторов `А<sub>1</sub> , `А₂ ,`А<sub>n</sub> . В столбец план - заносят компоненты вектора `В. Столбец Х_б - отображает переменные входящие в базис. Их индексы совпадают с индексами базисных векторов. Столбец С_б - коэффициенты при базисных переменных в целевой функции.

Проверка плана на оптимальность. Нижняя строка симплекс-таблицы Dj - называется индексной.

D₀ = `С<sub>б *</sub> `В;

D_j = `С<sub>б*</sub> `х_j - С_j или D_j = `C<sub>б *</sub> `А_j - C_j

Она служит для проверки опорного плана на оптимальность. Если все D_j ³ 0, то все планы являются оптимальными.

Переход от одного базисного решения к другому, осуществляется исключением из базиса какого-нибудь из векторов и введением в него нового вектора.

1. В качестве разрешающего столбца выбирают столбец для которого элемент индексной строки D_р является самым маленьким отрицательным числом.

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

3. Выбираем наименьшее из данных отношений. Строка с ним называется разрешающей.

4. На пересечении разрешающего столбца и разрешающей строки стоит разрешающий элемент а _qp . Индексы q и p обозначают, что из базиса выводится `А<sub>q</sub> , а вместо него вводится `А_p . Разрешающий элемент обычно обводят в таблице.

5. На месте разрешающего элемента в новой симплекс-таблице ставят 1, остальные элементы разрешающего столбца 0.

6. Все элементы разрешающей строки делят на разрешающий элемент.

7. Остальные элементы симплекс-таблицы пересчитывают по формулам Жордана-Гаусса.

Замечание: Если по индексной строке определили разрешающий столбец, но в нем все элементы не положительные, то задача не имеет решений.

Следующий этап - это определение оптимального плана из симплекс-таблицы Х^* = (х₁ ^* , х₂ ^* , ..., х _n ^* ). Оптимальное решение выписывают из столбцов Х_б и план. Столбец Х_б - показывает, какие неизвестные отличны от 0. Столбец план - показывает, чему они равны.

D₀ - в последней симплекс-таблицы равно max значению целевой функции.

Алгоритм работы по симплекс-методу:

1. Выделяем исходный допустимый базис и заполняем первую таблицу.

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

3. Пусть среди указанных в пункте 2 чисел имеется положительное число( скажем, в столбце х_j ). Отмечаем столбец Х_j вертикальной стрелкой. Просматриваем остальные числа этого столбца. Если среди них нет положительных чисел, то min f = -¥ - задача решений не имеет.

4. Пусть среди просмотренных в п.3 чисел имеются положительные числа. Для каждого из таких чисел a составляем отношение, где b - первое число в той же строке (свободный член). Из всех таких отношений выбираем наименьшее. Пусть оно соответствует строке базисного неизвестного х _i . Отмечаем эту строку горизонтальной стрелкой. Число a, стоящее в отмеченной строке и отмеченном столбце, называется разрешающим элементом таблицы.

5. Переходим к новой таблице. Для этого отмеченную строку умножаем на ( чтобы на месте разрешающего элемента появилась единица) и пишем ее на месте прежней. К каждой из остальных строк таблицы прибавляем строку, полученную на месте отмеченной строки, умноженную на такое число, чтобы элемент, стоящий в отмеченном столбце, обратился в 0.

6. С новой таблицей возвращаемся к п.2

1.3 М-метод.

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