Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

4.8. Приведение задач со смешанными ограничениями к эквивалентным задачам основного вида

Запишем задачи (4.18) и (4.19) в следующей форме: min[+.],

(4.18)
(4.19)

Обозначения x1, x2, c1, c2, b1, b2, A11,..... т. д. естественны; например, x1-вектор, составленный из тех компонент xj вектора х, для которых j∈J1; этому х1 соответствует с1 и т. д.

Понятны и обозначения клеток матрицы


Для приведения будем каждое равенство (например, φ=0) заменять двумя неравенствами (φ≥0 и -φ≥0 или φ≤0 и -φ≤0), а вместо переменной u, на которую не наложены условия не отрицательности, будем вводить неотрицательные переменные ū и ū̄ следующим образом: u=ū-ū̄, где

ū = max {u, 0} ≥ 0 и ū̄ = max{-u, 0} ≥ 0.

Итак, сделаем следующие замены переменных:


Вводя эти переменные и заменяя равенства соответствующими системами неравенств, приведем задачи (4.18) и (4.19) к следующему виду:

(4.20)
(4.21)

Ясно, что (4.20) и (4.21) образуют двойственную пару задач линейного программирования основного вида.

Нетрудно убедиться, что задачи (4.18) и (4.19) эквивалентны задачам (4.20) и (4.21), а именно;

Если


оптимальны для (4.18) и (4.19), то


оптимальны для (4.20) и (4.21), и обратно.

2) Если допустимое множество для (4.18) пусто, то пусто допустимое множество для (4.20), и обратно.

3) Если целевая функция задачи (4.18) неограничена снизу на допустимом множестве, то неограничена снизу и целевая функция задачи (4.20), и обратно.

Утверждения 1) - 3) обосновываются элементарными рассуждениями, которые (в случае необходимости) читатель может провести самостоятельно.

Из эквивалентности этих задач вытекает, что все теоремы, доказанные для задач (4.20) и (4.21), остаются справедливыми и для задач (4.18) и (4.19).

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"