Первая теорема двойственности

Если одна из пары двойственных задач (I) и (II разрешима, то разрешима и другая задача, причем оптимальные значения целевых функций прямой и двойственной задач совпадают.

Доказательство проводится редукцией к каноническому случаю. Пусть – оптимальное решение исходной ЗЛП

Тогда вектор – оптимальное решение ЗЛП

Где ( такой, что его положительные координаты равны положительным координатам вектора , а остальные равны нулю, у вектора положительные координаты совпадают с координатами вектора , остальные равны нулю).

Следовательно существует вектор – оптимальное решение ЗЛП

Которая есть в точности ЗЛП, двойственная к исходной ЗЛП.

Следствия:

1. Eсли прямая задача не ограничена, то двойственная не имеет решений; аналогично если двойственная задача не ограничена, то прямая не имеет решений. Обратное не всегда верно!

2. Если то

x⁰ – решение прямой задачи

y⁰ – решение двойственной задачи

9. Вторая теорема двойственности. Теорема о маргинальных значениях. Анализ чувствительности решений

Вторая теорема двойственности

Допустимые решения и соответственно исходной и двойственной ЗЛП оказываются оптимальными в том и только том случае, когда выполняются условия дополняющей нежесткости:

1. Если , то

2. Если , то

Доказательство.

Необходимость. Справедливые для произвольных допустимых решений неравенства

Для оптимальных решений в силу первой теоремы двойственности превращаются в равенства, которые после соответствующих преобразований можно записать так

1.1.

2.1.

Но так как и – допустимые решения, то вторые слагаемые в обоих равенствах равны нулю, а сомножители, из которых состоят первые слагаемые, - неотрицательные векторы. Если скалярное произведение равно нулю, то не могут быть одновременно отличны от нуля координаты с одинаковым номером. Следовательно выполнены условия 1 и 2.

Достаточность.

Если условия 1 и 2 выполнены для допустимых решений и , то выполняются и равенства 1.2 и 2.1 производя обратные преобразования, получим:

Что и означат оптимальность рассматриваемых решений.

Для канонической ЗЛП: для того чтобы и – соответственно допустимые решения ЗЛП были оптимальными, НиД выполнения любого из условий:

1. Если , то

2. Если , то

Анализ чувствительности решения ЗЛП.

Пусть задача

Имеет оптимальное базисное невырожденное решение (т.е. все базисные переменные положительны)

Тогда при небольших возмущениях координат вектора b базисные переменные остаются положительными, т.е. найдет вектор , такой, что

Условия оптимальности базисного решения:

Не зависят от правых частей и при малом изменении вектора b базисное решение остается оптимальным, а значение целевой функции

Будет ЛЗ от вектора ( оптимальное решение двойственной ЗЛП). Аналогично, если базисное оптимальное решение таково, что условие оптимальности

Выполняется следующим образом: для всех свободных переменных, то при некотором возмущении условие оптимальности сохранится, а значение целевой функции будет ЛЗ от вектора .

Теорема о маргинальных значениях.

Частная производная оптимального решения прямой задачи по одной из правых частей ограничений равна соответствующей компоненте оптимального решения двойственной задачи.

Доказательство:

(1)

(2) (min)

Поделим на и перейдем к пределу.

чтд.

10. Транспортная задача. Общая постановка транспортной задачи. Свойства множества решений. Методы нахождения первой вершины. (выпуклость. Пример эпсилон-процедуры)

Транспортная задача линейного программирования.

Т ранспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта.A_i в пункт В_j, i 1, …, m; j 1, ..., n. Требуется составить такой план перевозок, чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, при минимальной общей стоимости всех перевозок. х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j.

,

Эта задача обладает всеми свойствами линейной. Оптимальные решения ищем в вершинах, оптим-я из уже найденной вершины).

Методы нахождения первой вершины

Метод северо-западного угла

При построении исходного распределения с помощью данного метода, из оставшихся клеток выбирается левая верхняя клетка (северо-западная). На первом этапе выбирается клетка (1,1). В эту клетку записывается объём поставки х11= min {А1,В1}. Величины А1 и В1 уменьшаются на данную величину. Ту строку или столбец, где будет получен 0, удаляют из рассмотрения. Затем из оставшихся клеток, рассматривают левую верхнюю

клетку и поступают аналогично. Продолжая данный процесс, мы заполним клетку (m,n), причем удалим из рассмотрения и строку и столбец. Если в процессе заполнения клеток придётся вычеркнуть и строку, и столбец, то мы получим вырожденное распределение (количество занятых клеток меньше, чем m+n-1). Чтобы этого не произошло, из рассмотрения удаляем что–то одно: или строку, или столбец, а оставшийся столбец или строку считают с нулевой потребностью или запасами

Метод минимального элемента отличается от предыдущего метода тем, что из

оставшихся клеток выбирается клетка, имеющая наименьшие удельные затраты.