<<
>>

8.4. Линейное программирование

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

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

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

Рассмотрим алгоритм симплекс-метода на основе числового примера — оптимизационной задачи, включающей пять неизвестных и три ограничивающих условия:

J = 1,2 x(1) + 1,4 x(2) ^ min; x(3) = 40 x(1) + 25x(2) + 1000; x(4) = 35x(1) + 28x(2) + 980; x(5) = 25x(1) + 35x(2) + 875. 1-

й этап решения задачи. Начальное решение задачи примем при условии равенства нулю первых двух переменных:

x(1) = 0, x(2) =0, x(3) = 1000, x(4) = 980, x(5) = 875.

Это решение задачи представим в виде симплекс-таблицы (табл. 8.3).

Таблица 8.3 x(l) x(2) b x(3) 40 25 1000 x(4) 35 28 980 x(5) 25 35 875 J 1,2 1,4 0 Эта таблица в условном виде повторяет систему условий задачи. 2-

й этап решения задачи. Находим «ключевой» столбец по условию max c(i) (в нашем примере это будет c(i*) = 1,4). 3-

й этап решения задачи. Находим «ключевую» строчку по условию min b( j)/ a(i,j) (в нашем примере это будет min b( j)/а(i, j) = 875/35). 4-

й этап решения задачи.

«Поворачиваем» таблицу вокруг «ключевого» элемента (табл. 8.4).

Правила пересчета элементов таблицы: 1.

a(i, j*) ^ 1; a(i‘, k) ^ 0.

Таблица 8.4 х(1) х(5) b х(3) 155/7 0 375 х(4) 31 0 280 х(2) 5/7 0 25 J 1/5 0 35 2. »№.,-) ^ «(1.3) л 02! - 7

a(i , ] ) а(2,3) 7

35

а(2,3) 3.

Цк)л т-а(ЛУ’(/); «1)лВД-«<24Ш>-1000--375.

a(i ,] ) a(i*, j)a(i, j*) 25 x 25 155 4.

a(i, j) ^ a(i, j) —v v J a(1,1) = 40 = .

a(i*, j*) 35 7

tu\ tu\ a( k, j*) ... ... a(1,3)c(2) 25 x1,4 1 5.

c(k) ^ c(k) v J '; c(1) ^ c(1) —v ' y ' = 1,2 — = -.

a(i*, j*) a(2,3) 35 5 5-

й этап решения задачи. Повторяем пункты 2-5 и получаем следующую таблицу (табл. 8.5).

Таблица 8.5 х(3) x(5) b х 1 0 16 29/31 х 0 0 25 30/31 х 0 1 12 28/31 J 0 0 38,3871 В этой таблице получены нулевые коэффициенты в строке оценки, поэтому соответствующее ей решение является оптимальным:

29 28 30

х(1) = 1б|у; х(2) = 12^; х(3) = 0; х(4) = 25|^; х(5) = 0.

] = 38,3871.

Зачастую к определяемым величинам в задаче линейного программирования предъявляют требование целочисленности исходя из смысла переменной. Это может быть целое число станков, вагонов, числа работающих. Решение этих задач значительно сложнее. Типовыми алгоритмами их решения являются методы Гомори и Балаша.

Двойственная задача линейного программирования Каждой задаче линейного программирования можно сопоставить другую, называемую двойственной по отношению к исходной (прямой): Прямая задача

П

max(min)i1 = ? С]Х]; ]=1

n

? aiixi ^ ’ (i =1... m);

]=1

г{ > 0 (I = 1... т).

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

X] > 0 (] = 1... n).

Двойственная задача

max(min)^2 = ? bizi;

1=1

^ m

? i >c] (] =1... m);

1=1 1. Если целевая функция прямой задачи задается на max, тогда целевая функция двойственной задачи — на min, и наоборот. 12

ли

4n *2n

21

22

2. Матрица A =

, составленная из коэффициентов в систе-

ml

m2

ме ограничений прямой задачи, и аналогичная матрица \

21

11

m1 AT =

m2

a12 a22 1п и2т ит

в двойственной задаче получаются друг из друга транспонированием. 3.

Число переменных в двойственной задаче (т) равно числу соотношений (ограничений) в прямой задаче, а число ограничений в двойственной задаче (п) — числу переменных в прямой задаче. 4.

Коэффициенты при неизвестных в целевой функции прямой задачи — это свободные члены (Ьг), а правые части в ограничениях двойственной задачи (с/) — это коэффициенты при неизвестных в целевой функции прямой задачи. 5.

Если переменная %? прямой задачи может принимать только положительные значения (X/ > 0), то/-е условие двойственной задачи — условие неравенства вида «>». Если г-е соотношение в прямой задаче — неравенство, то г-я переменная двойственной задачи г г > 0.

