<<
>>

Линейное программирование как аналитическая технология оптимизации

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

Adam, 1996). В то время как дифференциальное исчисление свое типичное применение находит в классических моделях теории производства и издержек (см. гл. 5 (С), разд. I), а также теории цен (см. гл. 5 (D), разд. II), линейное программирование является все более признанным на практике инструментом для решения комплексных проблем принятия решения. В качестве специальных предпосылок для внедрения этой аналитической технологии оптимизации следует назвать следующие: Целевая установка ситуации принятия решения может быть представлена в виде линейной функции. Переменные присутствуют"только в первой степени и не связаны друг с другом умножением. Вспомогательные условия, ограничивающие задачу принятия решения, могут формулироваться как линейные уравнения и неравенства. Переменные величины задачи не могут опускаться ниже определенного уровня (обычно ниже нуля).

Ситуация принятия решения в общем виде может описываться следующим образом:

(1)

(2) где х. — переменная j задачи; с. — вклад переменой j в целевую функцию задачи; а(. — коэффициент переменной j в ограничений г; Ь. — максимальное значение ограничения г.

Решение подобной задачи при помощи симплекс-метода показано на следующем примере (см. Adam, 1996):

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

(4)

Целевую функцию надо максимизировать с учетом ограниченности производственных мощностей:

(5а)

(5Ь)

и условий неотрицательности переменных:

(6а)

lt;6Ь)

Для решения сформулированной таким образом математической проблемы в общем случае используется алгоритм симплекс-метода.

Однако в данном случае можно представить также графическое решение, так как задача принятия решения состоит только из двух структурных переменных. Это графическое решение должно быть продемонстрировано прежде всего из-за того, что оно помогает лучше понять механизм действия симплекс-метода (Miiller-Mebach, 1973).

В двухмерной координатной системе на оси абсцисс размещается переменная*,, а на оси ординат — х2 (см. рис. 93). На первом шаге на чертеж наносятся ограничения. Так как в примере речь идет о неравенствах, то отделяют допустимую область решения от недопустимой. В комбинации с условиями неотрицательности можно увидеть (заштрихованное на чертеже) допустимое пространство решений, содержащее все комбинации *, и х2, которые не нарушают ограничения (вспомогательные условия).

Ищутся, однако, не все допустимые решения, а оптимальные решения модели. Чтобы их определить, изображают целевую функцию, причем в G подставляются различные значения. Получают так называемые линии равной прибыли, которые, по мере роста величины прибыли параллельно удаляются от начала координат. До тех пор пока эти линии проходят внутри пространства решений, соответствующие им значения прибыли могут быть реализованы. Если необходимо максимизировать прибыль, то следует реализовать линию прибыли, отстоящую максимально далеко от начала координат и касающуюся пространства решений. Комбинация переменных, максимизирующая прибыль, находится, таким образом, в общем случае во внешней угловой точке допустимого пространства решений (в примере это комбинация дг, = 4 и дг2 «= Ю с общей прибылью 190 ден. ед.).

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

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

Эти итерации алгоритма симплекс-метода можно теперь продемонстрировать при помощи предыдущего числового примера (см. рис. 94).

Базисные

переменные

X,

х2

У,

Уг

ь,

bf/a.

1. Симплекс-

У,

5

3

1

0

50

16 2/3

ная таблица

(исходная)

Уг

3

6

0

1

72

12

10

15

0

0

0

У,

7/2

0

1

-1/2

14

4

2. Симплекс-

ная таблица

*2

1/2

1

0

1/6

12

24

5/2

0

0

-15/6

-180

3. Симплекс-

1

0

2/7

-1/7

4

ная таблица

*2

0

1

-1/7

+10/42

10

0

0

-5/7

- 90/42

-190

Рис. 94.

Алгоритм симплекс-метода

(1) Формирование исходной таблицы. Прежде всего в матрицу (исходная таблица) переносятся целевая функция и ограничения. Кроме этого, ограничения за счет введения вспомогательных переменных (у, и у2) должны быть преобразованы в уравнения:


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

Последние называются базисными переменными, приравненные к нулю переменные называются небазисными переменными.

Дальнейшие действия в соответствии с симплекс-алгоритмом состоят теперь в проверке, нельзя ли увеличить прибыль в результате обмена переменных, т. е. приравнивания к нулю прежних базисных переменных (выведения их из базиса) и введения в базисное решение новых (небазисных) переменных. Расчеты в исходной таблице. Чтобы получить первые базисные решения, в исходной таблице определяются обмениваемые переменные. Для этого надо определить опорный столбец и опорную строку: Определение опорного столбца. Сначала определяется вновь вводимая в базисное решение переменная; в соответствии с простым симплекс-критерием ею является переменная с наибольшим удельным вкладом в прибыль, т. е. в примере х2 с 15 ден. ед. Определение опорной строки. Для вновь введенной переменной необходимо приравнять к нулю одну из старых базисных переменных, она будет определена в результате определения опорной строки. Так как приравнивание нулю любой из старых базисных переменных у, и у2 ведет к образованию свободных ресурсов в обоих ограничениях, то выводимая переменная определяется путем выявления того ограничения, которое при увеличениих2 исчерпывается первым.

Сравнение отношений b/а.. показывает, что таким ограничением является ограничение 2 и, таким образом, у2является переменной, выводимой из базисного решения (ограничение 1 позволяет производить 162/3, в то время как ограничение 2 — максимум 12ед. продукции*.,, причем в этом случае у2 принимает значение, равное нулю). Для определения опорной строки при положительных правых частях Ь могут использоваться только положительные коэффициенты aff gt; 0 опорных столбцов. Коэффициент в точке пересечения опорного столбца и опорной строки называется ведущим элементом (а.). С его помощью образуется следующая симплексная таблица. Образование новой (второй) симплексной таблицы. Чтобы иметь возможность получать новые базисные элементы непосредственно из таблицы, необходимо ее преобразовать таким образом, чтобы векторы-столбцы базисных переменных состояли исключительно из нулей и единиц. Тогда значения базисных переменных выводятся из уравнений таблицы непосредственно как соответствующие значения правых частей Ьг так как остальные небазисные переменные равны нулю. Итак, вектор-столбец новой базисной переменной должен со-

держать в первой строке нуль, во второй — единицу и в третьей строке (целевая функция) также нуль. С этой целью нужно преобразовывать исходную таблицу при помощи следующих шагов: деление опорной строки на ведущий элемента, (в пример а = 6). В результате в векторе-столбце, соответствующем х2, появляется единица, значение хг устанавливается равным 12. Преобразованное уравнение вносится во вторую строку новой симплексной таблицы; получение нулей в остальных уравнениях таблицы производится вычитанием умноженного на соответствующее число вновь полученного уравнения из соответствующих строк исходной таблицы. (Для первой строки таблицы примера: вычитание умноженной на 3 новой второй строки второй таблицы из первой строки исходной таблицы; для строки целевой функции: вычитание умноженной на 15 новой второй строки из строки целевой функции исходной матрицы.) Соответствующим образом преобразованные уравнения вносятся на свои места в новую симплексную таблицу.

