<<
>>

15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ

Объем вычислительных операций при практическом решении задачи линейного программирования может оказаться очень большим. Поэтому важно внимательно и упорядоченно расположить данные и подготовить их для обработки на быстродействующих вычислительных машинах.
Общая задача линейного программирования рассмотрена в разделе 15.4: требуется максимизировать или минимизировать некоторую линейную функцию неотрицательных переменных при условии удовлетворения некоторой системы линейных неравенств. Первый шаг состоит в том, чтобы представить задачу в несколько иной форме: линейная функция неотрицательных переменных должна максимизироваться при условии удовлетворения системы линейных уравнений. Всякую задачу можно подвергнуть такому преобразованию: вначале задачу на минимум (если такой ее характер предусмотрен) превращаем в задачу на максимум, а затем вводим «добавочные переменные», обращая таким образом неравенства в уравнения. Сущность этого метода в достаточной степени можно проиллюстрировать на простом примере (см. 15.3) двух переменных и двух неравенств; общий случай рассматривается в упражнениях 2 и 3.

Решим следующую задачу линейного программирования:

Минимизировать выражение

РгЧ + РтР 2

при условии

a11x1-\-al2x2>bl, a12x1 + a22x2>b2, #!>(), х2>0.

Во-первых, введем обозначения сх— — pt и с2 — — р2, так что требуется уже максимизировать

Z = С^Х-^ 4" ^2*^2*

Далее, введем новые переменные: К1 = х19 Х2 — х2, — неотрицательную переменную разность (а11Х1 + а12Х2) — Ьх и ^—аналогичную разность (ааА + а22^г) — К Тогда

аііЛі ~t~ а12^2 ~~ =

а21Х1-\-а22Х 2 — Я4 = &2.

Наконец, представим z = c1'k1 + с2Х2 в более общем виде z = с^ + саА,а+ + с3А,3 + с4Я,4, где с3 = с4 = 0. Тогда задача линейного программирования представится в следующем виде: Максимизировать

Z = сг%х + с2Х2 + с3А,3 + с4А,4

при условии

+ а12^2 — ^3 —

а21^1 + а22^2 ^4 ^ ^2'

^>0, Х2>0, Я3>0, Х4>0.

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

Из четырех переменных две суть первоначальные, а остальные две —добавочные, условные переменные, введенные для удобства вычислений. Последние мы назовем вспомогательными или дополня- ющими (slack) переменными. Матрица технологических коэффициентов, ранее

квадратная второго порядка, теперь превращается в матрицу типа 2x4:

А-Ь *12 "о П-

Kl «22 0 -1J

Рассмотренную нами общую задачу линейного программирования можно записать следующим образом: Максимизировать

z = c'X при условии

(1)

АХ = Ь )

Ь>0, где А — соответственным образом расширенная матрица тхп технологических коэффициентов, Ь — вектор т-то порядка потребностей и имеющихся ресурсов, с —вектор /1-го порядка, характеризующий поставленную цель или максимизируемую функцию, и Л, —искомый вектор неизвестных /г-го порядка. Если учесть, каким способом мы увеличили число переменных, то можно считать m < /г, как это и принято далее. В основном выводе, принадлежащем Гейлу и доказанном простым способом Дано [4], утверждается, что в решении (оптимальном) задачи (1),. если оно существует, имеют положительные значения не более чем m (из общего их числа п) переменных X.

Удобнее (по крайней мере для вычислений) представить (1) в линейной форме относительно векторов m-го порядка с п коэффициентами. Расширим матрицу А, добавив справа столбец Ъ: тогда матрица А станет mx(n-\-i). Обозначим через p*s> (5= 1, 2, . . ., п) и р иг-мерные столбцы этой матрицы коэффициентов: «in Ь1

[р^р*2* ... р(«>р] =

(2)

"11 "12 «21 «22 • • • «2тг ^2 L«ml «т2 • • • «тп ^т-

Тогда задача линейного программирования может быть представлена в следующем виде:

найти неотрицательные значения ks>0 (5 = 1, 2, ... /г), максимизирующие выражение

z = c1X1 + c2X2+...+cnXn (3)

при условии

^iP(1) + Kv{2) + ... + Kv(n) = p. (4)

В уравнениях (3) и (4) также можно применить знак 2» то есть максимизировать

п

z=2 с А

s=i

при условии

2 ^р(3) = р-

5= 1

При такой постановке задачи мы пользуемся векторами m-ro и п-го порядка, где т<п.

Эти векторы изображаются точками в двух пространствах—соответственно т- и п-мерном. Эти «геометрические» термины все время применяются в дальнейшем, и мы можем воспользоваться теорией выпуклых множеств. Следует проводить четкое различие между двумя пространствами. I.

Пространство условий или требований иг-мерное, то есть низшей размерности (иг < п). Точки этого пространства р(1\ р<2>,..., р<п> и р определяются технологическими коэффициентами (матрица А) и потребностями Ь в матрице (2). Все это—известные данные задачи, входящие в уравнения (4). II.

Пространство решений w-мерное, то есть высшей размерности (п > т). Кроме точки с = (с1? с2,..., сп), соответствующей максимизируемой линейной функции (3), это пространство содержит ТОЧКИ X = (Xl,

элементы которых — искомые переменные. Эти элементы являются переменными в выражении (3), а также коэффициентами при заданных векторах в уравнении (4).

Всякая точка І,, удовлетворяющая уравнению (4), называется допустимим решением задачи; она не обязательно максимизирует функцию (3). Такое допустимое решение, которое максимизирует функцию (3), называется оптимальным допустимым решением; именно такую точку мы и стремимся найти. Общий метод решения заключается в том, чтобы сначала сосредоточить внимание на множестве всех допустимых решений, а затем — на тех допустимых решениях, которые оптимальны. Мы увидим далее, что множество допустимых решений есть выпуклое множество и что оптимальное решение следует искать среди экстремальных точек этого множества. Таким образом, здесь непосредственно применима теория выпуклых множеств.

Удобно пользоваться следующими терминами. Связь переменных решения % с заданными векторами (или точками) р в уравнении (4) можно определить, сказав, что к8 есть вес вектора (или точки) p (в иг-мерном пространстве) в решении X. Поскольку Xs>0, решение может иметь некоторые p(s> с положительными и некоторые с нулевыми весами, что соответствует положительным и нулевым значениям переменных в решении.

Оказывается, что важно различать положительные и нулевые веса.

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

Общую задачу линейного программирования (см. 15.4) можно сформулировать относительно N переменных при М ограничениях (линейных неравенств). Предположим, что все ограничивающие соотношения являются неравенствами, а уравнений среди них не имеется. Тогда эта задача, приведенная к канонической форме, будет иметь п = М + N переменных (из них М дополняющих переменных) и т = М линейных уравнений (см. упражнение 2). Следовательно, в канонической системе т < п. Это предложение справедливо и для двойственной задачи (см. упражнение 3).

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

Однако может оказаться, что это не так, если в представленной в общем виде (см. 15.4) задаче линейного программирования (с N переменными, подчиняющимися М ограничениям) некоторые или все ограничивающие соотношения уже с самого начала являются уравнениями, а не неравенствами. Тогда после приведения задачи к канонической форме может оказаться, что /п>тг, и допустимые решения определяются из системы уравнений, число которых не меньше, чем число переменных (см. упражнение 4). В этом случае, если уравнения совместны, возможно существование только одного допустимого решения, а если несовместны — даже полное отсутствие допустимых решений.

Обобщим сказанное: если в общей задаче линейного программирования все ограничения выражаются неравенствами, то в канонической ее форме

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

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

Задачи и упражнения 1.

Привести к канонической форме (1) двойственную задачу с двумя переменными (см. 15.3) и показать, что при этом число переменных увеличивается до четырех (в том числе две дополняющие переменные), а число ограничивающих уравнений равно двум. 2.

Общая задача линейного программирования состоит в том, чтобы найти N переменных х, минимизирующих функцию z = p'x при условии выполнения М ограничений Ах > Ь. Привести эту задачу к канонической форме с п переменными и т уравнениями. Если все М исходных ограничений выражены неравенствами, показать, что т — М и п= М + iV, а следовательно, что т < /г. 3.

Двойственная задача из предыдущего упражнения состоит в том, чтобы найти М переменных максимизирующих функцию ? — Ь'§ при условии выполнения N ограничений А'|<р. Привести задачу к канонической форме с п' переменными, подчиненными ш' уравнениям, и показать, что т' —N и п' = М + N, если все исходные ограничения являются неравенствами. Доказать, что прямая и двойственная ей задача линейного программирования, выраженные в канонической форме, имеют одинаковое число переменных, но различное число ограничивающих уравнений. 4.

Пусть в общей задаче линейного программирования (задача 2 настоящего раздела) с N переменными некоторые из исходных М ограничений выражены уравнениями. Показать, что после приведения к канонической форме может случиться, что т > п, рассматривая следующие возможные варианты:

а) М. =2 N и все ограничения суть уравнения (т=га);

б) M>N и N ограничений суть уравнения (т — п)\

в) M>N и более чем N ограничений суть уравнения (га>га).

<< | >>
Источник: Р. Аллен. МАТЕМАТИЧЕСКАЯ ЭКОНОМИЯ. 1963

Еще по теме 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ:

  1. ГЛАВА 15 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
  2. 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  3. 15.2. ПРОСТОЙ ПРИМЕР: ДВОЙСТВЕННАЯ ЗАДАЧА
  4. 15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ
  5. 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  6. 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ
  7. 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
  8. 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  9. 16.3. ПРЕДСТАВЛЕНИЕ ОТКРЫТОЙ СИСТЕМЫ ЛЕОНТЬЕВА В ВИДЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ОТРАСЛЕЙ
  10. 16.4. ЗАМЕНЯЕМОСТЬ В ОТКРЫТОЙ СИСТЕМЕ ЛЕОНТЬЕВА
  11. 16.9. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ; МОДЕЛЬ РОСТА НЕЙМАНА
  12. 17.3. ПРЕДЕЛЬНЫЙ АНАЛИЗ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ДЕЯТЕЛЬНОСТИ ФИРМЫ
  13. 17.4. ТЕХНОЛОГИЯ ФИРМЫ
  14. 17.5. ДВЕ ИЛЛЮСТРАТИВНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  15. 17.6. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ФИКСИРОВАННЫХ ФАКТОРОВ И ЗАДАННЫХ ЦЕН НА ПРОДУКТЫ
  16. 17.7. ПАРАДОКС РИКАРДО
  17. 17.8. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ СЛУЧАЯ НЕИЗМЕННОЙ 3 СТРУКТУРЫ СПРОСА