Библиографическое описание:

Кульневич А. Д. Линейное программирование // Молодой ученый. — 2017. — №10. — С. 29-32.



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

Ключевые слова: линейное программирование, математическая оптимизация, pivot-переменная, симплекс метод, slack variables

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

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

Objective: minimize cTx

Constraints: Ax = b (ограничения линейного вида) / l ≤ x ≤ u (ограничения на заданном интервале).

В результате описания в данной форме, вектор х представляет собой вектор переменных решений, с — линейная целевая функция, матричное уравнение Ах = b указывает линейные ограничения в х, векторы l и u — нижнюю и верхнюю границы в х.

Пример нахождения минимального и максимального значения:

Допустим вам необходимо купить шкафы для хранения документов. Известно, что 10 единиц стоит шкаф Х, который хранит 8 м2 файлов и требует пространства 6 м2. С другой стороны, известно, что 20 единиц стоит шкаф У, который хранит 12 м2 и требует 8 м2. Имеется 140 единиц денег, а также помещение размером 72 м2.

Подставляем значения в решение:

Количество хранимого:

Пространство:

Стоимость:

C:\Users\AlexeyDmitrievich\AppData\Local\Microsoft\Windows\INetCache\Content.Word\g2.jpg

Рис. 1. Графическое представление задачи

Из графика видно, что решение соответствует точкам (8, 3).

Первый алгоритм для решения задач линейного программирования был создан американским математиком Джорджом Данцигом в 1947 году.

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

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

История линейного программирования

В работе Л. В. Канторовича «Математические методы организации и планирования производства» (1939) были впервые изложены принципы новой отрасли математики, которая позднее получила название линейного программирования.

Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджом Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием «Project SCOOP». Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе 1952 года [2].

Эффективность

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

Наблюдения и анализ эффективности метода в практических приложениях привело к развитию других способов измерения эффективности.

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

Вычислительная эффективность оценивается обычно при помощи двух параметров:

  1. Числа итераций, необходимого для получения решения;
  2. Затрат машинного времени.

В результате численных экспериментов получены результаты:

  1. Число итераций при решении задач линейного программирования в стандартной форме с M ограничениями и N переменными заключено между M и 3M. Среднее число итераций 2M. Верхняя граница числа итераций равна 2M+N.
  2. Требуемое машинное время пропорционально M3.

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

Покажем суть метода на примере:

Владельцу предприятия, производящего трейлеры, необходимо определить лучший набор 3 продуктов: трейлер с прицепом, экономичный трейлер или трейлер высокого качества. Предприятие ограничено работой 24 днями на металлообработке и 60 днями на деревообработке для разработки трейлеров. Следующая таблица наглядно представит задачу:

С прицепом

Экономичный

Высокого качества

Ограничения (дней)

Металлообработка

0.5

2

1

24

Деревообработка

1

2

4

60

Выручка за единицу

6

14

13

Обозначим трейлеры за х1, х2, х3.

Необходимо:

Согласно ограничениям:

0.5x1+2x2+x3 ≤24

x1+2x2+4x3 ≤60

Неравенства «≥» и «≤» необходимо привести к равенствам с помощью добавления переменных, в английской литературе называемых slack variables.

0.5x1+2x2+x3+x4=24

x1+2x2+4x3+x5=60

Далее необходимо выбрать pivot переменную:

BASIS

X1

X2

X3

X4

X5

Ограничения

Отношение

Pivot

X4

0.5

2

1

1

0

24

12

*

X5

1

2

4

0

1

60

30

-z

-6

-14

-13

0

0

0

Pivot

*

Выбранный алгоритмом элемент выделен жирным. Далее необходимо “занулить” столбец с pivot переменной, а также привести её к 1. В столбце basis Х4 заменяется на Х2, так как pivot в столбце Х2 и строке Х4.

Результат:

BASIS

X1

X2

X3

X4

X5

Ограничения

Отношение

Pivot

X2

0.25

1

0.5

0.5

0

12

24

X5

0.5

0

3

-1

1

36

12

*

-z

-2.5

0

-6

7

0

168

Pivot

*

Операция повторяется:

BASIS

X1

X2

X3

X4

X5

Ограничения

Отношение

Pivot

X2

1/6

1

0

2/3

-1/6

6

36

*

X3

1/6

0

1

-1/3

1/3

12

72

-z

-1.5

0

0

5

2

240

Pivot

*

Операция повторяется:

BASIS

X1

X2

X3

X4

X5

Ограничения

Отношение

X1

1

6

0

4

-1

36

36

X3

0

-1

1

-1

0.5

6

6

-z

0

9

0

11

0.5

294

Таким образом, решение минимума z = -294. Максимум равен 294. Оптимальное решение х = (36, 0, 6, 0, 0).

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

Литература:

  1. Singiresu S. Rao Engineering optimization: theory and practice. — New York: Wiley, 2009. — 813 p.
  2. Гасс С. Линейное программирование. — М.: Государственное издательство физико-математической литературы, 2015. — 304 c.

Обсуждение

Социальные комментарии Cackle