Новое (второе) базисное решение содержит у{ со значением 14, а также х2 со значением 12. Изделие х2 производится в максимально допустимом вторым ограничением количестве (72:6 = 12), вследствие чего одновременно вспомогательная переменная у2 принимает значение, равное нулю. Объем производства^ в количестве 12 единиц вызывает одновременно нагрузку этим изделием на первое ограничение в количестве 12 х 3 = 36 единиц.

Поскольку второго ресурса имеется в распоряжении 50 единиц, то получается остаток в количестве 50 - 36 - 14 единиц. Этот остаток приходится на вспомогательную переменную уу Произведенные 12 единиц продукции х2 приносят по 15 ден. ед. за штуку, или всего 180 ден. ед. Эту величину можно непосредственно увидеть в таблице как коэффициент в строке целевой функции (с отрицательным знаком).

По коэффициентам новых небазисных переменных (xt и у2) в целевой функции можно увидеть, можно ли еще повысить значение целевой функции в результате введения какой-либо из этих переменных в базис в обмен на какую-то нынешнюю базисную переменную. Положительные коэффициенты сигнализируют об увеличении целевой функции, а отрицательные — об ее уменьшении в случае включения в базисное решение соответствующей переменной. Следовательно, в результате включения в базисное решение небазисной ныне переменной х, возможно дальнейшее повышение прибыли. Таким образом, на следующей итерации для определения нового базисного решения при помощи вычислительных процедур, изложенных выше, строится следующая (третья) симплексная таблица. Новым опорным столбцом является первый столбец второй таблицы, новой опорной строкой — первая строка, таким образом, из базиса удаляется переменная yv Новое базисное решение содержит в качестве базисных переменных xt - 4 их2 = 10 и приводит к прибыли в размере 190 ден. ед. Так как при этом третьем базисном решении в строке целевой функции не оказывается положительных' коэффициентов, найдено оптимальное решение. 

<< | >>
Источник: Ширенбек X.. Экономика предприятия: Учебник для вузов. 15-е изд. 2005

Еще по теме Линейное программирование как аналитическая технология оптимизации:

  1. Глава 52 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
  2. Область применения линейного программирования в экономическом анализе
  3. 4.7. Определение оптимального портфеля с помощью линейного программирования
  4.              Сведение матричной игры к задаче линейного программирования
  5. Линейное программирование
  6. Метод линейного программирования
  7. Приведение матричной игры к задаче линейного программирования
  8. ЛИНЕЙНЫЙ И РЫНОЧНЫЙ ПОДХОД К КОММЕРЦИАЛИЗАЦИИ ТЕХНОЛОГИЙ
  9. Критерии оптимизации информационных технологий
  10. Оперативная аналитическая обработка (OLAP-технология)
  11. § 16.7.2. Испытание гипотезы для оценки линейности связи на основе показателя наклона линейной регрессии
  12. Оптимизация технологий проведения срочных   операций
  13. КАК ПОТЕРПЕТЬ НЕУДАЧУ ПРИ ОПТИМИЗАЦИИ
  14. КАК ДОСТИЧЬ УСПЕХА ПРИ ОПТИМИЗАЦИИ
- Бюджетная система - Внешнеэкономическая деятельность - Государственное регулирование экономики - Инновационная экономика - Институциональная экономика - Институциональная экономическая теория - Информационные системы в экономике - Информационные технологии в экономике - История мировой экономики - История экономических учений - Кризисная экономика - Логистика - Макроэкономика (учебник) - Математические методы и моделирование в экономике - Международные экономические отношения - Микроэкономика - Мировая экономика - Налоги и налолгообложение - Основы коммерческой деятельности - Отраслевая экономика - Оценочная деятельность - Планирование и контроль на предприятии - Политэкономия - Региональная и национальная экономика - Российская экономика - Системы технологий - Страхование - Товароведение - Торговое дело - Философия экономики - Финансовое планирование и прогнозирование - Ценообразование - Экономика зарубежных стран - Экономика и управление народным хозяйством - Экономика машиностроения - Экономика общественного сектора - Экономика отраслевых рынков - Экономика полезных ископаемых - Экономика предприятий - Экономика природных ресурсов - Экономика природопользования - Экономика сельского хозяйства - Экономика таможенного дел - Экономика транспорта - Экономика труда - Экономика туризма - Экономическая история - Экономическая публицистика - Экономическая социология - Экономическая статистика - Экономическая теория - Экономический анализ - Эффективность производства -