Знакомство с линейным программированием

ЗНАКОМСТВО С ЛИНЕЙНЫМ ПРОГРАММИРОВАНИЕМ

Базовый алгоритм линейного программирования был разработан Джорджем Данцигом в Калифорнийском университете в Беркли в начале 1940-х годов. Данциг использовал эту концепцию для экспериментов с логистическим пла­ нированием материально-технического снабжения войск во время работы в ВВС США. В конце Второй мировой войны Данциг начал работать на Пентагон и превратил свой алгоритм в метод линейного программирования. Он исполь­ зовался для планирования боевых действий.

Сегодня линейное программирование применяется в решении важных практи­ ческих задач, связанных с минимизацией или максимизацией переменной на основе определенных ограничений. Вот некоторые примеры таких задач:

zz минимизация времени на ремонт автомобиля в автосервисе на основе име­ ющихся ресурсов;

zz распределение доступных ресурсов в вычислительной среде для минимиза­ ции времени отклика;

zz максимизация прибыли компании на основе оптимального распределения ресурсов внутри компании.

Формулировка задачи линейного

программирования

Условия для применения линейного программирования следующие:

zz Задачу можно сформулировать с помощью набора уравнений.

zz Переменные, используемые в уравнении, должны быть линейными.

Целевая функция

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