double arrow

Основы линейного программирования


Универсальный метод линейного программирования – симплексный метод.

Значительный вклад в развитие линейного программирования внес наш соотечественник математик Л.В. Канторович. В 1939 г. он в монографии «Математические методы организации и планирования производства» впервые предложил метод решения задач линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан широко используемый в настоящее время универсальный метод линейного программирования – симплексный метод.

Модель задач линейного программирования должна иметь вполне определенный вид: требуется найти максимум (минимум) значения целевой функции L при переменных x1, x2 …,xn

L(X) = c1x1 + c2x2 + …+ cnxn → max (min) (10)

при соблюдении линейных ограничений

a11x1 + a12x2 + …+ a1nxn = b1

a21x1 + a22x2 + …+ a2nxn = b2

…………………………….. (11)

am1x1 + am2x2 + …+ amnxn = bm

Каждая из переменных не может принимать отрицательного значения, т.е. x1 ≥ 0; x2 ≥ 0; … xn ≥ 0 (12)

В выражениях (10) и (11) коэффициенты аij и cj при переменных и величины bi – постоянные числа

(i = 1,2,…,m; j = 1,2,…,n).

Решение системы уравнений (11) при выполнении условия (12) называется допустимым решением задачи линейного программирования.




Оптимальное решение – это допустимое решение, удовлетворяющее условию (10). Для нахождения оптимального решения следует иметь множество допустимых решений. Если число уравнений m в системе (11) равно числу переменных n, то такая система уравнений имеет только одно решение. В задачах линейного программирования число уравнений должно быть меньше числа переменных: m < n.

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

ai1x1 + ai2x2 + …+ ainxn ≤ bi (13)

или

ak1x1 + ak2x2 + …+ aknxn ≥ bk (14)

Тогда введением дополнительных переменных, больших нуля, неравенства (13) и (14) превращают в уравнения:

ai1x1 + ai2x2 + …+ ainxn + xn+i = bi ; (15)

ak1x1 + ak2x2 + …+ aknxn + xn+k = bk . (16)

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

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

Ограничения по использованию ресурсов будут представлены системой неравенства вида (13). Планирование использования каждого вида ресурсов не должно превышать возможности предприятия. Дополнительная переменная в этом случае



xn+i = bi – (ai1x1 + ai2x2+ …+ ainxn)

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

Предположим также, что некоторые виды продукции пользуются повышенным спросом и их следует производить не менее определенного уровня bk. Следовательно, планируемый выпуск этих изделий должен быть больше либо равен bk. Дополнительная переменная здесь xn+к характеризует количество планируемых к выпуску изделий сверх минимального уровня:

xn+к = (аk1 x1 + аk2 x2 + … + аkn xn) – bk.

Объем изготовляемой продукции каждого вида характери­зуется значениями переменных x1, x2,, . . ., xn. Прибыль зависит от величины этих переменных. Дополнительная же переменная xn+k определяет не объем производства изделий, а показывает, на сколько планируемый объем превышает минимально возмож­ный выпуск. За этот дополнительный выпуск прибыль уже учтена в целевой функции. Чтобы повторного счета не было, переменная xn+k тоже должна включаться в целевую функцию с нулевым коэффициентом.

Свободные члены b1, b2, ..., bmв системе ограничений должны быть положительными или равными нулю.

Очень часто используют сокращенную запись задачи линей­ного программирования. Целевая функция имеет вид

n

L(X) = Σcjxj max(min) (17)

j =1

а система ограничений —

n

Σai jxj = bi, i = l, 2,. . . , m. (18)



j =1

xj = 1, 2, ..., n.

Все приведенные выше записи задач линейного программи­рования даны в канонической форме.

Рассмотрим построение модели линейного програм­мирования на конкретном примере – оптимизация плана производства предприятия..

Предприятие может производить продукцию двух видов. Требуется определить план выпуска продукции каждого вида, обеспечивающий максимально возможную прибыль, если в трех цехах А, Б и В установлено соответственно 24, 15 и 8 единиц оборудования, а нормы использования оборудования для про­изводства за 1 час единицы продукции представлены в табл.3.

Таблица 3

    Цех   Нормы использования оборудования для производства за 1 час единицы продукции  
Первого вида   Второго вида    
А Б В -

В цехе В, как видим, продукция первого вида не произво­дится.

Прибыль, получаемая предприятием при реализации еди­ницы продукции первого вида, равна 1 руб., а при реализации единицы продукции второго вида 2 руб.

В качестве переменных примем:

x1объем производства за 1 час продукции первого вида;

x2объем производства за 1 час продукции второго вида.

Целевая функция опреде­ляет величину получаемой прибыли (размер прибыли за­висит от объема вырабатывае­мой продукции):

L(X) = x1 + 2x2 max. (19)

Объем же вырабатываемой продукции зависит от количе­ства использованного оборудо­вания. По первому цеху, на­пример, 2x1планируемое ис­пользование оборудования для производства продукции пер­вого вида; Зх2 планируемое использование оборудования для производства продукции второго вида и 2x1 + 2 планируе­мое использование оборудования для производства всей продук­ции. Поскольку планируемое количество используемого обору­дования по технологическим переходам не должно превышать его наличия, ограничивающее условие по использованию обору­дования первого цеха можно записать так:

2x1 + 3x2 ≤ 24. (20)

Аналогично по второму цеху имеем

x1 + Зx2 ≤ 15 (21)

и по третьему цеху

2 ≤ 8. (22)

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

x1 ≥ 0; x2 ≥ 0. (31)

Таким образом, требуется найти значения переменных, кото­рые удовлетворяют следующей системе неравенств:

2x1 + 3x2 ≤ 24 (32)

x1 + Зx2 ≤ 15

2 ≤ 8

при x1 ≥ 0; x2 ≥ 0и целевой функции, достигающей наибольшего значения.

L(X) = x1 + 2x2 max. (23)

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

L(X) =x1+ 2x2 + 0x3 + 0x4 + 0x5àmax (24)

2x1+ 3x2 + x3 = 24

x1 + 3x2 + x4=15 (25)

2x2 +x5 = 8

x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0. (26)

Задача решается симплексным методом линейного программирования.

Оптимальное решение рассмотренной задачи:

x1= 9; x2 = 2; x3 = 0; x4 = 0; x5 = 4.

Оптимальный план рекомендует производить за час 9 изделий первого вида, 2 изделия второго вида, отказаться от изготовления третьего продукта. Этот вариант плана гарантирует получение максимальной прибыли. Значение критерия оптимизации равно 13.

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

Полученное решение допустимо, так как удовлетворяет системе ограничений (25):

2×9 + 3×2 + 0 = 24

1×9 + 3×2 + 0 = 15

2×2 + 4 = 8

Проверим также значение целевой функции:

L(X) = 1×9 + 2×2 + 0×0 + 0×0 + 0×4 = 13.

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

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

Ø Решается ли задача на нахождение максимума целевой функции или минимума?

Ø Сколько переменных в задаче?

Ø Сколько ограничений в задаче?

И выполнить по запросу компьютера операции типа:

Ø Укажите последовательно коэффициенты при переменных в целевой функции с их знаками;

Ø Укажите коэффициенты при переменных в системе ограничений в той последовательности и с теми знаками, с какими они входят в уравнения;

Ø Укажите значения свободных членов ограничений.

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

Сколько людей - столько мнений

Цицерон







Сейчас читают про: