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

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

Тип публикации: Тезисы

Язык: Русский

Дополнительная информация:
ID: 5b01de1cf2ad471e773c7249
UUID: e3e2dfa0-6280-0137-6fe1-525400006e27
Опубликовано: 20.05.2018 20:44
Просмотры: 1839

Current View

Перминов Л.М. УрГЭУ Теорема двойственности Установить взаимосвязь между оптимальными решениями пары двойственных задач помогают теоремы двойственности. Рассмотрим одну из теорем двойственности и покажем, на примере, как решив одну задачу из пары двойственных задач можно найти решение другой. Теорема: Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение: причем значения целевых функций задач на своих оптимальных решениях совпадают. Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений. Для следующей задачи составить и решить двойственную и, используя ее решение, найти решение исходной задачи: 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). Научный руководитель Кныш А.А.

- у работы пока нет рецензий -