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

Лев Перминов

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

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

Общественные науки в целом

Тезисы

Вуз: Независимое исследование (нет вуза)

ID: 5ed3f9a71db946000153236c

UUID: d9c1c270-859b-0138-b659-0242ac180003

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

Опубликовано: больше 4 лет назад

Просмотры: 31

Лев Перминов

Источник: vernsky.ru

Комментировать 0

Рецензировать 0

Скачать - 81,8 КБ

Поделиться работой

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

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

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

Отзывы:

Авторизуйтесь, чтобы оставить отзыв