Сделай Сам Свою Работу на 5

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





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

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

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

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

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

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*) (условие оптимальности).

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

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

1. Допустимое множество задачи ЛП либо пусто, либо является выпуклым многогранником в Rn (как пересечение полупространств, описываемых неравенствами (2)-(3)). Оно может быть как ограниченным, так и неограниченным; в любом случае это замкнутый многогранник.

2. Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.

3. Оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая их выпуклая комбинация также является оптимальным решением (т.е. существует бесконечное множество точек максимума или минимума).

Методами решения задач ЛП являются:

1. графический метод (в случае двух переменных),

2. симплекс-метод или его разновидности (в общем случае).

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.