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

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

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

двойственный линейный программирование гомори

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

. Найти оптимальный план прямой задачи:

а) графическим методом;

б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).

. Построить двойственную задачу.

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

. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).

. Найти оптимальное целочисленное решение:

а) графическим методом;

б) Методом Гомори.

Сравнить значения функций целочисленного и нецелочисленного решений.

1. а) Найдем оптимальный план прямой задачи графическим методом

Решение: Изобразим на плоскости систему координат Ох₁х₂ и построим граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):

Область допустимых решений определяется множеством АВСDЕ.

Для линий уровня 2х₁ + 3х₂ = h (h - const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рисунке она проходит через начало координат) Так как задача на максимум, то перемещаем линию уровня в направлении вектора  до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L₆ и L₄, т.е. через точку . Для определения координат точки А решаем систему уравнений:

Это и будет оптимальным решением данной задачи, которому соответствует максимальное значение целевой функции Z_max:

.

. б) Найдем оптимальный план прямой задачи симплекс-методом.

Приводим задачу к каноническому виду. Умножим первое ограничение на -1:

Для этого в левую часть ограничений-неравенств типа «£» вводим по дополнительной переменной с коэффициентом (+1). В целевую функцию эти переменные входят с коэффициентом (0). Получаем

В 3-м ограничении отсутствует базисная переменная. Формулируем задачу искусственного базиса.

Полученную задачу будем решать модифицированным симплексным методом [1].

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

Находим начальное опорное решение. Для этого свободные переменные приравниваем к нулю х₁ = х₂ = 0. Получаем опорное решение Х₁ = (0,0,19,28,0,47,19) с единичным базисом

Б₁ = (А₃, А₄, А₇, А₆).

Вычисляем оценки разложений векторов условий по базису опорного решения,

Оценки векторов, входящих в базис, всегда равны нулю. Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываем в симплексную таблицу

Начальное опорное решение не является оптимальным, так как оценки D₁ = -4, D₂ = -1 для векторов А₁ и А₂ противоречат признаку оптимальности. Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов условий.

Определим, введение, какого из двух векторов приведёт к большему приращению целевой функции. Приращения целевой функции найдём по формуле . Вычислим значения параметра q₀₁ для первого и третьего столбцов по правилу Креко, получим q₀₁ = 1 при l = 2 и q₀₂ =4 при l =2. Находим приращение целевой функции при введении в базис первого вектора  и второго вектора . Следовательно, для наиболее быстрого нахождении оптимального решения необходимо ввести в базис опорного решения вектор А₂ вместо вектора базиса А₇.

Далее выполним преобразование Жордана-Гаусса с элементом х₂₂ = 1, получим второе опорное решение Х₂:

Так как оценки неотрицательны, построенный план оптимален.

Искусственные переменные выведены из базиса.

Оптимальное решение вспомогательной задачи - это х7=х8=0, max G=0.

Попутно построен опорный план исходной канонической задачи:

Вернемся к ней. Используем последнюю симплекс-таблицу, из которой исключим переменную х7 и изменим цены базисных переменных, взяв их из заданной целевой функции. Получим

План необходимо улучшить. Вводим в базис х5, выводим х6

Проверим план на оптимальность. Оценки неотрицательны, план оптимален.

Ответ: max Z(X) = 20 1/7 при Х*= (0; 6 5/7; 45 6/7; 61 4/7; 2 5/7; 0).

2. Построим двойственную задачу к исходной. Так как исходная задача на максимизацию, то приведём все неравенства системы ограничений к виду «£», для чего обе части 1-го и 3-го неравенств умножим на (-1). Получим

Составим расширенную матрицу системы

.

Найдём матрицу , транспонированную к А

.

Сформулируем двойственную задачу:

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

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

Так как прямая задача разрешима, то двойственная тоже имеет решение, и, в силу первой теоремы двойственности, . Найдем значения переменных.

Подставим найденное оптимальное решение Х*= (0; 6 5/7) в систему ограничений исходной задачи:

В силу условия 1 дополняющей нежесткости получаем: .

Получаем систему уравнений для нахождения оставшихся неизвестных:

Ответ: оптимальное решение двойственной задачи

. Найдем оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи. Решению двойственной задачи соответствуют оценки переменных х₃ - х₆..

Проверим утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают», то есть то есть равенство  выполняется.

. Двойственную задачу решим симплекс-методом.

Запишем задачу в каноническом виде.

Перейдем к канонической задаче. Из левой части второго неравенства вычтем дополнительную переменную, к левой части первого неравенства прибавим, перейдем к задаче на максимум. Получим

Сформулируем задачу искусственного базиса

Сформулируем вспомогательную задачу искусственного базиса. Ее решение даст нам опорный план исходной канонической задачи (см. [1])

Решаем вспомогательную задачу симплекс-методом: