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

4. На пересечении разрешающего столбца и разрешающей строки стоит разрешающий элемент аqp. Индексы q и p обозначают, что из базиса выводится (Аq, а вместо него вводится (Аp. Разрешающий элемент обычно обводят в таблице.

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

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

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

Жордана-Гаусса.

[pic] [pic]

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

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

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

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

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

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

3. Пусть среди указанных в пункте 2 чисел имеется положительное число( скажем, в столбце хj). Отмечаем столбец Хj вертикальной стрелкой.

Просматриваем остальные числа этого столбца. Если среди них нет положительных чисел, то min f = -( - задача решений не имеет.

4. Пусть среди просмотренных в п.3 чисел имеются положительные числа.

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

5. Переходим к новой таблице. Для этого отмеченную строку умножаем на

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

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

3 М-метод.

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

При решении М-задачи могут представиться две возможности:

1. М-задача имеет решение, т.е. min F существует.

2. М-задача не имеет решения, min F =(.

Решая М-задачу, мы стремимся получить оптимальное решение, в котором значения искусственных неизвестных равны нулю. Для того чтобы этого достичь, необходимо выбрать последовательность шагов таким образом, чтобы все искусственные неизвестные вышли из базиса, т.е. стали свободными. Тогда в базисном решении значения этих неизвестных и будут как раз нулями.

Рекомендуем скачать другие рефераты по теме: шпоры по гражданскому праву, заказать дипломную работу.



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

Поделитесь этой записью или добавьте в закладки