Решение симметричных задач линейного программирования

Решение неканонических задач линейного программирования

Решение симметричных задач линейного программирования

Пусть необходимо решить задачу линейного программирования в симметричной форме записи:

(1)

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

Преобразуем задачу (1) к каноническому виду. Добавим в левые части неравенств системы , так называемые дополнительные переменные . Получим, таким образом, следующую каноническую задачу линейного программирования:

(2)

Легко убедиться, что задачи (1) и (2) эквивалентны.

Заметим, что система векторов является базисом, а в силу неотрицательности всех он допустим, то есть опорное решение является опорным планом задачи (2).

Отметим еще одну особенность задачи (2). Пусть симплексным методом найдено ее решение. Тогда для оптимального базиса справедливы равенства . (В справедливости

этих равенств убедитесь самостоятельно.) Следовательно, вектор является решением задачи двойственной к задаче (1).

Прежде, чем перейти к другим неканоническим задачам, заметим следующее. Часто матрица задачи линейного программирования имеет столбцы, которые удобно включить в исходный базис. В таких случаях нет надобности вводить полный искусственный базис, а только лишь достроить уже имеющуюся часть базиса до полного введением некоторого числа искусственных переменных. Иногда этого удается добиться элементарными преобразованиями системы ограничений задачи. Если такие преобразования выполнить легко, то можно добиться заметной экономии при дальнейших вычислениях. Учет специфики конкретной задачи, опыт решения разнообразных задач линейного программирования могут помочь найти удачный способ преобразования задачи вместо введения полного искусственного базиса. Далее приведем пример задачи, где целесообразны предварительные преобразования.

5.2 Решение задач линейного программирования с ограничениями вида

Укажем один тип задач линейного програм-мирования, для которых простые предварительные преобразования могут позволить обойтись не

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

(3)

Предположим, что все координаты вектора неотрицательны. Очевидно, что сведение задачи (3) к симметричной форме записи умножением на –1 каждого неравенства системы не позволит использовать прием, описанный в пункте 5.1. Поэтому, прежде всего, преобразуем задачу (3) к каноническому виду. Для этого введем дополнительные переменные , вычитая их из левых частей соответствующих неравенств системы . Получим, таким образом, следующую каноническую задачу:

(4)

Далее, выберем номер одной компоненты вектора так, что и преобразуем систему уравнений задачи (4) следующим образом. Заменим каждое -тое уравнение () в этой системе на разность -ого и -ого уравнения, уравнение с номером оставим без изменения. Получим задачу

(5)

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