Линейное программирование | Статья в журнале «Молодой ученый»

Автор:

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

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

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

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

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

Кульневич А. Д. Линейное программирование // Молодой ученый. — 2017. — №10. — С. 29-32. — URL https://moluch.ru/archive/144/40399/ (дата обращения: 16.12.2018).



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

Ключевые слова: линейное программирование, математическая оптимизация, 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.
Основные термины (генерируются автоматически): линейное программирование, BASIS, симплекс метод, ограничение, число итераций, SEAC, высокое качество, вычислительная эффективность, SCOOP, решение задач.


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

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

Похожие статьи

Решение многокритериальных задач линейного...

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

%Настройка функции linprog на решение симплекс-методом.

Целочисленное решение задач линейного программирования...

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

Решение интервальной задачи дробно-линейного...

Решив задачу симплекс-методом, получим следующие значения переменных , , . Сделав возврат к исходным переменным, получим следующее

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

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

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

Применение метода линейного программирования для...

Метод линейного программирования при решении текстовых задач графически имеет следующий алгоритм

Математика. Решение задач и уравнений в целых числах. – М., Издательство «Экзамен», 2015, 126 с.

Приложения линейного программирования к решению...

Как и выше задача свелась к задаче линейного программирования. Решение указанных задач может производиться известными методами; наиболее распространенным является симплекс-метод (существуют стандартные программы).

Некоторые прикладные задачи целочисленного...

Существует ряд методов решения задачи целочисленного программирования.

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

Решение задач оптимального раскроя средствами MS Excel

Симплекс-метод, основанный на идеях Л. В. Канторовича, был описан и детально разработан рядом ученых из США в середине 20 века.

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel.

Интерактивный подход к решению задач линейного...

В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс-методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и...

Обсуждение

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

Похожие статьи

Решение многокритериальных задач линейного...

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

%Настройка функции linprog на решение симплекс-методом.

Целочисленное решение задач линейного программирования...

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

Решение интервальной задачи дробно-линейного...

Решив задачу симплекс-методом, получим следующие значения переменных , , . Сделав возврат к исходным переменным, получим следующее

Решение многокритериальных задач линейного программирования (ЗЛП) методом последовательных уступок в MatLab.

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

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

Применение метода линейного программирования для...

Метод линейного программирования при решении текстовых задач графически имеет следующий алгоритм

Математика. Решение задач и уравнений в целых числах. – М., Издательство «Экзамен», 2015, 126 с.

Приложения линейного программирования к решению...

Как и выше задача свелась к задаче линейного программирования. Решение указанных задач может производиться известными методами; наиболее распространенным является симплекс-метод (существуют стандартные программы).

Некоторые прикладные задачи целочисленного...

Существует ряд методов решения задачи целочисленного программирования.

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

Решение задач оптимального раскроя средствами MS Excel

Симплекс-метод, основанный на идеях Л. В. Канторовича, был описан и детально разработан рядом ученых из США в середине 20 века.

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel.

Интерактивный подход к решению задач линейного...

В процессе решения задач линейного программирования (далее — ЗЛП) часто возникает ситуация, когда пользователь не может решить задачу обычным симплекс-методом (то есть в системе ограничений присутствует не только условие вида « », но и условия видов « » и...

Задать вопрос