Автор: Кульневич Алексей Дмитриевич

Рубрика: Информатика

Опубликовано в Молодой учёный №10 (144) март 2017 г.

Дата публикации: 10.03.2017

Статья просмотрена: 21 раз

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

Кульневич А. Д. Линейное программирование // Молодой ученый. — 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.
Основные термины (генерируются автоматически): линейного программирования, симплекс метод, задача линейного программирования, задач линейного программирования, линейное программирование, Линейное программирование, Модель линейного программирования, Симплекс метод, задачи линейного программирования, название линейного программирования, ограничения линейного вида, области линейного программирования, формулировке задач линейного, решении задач линейного, общая задача линейного, решения задач, переменных решений, числа итераций равна, число итераций 2M, решения задач оптимизации.

Ключевые слова

линейное программирование, математическая оптимизация, pivot-переменная, симплекс метод, Слабые переменные

Обсуждение

Социальные комментарии Cackle
Задать вопрос