![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теорема 3.4.
Если ИЗ разрешима, то разрешима и ДЗ и наоборот, причем Если ИЗ неразрешима, то ДЗ тоже неразрешима и наоборот.
Тогда ДЗ имеет вид (3.12, 3.14):
Предположим, что исходная задача имеет решение, т.е. существует ее оптимальный план x*. Приведем ИЗ к каноническому виду:
Ее решение может быть получено симплекс – методом, т.к. расширенная матрица системы (2´) имеет вид К -матрицы.
На S -ой итерации симплекс-метода получим матрицу
или в развернутом виде эти матрицы можно представить:
Вектор Векторы Следовательно, матрицу
Матрица
т.е. вся необходимая информация может быть получена с помощью матрицы Так как на S-ой итерации получен оптимальный опорный план, то отвечающие матрице
Или с учетом (3.17) получим:
Обозначим
Покажем, что вектор Действительно, рассматривая первые n неравенств (3.20) и записывая их в векторно-матричной форме, имеем:
Аналогично, рассматривая неравенства (3.20) для j=n+1, n+m и учитывая, что
получаем
или
Из (3.22) и (3.24) следует, что - Далее, т.к.
Пусть ИЗ не имеет решения. Предположим противное, что ДЗ имеет решение, тогда по доказанному в первой части теоремы его имеет и ИЗ. Что противоречит условию теоремы. Следствие 1. Из выражения (3.23)
следует, что i-ая компонента Следствие 2. Из выражения (3.21) следует, что j-я симплекс-разность матрицы
Следствие 3. Из теорем 3.3 и 3.4 следует, что равенство целевых функций ИЗ и ДЗ является необходимым и достаточным условием оптимальности планов обеих задач.
|