- •Оглавление
- •Краткая классификация моделей и методов математического программирования
- •Линейное программирование
- •1. Примеры экономических задач линейного программирования
- •1.1. Задача оптимального производственного планирования
- •1.2. Задача о смесях
- •1.3. Задача о раскрое
- •1.4. Транспортная задача
- •1.5. Вопросы для самопроверки
- •2. Некоторые сведения из линейной алгебры
- •2.1. Основные понятия и теоремы
- •Решение систем линейных алгебраических уравнений методом Жордана–Гаусса
- •3.3. Переход от задачи минимизации целевой функции к задаче максимизации
- •3.4. Переход от одной формы модели задачи линейного программирования к другой
- •3.4.1. Переход к канонической форме модели
- •3.4.2. Переход от канонической формы модели задачи линейного программирования к стандартной
- •3. 5. Выпуклые множества
- •4. Графический метод решения задачи линейного программирования
- •4.1. Геометрическая интерпретация множества решений линейного неравенства
- •4.2. Геометрическая интерпретация множества решений системы линейных неравенств
- •Возможные случаи области допустимых решений
- •4.3. Вопросы для самопроверки
- •5. Свойства допустимых планов задачи линейного программирования. Опорный план
- •Опорный план. Теорема о соответствии опорного плана вершине многогранника допустимых планов
- •6. Симплекс-метод
- •6.1. Идея симплекс-метода
- •6.2. Алгебра симплекс-метода
- •6.2.1. Алгоритм симплекс-метода
- •6.2.2. Выбор разрешающей строки в симплексных преобразованиях
- •6.2.3. Альтернативный оптимум
- •6.2.4. Признак неограниченности целевой функции
- •6.3. Понятие о вырождении
- •Примеры решения задач симплекс-методом
- •Пример 6.4. Решить симплекс-методом злп:
- •6.4. Вопросы для самопроверки
- •6.5. Индивидуальное задание
- •6.6. Задачи для самостоятельной работы
- •7. Двойственность в линейном
- •7.1. Пример двойственных задач линейного программирования
- •7.2. Правила построения двойственных задач
- •7.3. Симметричные двойственные задачи
- •Пример 7.3. Для задачи:
- •7.4. Основные теоремы двойственности
- •7.5. Анализ устойчивости двойственных оценок
- •7.6. Вопросы для самопроверки
- •7.7. Индивидуальное задание
- •Заключение
- •Библиографический список
- •Приложение. Применение программы Excel к решению задач линейного программирования
7.3. Симметричные двойственные задачи
Пусть модель исходной ЗЛП задана в стандартной форме:
(7.1)
Составим модель двойственной ЗЛП, используя правила, изложенные в п. 7.2.
Модель двойственной задачи примет вид:
(7.2)
Если ввести в рассмотрение матрицы:
,
то пара симметричных двойственных задач в матричной форме примет вид:
Прямая задача
|
Двойственная задача
|
Пример 7.2. Составить двойственную задачу к следующей ЗЛП:
и показать взаимосопряженность полученной пары двойственных задач.
Решение. Прежде всего приведем модель к виду, для которого изложены правила построения двойственных задач.
Преобразуем третье ограничение, умножив обе части неравенства на –1 и изменив знак неравенства на противоположный:
В результате исходная задача примет вид:
(7.3)
Согласно правилам двойственная задача будет содержать три переменные (они записаны справа от ограничений), причем , так как соответствуют ограничениям-неравенствам исходной задачи, а у2 является свободной переменной: у2 0 (у2 соответствует ограничению-равенству исходной задачи).
Матрицей системы ограничений двойственной задачи является матрица, транспонированная к исходной:
.
Правыми частями системы ограничений двойственной задачи станут коэффициенты (1, 2, –3, 1) целевой функции исходной задачи.
Каждой неотрицательной переменной исходной задачи соответствует ограничение-неравенство того же смысла:
Свободной переменной х4 соответствует ограничение-равенство:
х4 0 у1 – у2=1.
Коэффициентами целевой функции W двойственной задачи, которая (согласно правилам) минимизируется, становятся свободные члены системы ограничений исходной задачи.
Итак, математическая модель двойственной задачи примет вид:
(7.4)
Далее покажем взаимосопряженность полученной пары двойственных задач, т.е. покажем, что задача, двойственная к (7.4), совпадает с исходной (7.3).
Для этого прежде всего преобразуем модель (7.4) к виду:
Согласно правилам построения двойственных задач получим модель двойственной задачи:
|
|
Умножив обе части первых двух ограничений на –1 и введя функцию Z= –Z1, получим эквивалентную ЗЛП:
которая совпадает с исходной.
Таким образом, показана взаимосопряженность пары двойственных задач, что позволяет считать одну из них (безразлично какую) исходной, а вторую – двойственной к ней.
Пример 7.3. Для задачи:
составить двойственную и найти решение обеих задач.
Решение. Двойственной является задача:
Как в исходной, так и в двойственной задаче число неизвестных равно двум. Следовательно, их решение можно найти графическим методом.
Рис. 7.1. достигается в точке B
Рис. 7.2. достигается в точке Е
Как видно из рис. 7.1, максимальное значение целевая функция исходной задачи принимает в точке В. Следовательно, Х*=(3,7) является оптимальным планом, при котором Zmax=48.
В двойственной задаче (рис 7.2) ОДР не ограничена. Минимальное значение целевая функция двойственной задачи принимает в точке Е, т.е. и Таким образом, значения целевых функций исходной и двойственной задач при их оптимальных планах равны между собой.
Далее будет показано, что для любой пары двойственных задач, имеющих оптимальные решения, экстремальные значения целевых функций совпадают (Zmax=Wmin).