Теоремы двойственности и их использование в задачах ЛП - Решение оптимизационных экономических задач методами линейного программирования

Исходная задача:

При ограничениях:

Двойственной является следующая задача:

При ограничениях:

Число неизвестных в двойственной задаче равно 2. Следовательно, решение двойственной задачи можно найти графическим методом.

Построим систему координат и проведем прямые, ограничивающие область допустимых решений (ОДР). Для этого в неравенствах системы ограничений и условиях неотрицательности переменных () знаки неравенств заменим на знаки равенств, и для каждой прямой зададим координаты двух точек:

Построим вектор целевой функции W.

Областью допустимых решений является неограниченная выпуклая многоугольная область.

Далее, среди всех точек области допустимых решений (ОДР) надо найти такую точку, в которой целевая функция W имеет минимальное значение.

Уравнение при фиксированном значении W определяет прямую, а при изменении значения W - семейство параллельных прямых, которые называются Линиями уровня для функции W.

Будем перемещать линию уровня (например, ) по ОДР параллельно самой себе в направлении вектора до тех пор, пока она не пройдет через первую общую точку с ОДР. Координаты этой точки и являются оптимальным решением данной задачи.

Для нахождения координат необходимо решить систему линейных уравнений соответствующих прямым, пересекающимся в данной точке. У нас 4 точки: А, В, С, Д.

Найдем координаты Точки А. Для этого решим систему, составленную из уравнений (4) и (5):

А (0; 5)

Подставим координаты точки А в целевую функцию:

Найдем координаты Точки В. Для этого надо решить систему, составленную из уравнений (3) и (4):

В (3; 2)

Подставим найденные значения в целевую функцию:

Найдем координаты Точки С. Для этого решим систему, составленную из уравнений (3) и (2):

С (12; 1/2)

Подставим найденные координаты точки С в целевую функцию:

Найдем координаты Точки Д. Для этого решим систему, составленную из уравнений (3) и (6):

Д (15; 0)

Подставим найденные координаты точки Е в целевую функцию:

Среди всех найденных значений целевых функций выбираем наименьшую.

Функция W принимает минимальное значение в точке Д; .

Решим данную задачу, используя теорему двойственности

Т. к. y1>0, то х1+х2+х3+3х4=4

Т. к. y2>0, то 2х1+4х2+6х3+х4=18

F(x)=G(y)= 57 - первая теорема двойственности выполнена, приведенный в условии план является оптимальным.

Проанализируем использование ресурсов:

Подставим y1 и y2 в систему ограничений двойственной задачи.

Оставим систему с x3 и x2:

F(x) = 9*0 + 14*3 + 15*1 + 5*0=57

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

Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план, причем экстремальные значения целевых функций равны: .

В нашем случае: при решении исходной задачи симплекс-методом была получена функция , а т. к. по теореме двойственности, то, что мы и получили, решая двойственную задачу графическим методом.

Похожие статьи




Теоремы двойственности и их использование в задачах ЛП - Решение оптимизационных экономических задач методами линейного программирования

Предыдущая | Следующая