Главная / Системный анализ / Линейное программирование

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

Линейное программирование – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т. е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «liner programming». Одно из значений слова «programming»-составление планов, планирование. Следовательно, правильным переводом «liner programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т. д. в нашей литературе стали общепринятыми, и поэтому будут сохранены.

Итак, линейное программирование возникло после Второй Мировой Войны, и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической стройности.

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

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

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

Найти вектор , значений переменных, доставляющих экстремум линейной целевой функции , при m ограничениях в виде линейных равенств или неравенств

Если в задачах необходимо найти вектор X значений переменных, при которых целевая функция F(x) должна достичь максимального значения, то задача линейного программирования решается в такой же постановке (т. е. ищется минимум), но знаки всех коэффициентов C1, C2,…,Cn изменяются на противоположные.

Точно так же неравенства вида ³, могут быть преобразованы к виду £, т. е. к тому виду, в котором поставлена задача нелинейного программирования, умножением обеих частей неравенств на -1.

Вектор X, при котором целевая функция задачи принимает свое экстремальное значение, называется оптимальным планом.

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

Пример.

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

Тип оборудования

Затраты времени (станко-часов) на обработку одного изделия вида

Общий фонд рабочего времени оборудования

A

B

C

(часы)

Фрезерное

2

4

5

120

Токарное

1

8

6

280

Сварочное

7

4

5

240

Шлифовальное

4

6

7

360

Прибыль (руб.) от реализации одного изделия

10

14

12

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

Составить математическую модель задачи.

Решение.

Предположим, что будет изготовлено x1 единиц изделий вида А, x2 единиц изделий вида В и x3 единиц изделий вида С.

Для производства такого количества изделий потребуется затратить 2×1+4×2+5×3 станко-часов фрезерного оборудования. Так как общий фонд рабочего времени фрезерных станков не может превышать 120, то должно выполняться неравенство: 2×1+4×2+5×3£120.

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

x1+8×2+6×3£280

7×1+4×2+5×3£240

4×1+6×2+7×3£360.

При этом, так как количество изготавливаемых изделий не может быть отрицательным, то:

x1³0,

x2³0,

x3³0.

Тогда прибыль от реализации составит F=10×1+14×2+12×3 ® max, которая по условию задачи должна быть максимальной.

Таким образом, математическая модель поставленной задачи будет иметь вид:

Найти оптимальный план , доставляющий максимум целевой функции F=10×1+14×2+12×3 при ограничениях в виде линейных равенств или неравенств:

, .

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