Теория двойственности

Любой задаче линейного программирования, называемой исходной, можно поставить в соответствие другую задачу, которая называется двойственной. Обе эти задачи образуют пару двойственных задач. Каждая из задач является двойственной к другой задаче.

Алгоритм составления двойственной задачи:

1) Привести все неравенства ограничений исходной задачи к единому смыслу: если в исходной задаче ищется максимум линейной функции, то все неравенства системы ограничений привести к виду «≤», а если минимум – к виду «≥». Для этого неравенства, в которых данное требование не выполняется, умножить на -1.

2) Составить расширенную матрицу системы – А, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3) Найти матрицу А` транспонированную к матрице А

4) Сформулировать двойственную задачу на основании полученной матрицы А` и условия неотрицательности переменных.

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

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

II Задание: Решить графическим методом задачу с двумя переменными.

Z(х)=4х₁+13х₂+3х₃+6х₄ → min

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

-5х₁+3х₂-х₃+2х₄+х₅ = -1

9х₁-4х₂+2х₃-3х₄+х₆ = 6

Учитывая условия неотрицательности:

х_j ≥ 0, j=1,2,3,4.

Для решения данной задачи необходимо перевести систему ограничений в стандартный вид путём введения дополнительных переменных:

-5х₁+3х₂-х₃+2х₄+х₅ ≥ -1

9х₁-4х₂+2х₃-3х₄+х₆ ≥ 6

Составим расширенную матрицу системы уравнений

-5 3 -1 2 1 0 -1