double arrow

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

2

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

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

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

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

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

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

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

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

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

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

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

Таблица 3.1

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

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

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

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

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

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

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

3x1 + 4х2 ≤ 1700 (1)

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

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

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

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

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

0,2x1 + 0,5х2 ≤ 160 или 2x1 + 5х2 ≤ 1600 (2)

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

x1 ≥ 0, х2 ≥0 (3)

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

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

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

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

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

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

F=2x1 + 4х2 → max

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2

Сейчас читают про: