ній способ доводитися, що - оптимальний план двоїстої задачі.
3.1 Перша теорема двоїстості
Теорема ( перша теорема двоїстості ). Если одна з парі спряжених задач має оптимальний план, то й друга задача такоже має розв'язок, причому для оптимальних розв'язків Значення цільовіх функцій обох завдань збігаються, тоб.
Если цільова функція однієї Із завдань Необмежена, то спряж завдання такоже НЕ має розв'язку.
Доведення . Припустимо, что початкова задача (3.1) - (3.3) має оптимальний план, Який отриманий симплексним методом. НЕ порушуючі загальності, можна вважаті, что Останній базис Складається з дерло m векторів. Остання симплексній таблиці має вигляд:
В
Таблиця 3.1
и
Базис
Сб
План
з1
с2
...
сm
cm + 1
...
cn
x1
x2
...
xm
xm + 1
...
xn
1
x 1
В В
1
0
...
0
В
...
В
2
x 2
В В
0
1
...
0
В
...
В
m
xm
В В
0
0
...
1
В
...
В
m + 1
В
F0
0
0
...
0
В
...
В
Позначімо через D матрицю, что утворена з компонент векторів А1, А2, ..., Аm последнего базису в першій сімплексній табліці.
Для оптимального плану отрімаємо:
(3.12)
де, В- вектор, что Складається з вільніх членів системи обмежень.
Звідсі:
(3.13)
симплексній таблиці 3.1 містіть КОЕФІЦІЄНТИ Розкладу векторів початкової системи обмежень задачі за векторами базису, тоб шкірному вектору з системи обмежень задачі (3.1) - (3.3) Аj відповідає в сімплексній табліці вектор, такий что
(3.14)
Позначімо через матрицю, что Складається з Коефіцієнтів Розкладу векторів. Тоді буде справджуватіся Рівність:
, Звідки
. (3.15)
ВРАХОВУЮЧИ (3.13), значення оптимального плану даної задачі знаходится у вігляді:
В
де, причому
В
,
тоб ВСІ компоненти вектора є оцінкамі оптимального планом задачі (3.1) - (3.3), а тому
. (3.16)
Оскількі оптимальний план початкової задачі подано у вігляді, то за правилами Побудова двоїстої задачі можна допустити,, что ее оптимальний план матіме вигляд:
. (3.17)
Доведемо, что Дійсно є оптимальним планом двоїстої задачі.
Система обмежень двоїстої задачі у векторно-матрічній ФОРМІ матіме вигляд:.
Підставімо в Цю нерівність значення. Тоді, ВРАХОВУЮЧИ (3.15), (3.16) та (3.17), отрімаємо:. p> Звідки:. Отже, задовольняє систему обмежень (3.5) двоїстої задачі, тому є допустимим планом задачі (3.4) - (3.6).
Для даного плану Значення функціонала дорівнюватіме:
, (3.18)
де. Підставімо в (3.18) значення з (3.17) та, ВРАХОВУЮЧИ (3.13), матімемо:
. (3.19)
Доведено, что збігається Зі значеннями оптимального плану початкової задачі.
