Метод искусственного базиса - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Метод искусственного базиса. Доклад-сообщение содержит 11 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Симплекс-метод Метод искусственного базиса

Слайд 2

Описание слайда:

Метод искусственного базиса Последняя трудность, которую осталось преодолеть - это определение исходного опорного плана и исходной симплекс-таблицы, с которой начинаются все итерации. За счет чего мы так легко составили исходную симплекс-таблицу в предыдущем примере? Легко видеть, что это произошло потому, что среди переменных были такие, что входили лишь в одно уравнение системы ограничений и не входили в другие. На искусственном введении таких переменных и основан метод искусственного базиса.

Слайд 3

Описание слайда:

Метод искусственного базиса Итак, пусть мы имеем задачу линейного программирования в канонической форме Можно считать, что все bi≥0, так как умножением соответствующего ограничения на -1 всегда можно сменить знак. Возьмем ну очень большое число M и будем решать следующую вспомогательную задачу.

Слайд 4

Описание слайда:

Вспомогательная задача В этой задаче сразу ясен исходный базис - в качестве него надо взять переменные xn+1,…,xn+m. В качестве исходного опорного плана надо взять план

Слайд 5

Описание слайда:

Решение симплекс-таблицы А теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса дополнительные переменные. Заметим, что если какая-то дополнительная переменная выведена из базиса, то соответствующий столбец симплекс-таблицы можно просто вычеркнуть и больше к нему не возвращаться. В конце концов возможны два варианта. Вариант 1 Все векторы, соответствующие введенным дополнительным переменным, будут выведены из базиса. В этом случае мы просто вернемся к исходной задаче, попав в какую-то вершину допустимой области. Все столбцы симплекс-таблицы, соответствующие дополнительным переменным, тогда исчезнут и дальше будет решаться исходная задача. Вариант 2 Несмотря на то, что M очень велико, получающийся оптимальный план будет все-таки содержать какую-то из дополнительных переменных. Это означает, что допустимая область исходной задачи пуста, то есть ограничения исходной задачи противоречивы и поэтому исходная задача вообще не имеет решений. Заметим в заключение, что величина M вообще не конкретизируется и так и остается в виде буквы M. При решении учебных задач в дополнительную строку пишут алгебраические выражения, содержащие M, а при счете на ЭВМ вводится еще одна дополнительная строка, куда пишутся коэффициенты при M.