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

Примеры задач ЛП

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

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

Математическая модель любой задачи линейного программирования включает в себя:

1) максимум или минимум целевой функции (критерий оптимальности);

2) систему ограничений в форме линейных уравнений и неравенств;

3) требование неотрицательности переменных.

Рассмотрим алгоритм составления математической модели задачи на примере.

Пример 1. Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м² досок, а для модели В - 4 м². Фирма может получать от своих поставщиков до 1700 м² досок в неделю. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели В - 30 мин. В неделю можно использовать 160 часов машинного времени.

Сколько изделий каждой модели следует выпускать фирме в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В - 4 дол. прибыли?

Сведем все данные в табл.

Таблица 3.1

Ресурс	Модели книжных полок	Запас ресурсов
А	Б
Доски, м2
Машинное время, мин
Цена

Построение математической модели.

Пусть х₁ - количество выпущенных за неделю полок модели А,

х₂ - количество выпущенных полок модели В.

Тогда: 3x₁ - количество досок требуемых на неделю для изготовления полок модели А,

4х₂- количество досок требуемых на неделю для изготовления полок модели В.

3x₁ + 4х₂ - количество досок требуемых на неделю для изготовления книжных полок двух моделей, а по условию задачи это число не должно превышать 1700 м². Следовательно, получаем первое ограничение:

3x₁ + 4х₂ ≤ 1700 (1)

Найдем ограничение на использование машинного времени:

12 мин. составляют 0,2 часа, а 30 мин. - 0,5 часа.

Таким образом: 0,2x₁ - количество времени, требуемое на неделю для обработки полок модели А;

0,5х₂ - количество времени, требуемое на неделю для обработки полок модели В;

0,2x₁ + 0,5х₂ - количество времени, требуемое на неделю для обработки двух моделей, а по условию задачи это число не должно превышать 160 часов. Следовательно, получаем второе ограничение:

0,2x₁ + 0,5х₂ ≤ 160 или 2x₁ + 5х₂ ≤ 1600 (2)

Кроме того, поскольку x1 и х2 выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательными, то есть

x₁ ≥ 0, х₂ ≥0 (3)

Наша задача состоит в том, чтобы найти такие значения x₁ и х₂, при которых еженедельная прибыль будет максимальной.

Составим выражение для еженедельной прибыли:

2x₁ - еженедельная прибыль, получаемая от продажи полок модели А.

4х₂ - еженедельная прибыль, получаемая от продажи полок модели В.

F=2x₁ + 4х₂ - еженедельная прибыль, которая должна быть максимальной.

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

F=2x₁ + 4х₂ → max

Полученная модель является задачей линейного программирования. Функция F это целевая функция, она является линейной функцией своих переменных (x₁, х₂). Ограничения на эти переменные (1) и (2) тоже являются линейными. Выполнено условие неотрицательности для переменных x₁ и х₂.

Необходимо найти значения переменных x₁ и х₂, при которых данная функция F принимает максимальное значение, при соблюдении ограничений, накладываемых на эти переменные.

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

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

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

(l)-(3) - это стандартная постановка задачи ЛП (в общем случае в ограничениях (2) могут быть различные соотношения вида «≤», «≥», «=»).

с₁,…, c_n - коэффициенты при целевой функции,

а₁₁, …, а_kn - коэффициенты при ограничениях,

b₁, …, b_k - свободные члены при ограничениях.

Все они являются известными числами (заданы).

Неизвестными являются переменные х₁, …, х_n.

В задачах (1) - (3) требуется найти такие значения переменных (точку максимума), чтобы:

1. эти переменные удовлетворяли всем ограничениям (2) и (3) (условие допустимости);

2. В точке х* = () целевая функция f принимала максимальное значение f(x*) (условие оптимальности).

Аналогично ставится задача на минимум.