Если ПЗ имеет решение, то и ДЗ тоже имеет решение, причем шах^т)^ = = шт(шах)Х2. Поэтому достаточно для отыскания оптимума решить какую-либо одну из задач двойственной пары; обычно решают ту, которая проще.

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

Пример. Для производства изделий А, В, С используются три различных вида ресурсов. Каждый из видов ресурсов может быть использован в количестве соответственно не большем 180, 210, 244 ед. Известны затраты каждого из видов ресурсов на единицу продукции и цена единицы продукции каждого вида (табл. 8.6).

Таблица 8.6

Оценка дефицитности вида продукции Вид ресурса Норма расхода ресурса, ед. изм./ ед. продукции А В С 1 4 2 1 2 3 1 3 3 1 2 5 Цена продукции 10 14 12 Требуется определить план производства, при котором обеспечивается максимальный доход, и оценить дефицитность каждого из видов ресурсов, используемых для производства продукции.

Решение. Обозначим через х1 искомый план производства изделий А, через х2 —

В, х3 — С, а через z1 — двойственную оценку дефицитности первого вида ресурса, через г2 — второго, 23 — третьего. Тогда прямая и двойственная задачи формулируются следующим образом: Прямая задача

max L = 10.x1 + 14x2 + 12x3;

Двойственная задача min L2 = 180z1 + 210z2 + 244z3; 4x1 + 2x2 + x3 < 180;

3xj + X2 + ЗХ3 < 210;

x1 + 2x2 + 5x3 < 180; x1, x2, x3 > 0.

4z1 + 3z2 + z3 > 10 2zt + z2 + 2z3 > 14 z1 + 3z2 + 5z3 > 12 z, z0, z4 > 0.

123

Решение прямой задачи дает оптимальный план производства изделий А, В, С, а решение двойственной задачи — оптимальную систему оценок ресурсов, используемых для производства этих изделий:

xj3 = 0; x° = 82; x° = 0; max L = 1340; 2° = 5,75; = 0; = 1,25; min L = 1340.

Исходя из анализа оптимальных двойственных оценок можно сделать следующие выводы.

Ресурсы первого и третьего вида используются полностью.

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

Более того, величина двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества соответствующего ресурса на 1 ед. Так, увеличение количества ресурса первого вида на 1 ед. приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общий доход возрастет на 5,75 ден. ед. и станет равным 1340 + 5,75 = 1345,75 ден. ед. Анализ полученных оптимальных значений новой прямой задачи показывает, что это увеличение общего дохода достигается за счет увеличения производства изделий В на 0,625 ед. и сокращения выпуска изделий С на 0,25 ед. Вследствие этого использование ресурса второго вида уменьшается на 0,125 ед.

Точно так же увеличение на 1 ед. количества ресурсов третьего вида позволит перейти к новому оптимальному плану производства, при котором доход возрастет на 1,25 ден. ед. и составит 1340 +1,25 = 1341,25 ден. ед., что достигается за счет увеличения выпуска изделий С на 0,25 ед. и уменьшения выпуска В на 0,25 ед., причем объем используемого ресурса второго вида возрастает на 0,625 ед.

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

4 х 5,75 + 1,25 > 10;

2 х 5,75 + 1,25 = 14;

5,75 + 5 х 1,25 = 12.

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

При одновременном изменении ресурсов всех видов на величину ЛЬг(г = 1... т) можно оценить их суммарное влияние на значение целевой функции (при условии неизменности двойственных оценок в новой двойственной задаче относительно оценок в первоначальной двойственной задаче):

т

Д^ = ? ДЬ,-г°,

г=1

где ЛЬг — величина возможного (при сохранении оптимального плана первоначальной двойственной задачи) изменения (увеличения или уменьшения) ресурса г-го вида.

<< | >>
Источник: Глухов В. В.. Менеджмент: Учебник для вузов. 3-е изд. — СПб.: Питер. — 608 с.. 2008

Еще по теме 8.4. Линейное программирование:

  1. Линейное программирование
  2. 8.10. Дробно-линейное программирование
  3. 5.7.2. Сведение матричной игры к задаче ч: линейного программирования
  4. 8.5. Целочисленное программирование
  5. 4.2. Основы социального программирования
  6. 8.16. Эвристическое программирование
  7. 8.14. Стохастическое программирование
  8. Экономическое программирование
  9. Вопрос 29 КТО ТАКИЕ ЛИНЕЙНЫЕ И ФУНКЦИОНАЛЬНЫЕ МЕНЕДЖЕРЫ?
  10. Вопрос 74 ЧТО ТАКОЕ ЛИНЕЙНАЯ СТРУКТУРА УПРАВЛЕНИЯ?
  11. 8.13. Динамическое программирование
  12. Вопрос 86 ЧТО ТАКОЕ ЛИНЕЙНЫЕ ПОЛНОМОЧИЯ?