Chernov_-_Vvedenie_v_LP

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

ВОПРОСЫ И УПРАЖНЕНИЯ

1.Каковы задачи разделов постоптимизационного анализа?

2.Что показывают критические границы цен? Что показывают критические границы ресурсов?

3.Как при принятии решений используется знание теневых цен (двойственных оценок)?

4.Для модели, приведенной в упражнении 9а п. 3.6, придумайте самостоятельно исходную содержательную экономическую задачу. Проведите постоптимизационный анализ решения на языке вашей исходной постановки.

5.Для моделей, приведенных в упражнениях 9 б, в, г п. 3.6, проведите постоптимизационный анализ решения, не используя содержательные экономические понятия, а пользуясь терминологией линейного программирования ("значение целевой функции" вместо "доход", "правая часть ограничения" вместо "объем ресурса" и т.п.).

101

4. Симплекс-метод решения задач линейного

программирования

4.1. Общая характеристика симплекс-метода

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

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

Мы рассмотрим такой метод в его наиболее простом варианте. Это так называемый симплекс-метод решения задач линейного программирования.

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

В последовательности преобразований модели выделяют этапы. Результатом этапа является такая форма записи модели, с которой

102

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

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

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

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

4.2. Пример решения задачи линейного программирования

симплекс-методом

Рассмотрим наш пример с производством коктейлей. Напомним математическую модель задачи:

Приведем ее к канонической форме. Получим:

103

Новые переменные имеют ясный смысл - это недоиспользованные объемы ресурсов. Каждая такая переменная присутствует лишь в своем ограничении, причем коэффициент при такой переменной равен 1.

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

Внашем случае базисные переменные - это x3, x4, x5. Небазисные переменные - это x1, x2.

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

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

Внашем примере текущий опорный план имеет следующие компоненты:

x1 = 0, x2 = 0, x3 = 108, x4 = 48, x5 = 22.

В векторной записи это пятимерный вектор X0:

X0 =(0; 0; 108; 48; 22).

104

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

Очевидно, план X0 является допустимым, он удовлетворяет всем ограничениям системы. Чтобы получить его образ в системе координат на рис. 7, достаточно изобразить точку, определяемую его первыми двумя компонентами. Плану X0 соответствует точка (0; 0), начало координат, одна из вершин области допустимых планов.

Обращение к чертежу, однако, не является необходимым. Более того, симплекс-метод ориентирован в первую очередь именно на решение многомерных задач, когда чертежи не приносят пользы. Все же, мы будем иногда ссылаться на рис. 7, просто, чтобы придать рассуждениям большую наглядность и сопоставить результаты с теми, которые были получены графическим методом.

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

z 12x1 10x 2

в равносильной форме

z 12x1 10x 2 0 .

В результате математическая модель примет следующий вид:

105

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

Вобщей форме запаси задачи присутствует m ограничений. Новое ограничение получает при этом номер m + 1. Чтобы подчеркнуть его особую роль, мы сохраняем этот его общий номер m + 1 вместо номера 4.

Как мы увидим, на основе этого ограничения устанавливается критерий (признак) оптимальности текущего опорного плана. Это ограничение часто называют критериальным.

Рассмотрим значение целевой функции z на опорном плане X0. Для этого подставим значение компонент плана X0 в критериальное (m + 1) -е ограничение. Получим z0 = 0. Является ли это значение максимально возможным? Другими словами, мешает ли что-нибудь увеличению значения z?

Всистеме ограничений переменная z присутствует лишь в критериальном ограничении. При увеличении z это ограничениеравенство не должно нарушаться. Поскольку в это равенство входят переменные x1 и x2 с отрицательными коэффициентами, то увеличение z можно компенсировать одновременно в нужной пропорции увеличивая, например, значение одной из переменных, x1 или x2.

Заметим сразу, что если бы все переменные xj, входили в критериальное ограничение с неотрицательными коэффициентами, то

106

увеличить значение z было бы невозможно. Это означает, что текущий опорный план был бы оптимальным.

Мы получили критерий оптимальности текущего опорного плана: текущий опорный план оптимален, если все переменные x j , входят в критериальное огран ичение с неотрицательными коэффициентами. Это признак конца процедуры решения задачи.

Рассмотрим увеличение значения z и одновременное компенсирующее увеличение значения одной из переменных, например, x1.

Существуют ли какие-нибудь препятствия увеличению значения x1? Если таких препятствий нет, если значение x1 можно увеличивать неограниченно, то неограниченно можно увеличивать и значение z. Это означает, что целевая функция на множестве допустимых планов неограниченна, любой план может быть улучшен, самого лучшего, оптимального плана, дающего максимальное значение целевой функции, не существует. Задача в этом случае решения не имеет.

В нашем случае это не так. Переменная x1 входит еще в три ограничения, каждое из которых может создавать свои препятствия росту ее значения. Рассмотрим эти ограничения поочередно.

Для того чтобы выполнялось первое равенство, рост x1 должен компенсироваться уменьшением других переменных. Но значение переменной x2 и так равно 0. Отрицательными значения переменных быть не могут по условию модели.

Следовательно, рост x1 должен компенсироваться уменьшением базисной переменной x3 в соответствующей пропорции. Однако значение x3 не может уменьшаться беспредельно, нижней границей значений переменных является 0. Таким образом, значение x1 может расти лишь до некоторой верхней границы. Ее можно определить, положив в первом ограничении все остальные переменные равными 0.

Получим:

0,675x1 108,

107

откуда

x1 0108,675 160 .

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

Первое ограничение дает возможность роста переменной x1 до величины 160.

Во втором ограничении рост значения переменной x1 должен компенсироваться уменьшением значения другой базисной переменной x4.

Рассуждая аналогичным образом, получим новую верхнюю границу роста значений переменной x1

x1 48 240 . 0,200

В третьем ограничении рост x1 компенсируется уменьшением значения базисной переменной x5. Граница роста x1 определяется аналогично. Она равна:

При росте значения переменной x1 должны выполняться все ограничения. Это означает, что из трех полученных верхних границ нужно выбрать наименьшую,

min 160; 240; 176 .

Значение переменной x1 может быть поднято до величины 160. Из критериального ограничения следует, что значение целевой функции z может быть при этом поднято от 0 до 1920.

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

108

разобраться с этим вопросом и подготовить запись системы ограничений

идальнейшему анализу, следует ее преобразовать.

Воснове преобразования лежит метод Гаусса. Будут пересчитаны коэффициенты при переменных и свободные члены ограничений.

Мы анализировали возможности роста переменной x1. Столбец коэффициентов при этой переменной, то есть столбец

называется разрешающим столбцом.

Элементы этого столбца участвовали в определении наименьшей границы роста переменной x1. Каждое ограничение дало свою границу, но наименьшая среди них (равная 160) возникла в первом ограничении.

Поэтому само это первое ограничение в процессе дальнейших преобразований будет называться разрешающим ограничением (разрешающей строкой), а элемент 0,675, находящийся на пересечении разрешающих столбца и строки, будет называться разрешающим элементом. Это тот самый элемент, при делении на который правой части ограничения возникла наименьшая граница

160 0108,675 .

Целью эквивалентного преобразования системы ограничений методом Гаусса является приведение системы к такому виду, когда переменная x1 становится базисной, причем на месте разрешающего элемента возникает 1, а на месте всех остальных элементов разрешающего столбца возникают нули.

Для этого сначала разрешающая строка (разрешающее равенство) делится на разрешающий элемент. В нашем случае первая строка

109

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

Мы не будем здесь и в дальнейшем дописывать неравенства, требующие неотрицательности переменных xj. Эти требования будут постоянно подразумеваться.

Приступим к преобразованию системы ограничений методом Гаусса. Разделим первую строку на 27/40.

Получим:

x1 23 x 2 2740 x 3 160 .

На месте разрешающего элемента возникло число 1. Теперь преобразуем поочередно все остальные строки так, чтобы остальные элементы разрешающего столбца стали равны 0. Для преобразования второй строки следует из нее вычесть преобразованную разрешающую строку, умноженную предварительно на 1/5.

Получим:

0 x1 154 x 2 278 x 3 x 4 16 .

110