Разделы презентаций


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

Вспомогательная задача к ЗЛП (1): (2)Вектор составлен из естественных переменных ЗЛП (1.) и искусственных переменных, введенных в ЗЛП (2):

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

Слайд 1Метод искусственного базиса
Цель метода искусственного базиса – построение начального


БДП (либо установить отсутствие БДП).
ЗЛП задана в канонической форме,

(

Этого всегда можно добиться, умножив уравнения на -1):


(1)

Метод искусственного базисаЦель метода искусственного базиса – построение начального  БДП (либо установить отсутствие БДП). ЗЛП задана

Слайд 2Вспомогательная задача к ЗЛП (1):
(2)
Вектор составлен из естественных переменных

ЗЛП (1.) и искусственных переменных, введенных в ЗЛП (2):


Вспомогательная задача к ЗЛП (1): (2)Вектор составлен из естественных переменных ЗЛП (1.) и искусственных переменных, введенных в

Слайд 3Искусственные переменные не несут никакого экономического смысла. Они необходимы только

для поиска начального БДП.
Единичные векторы An+1, An+2, …, An+m

образуют искусственный базис системы ограничений ЗЛП (2). Они представляют собой единичную матрицу размера m  m.
В ЗЛП (2) мы имеем начальный БДП, в котором первые n координат равны нулю.
Пусть множество допустимых планов задачи (1) - D1, а множество допустимых планов задачи (2) - D2.
Искусственные переменные не несут никакого экономического смысла. Они необходимы только для поиска начального БДП. Единичные векторы An+1,

Слайд 4Теорема. (О существовании плана ЗЛП).

Пусть


оптимальный план ЗЛП (2), тогда:
Если , то план является планом задачи (1), т.е. D1.
Если , то ЗЛП (1) не имеет допустимых планов, т.е. D1 есть пустое множество (D1 = ).
Замечание. Вспомогательная задача (2) всегда имеет оптимальный план.
Теорема. (О существовании плана ЗЛП).      Пусть

Слайд 5П р и м е р: Рассмотрим ЗЛП:
Приведем данную ЗЛП

к каноническому виду:

П р и м е р: Рассмотрим ЗЛП:Приведем данную ЗЛП к каноническому виду:

Слайд 6 Единичного базиса нет, поэтому построим

вспомогательную задачу, предварительно введя две искусственные переменные х5  0

и х6  0.
Единичного базиса нет, поэтому построим вспомогательную задачу, предварительно введя две искусственные переменные

Слайд 8Решив данную вспомогательную задачу симплекс-методом, мы найдем ее оптимальный план

и значение целевой функции на этом плане:


Оптимальный план вспомогательной задачи

есть начальный БДП основной задачи. После чего необходимо приступить к ее решению также симплекс-методом. Оптимальный план основной задачи:
х* = (11; 3; 0; 0); С1(х*) = – 19; С(х*) = 19
Решив данную вспомогательную задачу симплекс-методом, мы найдем ее оптимальный план и значение целевой функции на этом плане:Оптимальный

Слайд 9Признак неограниченности целевой функции
ЗЛП в канонической форме:
Пусть х0 =

(х10, х20,…, хn0) - БДП задачи (1)
Ax0 = b

эквивалентно

(1)

 - носитель плана, следовательно - ,
или в матричной форме записи:

(2)

Признак неограниченности целевой функции ЗЛП в канонической форме:Пусть х0 = (х10, х20,…, хn0) - БДП задачи (1)

Слайд 10 В уравнении (2) хσ0 представляет

часть исходного вектора х0 , из которого удалены нулевые (свободные)

компоненты. Для плана х0 можно построить симплекс-таблицу, причем предположим, что среди двойственных оценок имеются отрицательные , т.е. план не оптимальный.
В уравнении (2) хσ0 представляет часть исходного вектора х0 , из которого

Слайд 11Теорема. О неразрешимости ЗЛП.

Если для некоторого БДП х0 существует k

  и все элементы k-го вектор-столбца меньше или равны

нулю, т.е. , i, то ЗЛП неразрешима. Другими словами, в данной ситуации целевая функция не ограничена на допустимом множестве, т. е. С(х)   .

Теорема. О неразрешимости ЗЛП.Если для некоторого БДП х0 существует k   и все элементы k-го вектор-столбца

Слайд 12Пример:
Единичный базис состоит из векторов А3, А4, А5. Вырожденный БДП

х0 = (0; 0; 1; 0; 3).

Пример:Единичный базис состоит из векторов А3, А4, А5. Вырожденный БДП х0 = (0; 0; 1; 0; 3).

Слайд 13Решение ЗЛП

Решение ЗЛП

Слайд 14На второй итерации 2 = -3  0. Вводим в

базис вектор А2, однако координаты этого вектора . На основании

только что доказанной теоремы можно сделать заключение, что данная ЗЛП неразрешима, она не имеет оптимальных планов, а ее целевая функция С(х) → +∞ на множестве допустимых планов.
На второй итерации 2 = -3  0. Вводим в базис вектор А2, однако координаты этого вектора

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика