Задачи ЛП и методы их решения

31

3.4. Метод искусственных переменных. Вспомогательная задача ЛП.

В рассмотренном выше примере столбцы матрицы ограничений при дополнительных переменных x3, x4, x5 образовывали единичную подматрицу

Выбирая дополнительные переменные в качестве базисных легко получить начальное базисное решение

x3 = 24 , x4 =12, x5 = 8 - значения базисных переменных равны соответствующим элементам вектора правой части в системе ограничений;

x1 = 0, x2 = 0- значения небазисных переменных равны нулю;

и заполнить начальную симплекс-таблицу.

В общем случае (например для ЗЛП в стандартной форме)

f = x1 − 2x2 + 4x3 + 6x4 → max

для нахождения начального базисного решения и заполнения начальной симплекс-таблицы необходимо проделать следующее:

а) Выбрать столбцы матрицы ограничений, составляющую квадратную матрицу (их число должно быть равно числу ограничений).

Например

б) Убедиться в том, что они (выбранные столбцы) образуют базис (путем нахождения обратной матрицы), либо установить их линейную зависимость.

Так, столбцы A2 и A3 не образуют базис в силу их линейной зависимости (в данном случае они просто равны между собой), а матрица в (**) не является базисной. С другой стороны, столбцы A1 и A2 линейно независимы (они не пропорциональны друг другу) и обратную матрицу к базисной в (*) можно найти путем приведения исходной базисной матрицы к единичной по методу полного исключения Гаусса-Жордана.

34

и ее целевая функция ограничена снизу нулем. А, следовательно, такая задача ЛП всегда разрешима.

Пусть X * = (x1* , x2* , x3* , x4* , x5* , x6* ) оптимальное решение задачи (i),

а g(X * ) - минимальное значение целевой функции. Если при этом g(X * ) = 0 и

искусственные переменные x5 , x6 , не входят в число базисных ( x5* = 0, x6* = 0 ), то

X0 = (x1* , x2* , x3* , x4* )

является начальным базисным решением исходной ЗЛП (+).

Построение начальной симплекс-таблицы для ЗЛП (i) трудностей не вызывает, т.к.

f

ШАГ 3. Переходим к новому базисному решению с базисом {5, 1}.

ШАГ 3. Переходим к новому базисному решению с базисом {2, 1}.

35

Если теперь отбросить часть С-Т, относящуюся к искусственным переменным, заменить коэффициенты в целевой функции из ЗЛП (+) и пересчитать последнюю строку (значение целевой функции и оценки), то получим С-Т для улучшения начального базисного решения

X0 = (2, 0, 0, 0)

исходной ЗЛП (+).

2 0 0 -6 -5

f

ШАГ 1. 3 < 0 . Текущее решение не является оптимальным.

ШАГ 3. Переходим к новому базисному решению с базисом {3, 1}.

f

37

Текущее решение является оптимальным решением задачи (i) и gmin =1> 0. Следовательно, исходная ЗЛП(+) не имеет ни одного допустимого решения. Действительно, левая часть 2-го уравнения в системе ограничений ЗЛП (+) может быть получена, если 1-ое уравнение умножить на 3. Тогда имеем

6x1 + 9x2 +15x3 = 906x1 + 9x2 +15x3 = 91

Ясно, что данная система несовместна. h

38

4. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

Рассмотрим частный случай задачи линейного программирования, которая получила название транспортной задачи (ТЗ). Модификация симплекс-метода для ее решения называется методом потенциалов.

Если какая-либо коммуникация отсутствует, то считаем, что она есть, но цену перевозки на ней устанавливаем равной бесконечности (+ ∞ ). Это соглашение сделает невыгодным перевозку по ней и автоматически исключит данную коммуникацию из плана перевозок.

Экономическая постановка ТЗ

Требуется составить план перевозок продукции от поставщиков к потребителям так, чтобы

потребности потребителей были бы удовлетворены за счет вывоза запаса от поставщиков.

Цель - минимизация суммарной стоимости всех перевозок.

Итак, мы привели экономическую постановку транспортной задачи. Отметим один существенный момент. Если суммарный запас продукции, имеющейся у поставщиков,

совпадает с суммарной потребностью в продукции у потребителей, тогда транспортная задача считается закрытой (имеет место баланс запасов и потребностей). Если же баланс нарушается (не хватает запасов, или запасов излишек) задача называется открытой. Имея в виду тот факт, что метод потенциалов “работает” только для закрытых ТЗ, изложим способ сведения открытой ТЗ к закрытой. Суть этого способа очень проста. Так, например, при

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

120 + 70 = 190 ед. С другой стороны суммарная потребность составляет

60 + 100 + 80 = 240 ед.