Решение задач линейной оптимизации симплекс – методом
| Категория реферата: Рефераты по математике
| Теги реферата: диплом государственного образца, рассказы
| Добавил(а) на сайт: Холопов.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Требуется определить вектор [pic], обращающий в максимум
[pic]. (7.2) при условиях
AX=B; (7.3)
[pic]. (7.4)
Тогда двойственная задача – определить вектор [pic], обращающий в минимум f(Y)=YB (7.5) при условиях
[pic]. (7.6)
Транспонируя обе части неравенства (7.6), записанного в виде строки, и учитывая [pic], получим
[pic]. (7.7)
Отметим, что в двойственной задаче переменные yi могут быть и отрицательными.
Рассмотрим в качестве исходной задачу (2.12), (2.13). С учетом (7.1) и
(7.7) запишем
С = (120, 100, 150, 0, 0, 0, 0, 0), B = ([pic], [pic], [pic], [pic],
[pic]),
[pic]
[pic].
Двойственная задача имеет вид
[pic]; (7.8)
[pic] (7.9)
8. Формирование оптимального решения двойственной задачи на основе теоремы о двойственности
Оказывается, что для задач (7.2) - (7.4) и (7.5), (7.6), называемых двойственной парой, справедлива следующая теорема.
Теорема (первая теорема о двойственности). Если одна из задач
двойственной пары (7.2) - (7.4) и (7.5), (7.6) имеет решение, то другая
задача также разрешима. При этом для любых оптимальных планов [pic] и
[pic](здесь Мх, Му – множества планов соответственно прямой и двойственной
задач) задач (7.2) - (7.4) и (7.5), (7.6) имеет место равенство
[pic].
Если линейная форма одной из задач не ограничена (для F(X) – сверху, для f(Y) - снизу), то другая задача не имеет ни одного плана.
Оптимальное решение двойственной задачи может быть найдено на основе следующего следствия из этой теоремы.
Следствие. Если вектор [pic] является оптимальным опорным планом задачи
(7.2) - (7.4), то вектор [pic] (8.1), является оптимальным опорным планом
задачи (7.5), (7.6).
Стоит отметить, что в ходе решения исходной задачи вторым алгоритмом, при каждом шаге вычисляется вектор [pic]. И если Х – оптимальный опорный план задачи (7.2) - (7.4), то в (m+1)-й строке, соответствующей основной таблице, находится решение задачи (7.5), (7.6).
Пусть двойственная задача имеет вид (7.8), (7.9).
Рекомендуем скачать другие рефераты по теме: доклад, курсовая работа на тему предприятие.
Категории:
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Главная