Теорема Двойственности

Применение одной из теорем двойственности на практике.

Преподаватель: Кныш А.А.
Авторские права: Перминов Л.М.

ТезисыМатематика
Просмотров: 20
Страниц: 4
Дата публикации: 2018-05-20

Лев Перминов

1
РЕЙТИНГ РАБОТЫ

Скачать Поделиться
Пожаловаться

Перминов Л.М. УрГЭУ Теорема двойственности Установить взаимосвязь между оптимальными решениями пары двойственных задач помогают теоремы двойственности. Рассмотрим одну из теорем двойственности и покажем, на примере, как решив одну задачу из пары двойственных задач можно найти решение другой. Теорема: Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение: причем значения целевых функций задач на своих оптимальных решениях совпадают. Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений. Для следующей задачи составить и решить двойственную и, используя ее решение, найти решение исходной задачи: Z(X) = . Решение. Составляем задачу двойственную к исходной: F(Y) = .

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме): F(Y) = . Производим решение задачи симплексным методом: БП F B 0 -1 2 1 1 0 0 2 -2 0 (1) -2 3 0 1 0 6 6 0 1 1 3 0 0 1 12 12 - -1 0 2 0 0 0 0 - Опорный план не удовлетворяет критериям оптимальности, поэтому следует провести пересчет: БП F B 0 0 0 4 1 1 0 8 - 1 1 -2 3 0 1 0 6 -3 0 0 (3) 0 0 -1 1 6 2 - 0 -2 5 0 1 0 6 - Опорный план не удовлетворяет критериям оптимальности, поэтому снова следует провести пересчет: БП F B 0 0 0 4 1 1 0 8 - 1 1 0 3 0 1/3 2/3 10 -

0 0 1 0 0 -1/3 1/3 2 - - 0 0 5 0 1/3 2/3 10 - Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Оптимальный план можно записать так: . Чтобы найти решение исходной задачи необходимо использовать формулу: . Матрица находится в последней части симплексной таблицы. Ее столбы располагаются под векторами : . А координатами вектора являются коэффициенты целевой функции при базисных неизвестных оптимального решения : . Вычисляем: =

Оптимальное решение исходной задачи можно найти проще, по формуле: , i = 1, 2, 3. Для этого необходимо к оценкам векторов прибавить соответствующие коэффициенты целевой функции: Значит, опорный план исходной задачи можно записать так: Ответ: min F(X)=10, при (0; 1/3; 2/3). Научный руководитель Кныш А.А.

Вы просматриваете облегчённый вариант работы - только текст.

Комментарии

Чтобы оставить комментарий, вам необходимо авторизоваться