Графическое решение задач линейного программирования

Размещено на http://www.allbest.ru/

Лабораторная работа

Графическое решение задач линейного программирования

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

Нередко на практике возникают задачи оптимизации какого-либо процесса по выбранному критерию. В данной работе рассматривается задача построения математической модели и её оптимизация графическим методом линейного программирования.

Постановка задачи.

Размещено на http://www.allbest.ru/

Рис.1

Небольшое предприятие (рис.1) выпускает два вида изделий Е и I. Продукция обоих видов поступает в продажу. Для производства требуется два исходных продукта - А и В. Максимально возможные суточные запасы этих продуктов на складе предприятия составляют b1 и b2 соответственно.

Расходы продуктов А и В на единицу соответствующего изделия приведены в табл.1.

Т а б л и ц а 1

Цена одной единицы изделия Е равна Сe и Сi для I.

Изучение рынка сбыта показало, что суточный спрос на изделие I никогда не превышает спроса на изделие Е более чем на b3. Кроме того, установлено, что спрос на изделие I никогда не превышает b4.

Каков должен быть объем производства каждого вида изделия в сутки, чтобы доход от реализации был максимальным?

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

Процесс построения математической модели для решения поставленной задачи можно начать с ответов на три следующих вопроса:

Для определения каких величин должна быть построена модель? Другими словами, как идентифицировать переменные (искомые величины) данной задачи.

Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия и ограничения, характерные для данной задачи?

В чем состоит цель решения задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?

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

Переменные.

Хe - суточный объем производства изделия Е.

Xi - суточный объем производства изделия I.

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

D = De+Dj = CeXe + Сi Хi

-доход. от производства и сбыта изделия Е и I.

Необходимо определить такие значения Xe и Хi , при которых совокупный доход D достигает максимума.

Ограничения.

При решении рассматриваемой задачи должны быть учтены ограничения на расход исходных продуктов A и B и ограничения по спросу на изготовляемые изделия E и I.

Ограничения на расход исходных материалов запишем следующим образом:

Принимая во внимание обозначения, принятые в табл.1 запишем ограничения на суточные расходы исходных продуктов:

Изложенные выше ограничения на спрос запишутся в виде:

Кроме того, переменные Xe и Хi по своему смыслу не могут быть отрицательными:

Итак, выпишем математическую модель поставленной задачи.

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

Ограничения:

Требуется максимизировать значение целевой функции D (т.е. доход).

Математическая модель поставленной задачи относится к задаче линейного программирования. Для ее решения в общем случае используется симплекс-метод. В случае двух переменных удобно использовать простой и наглядный графический метод решения.

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

Для нахождения оптимального решения, необходимо выяснить в каком направлении возрастает целевая функция

D = CeXe + Сi Хi.

С этой целью, в ОДР наносят ряд параллельных линий равного уровня значений целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях D. Это позволяет определить наклон целевой функции и направление, в котором происходит её увеличение. Чтобы найти оптимальное решение, следует перемещать прямую равного дохода, в направлении возрастания целевой функции до тех пор, пока она не сместится в область недопустимых значений переменных. Точка перехода из ОДР в область недопустимых значений соответствует оптимальному решению.

Исходные данные

1.Запишем математическую модель:

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

D=2,5 Хi +4,5 Xe

Ограничения:

1,2Xe+ 1,9Xi? 6 (-)1

2Xe+ 0,9Xi? 8,2 (-)2

Xe+ Xi?1 (-)3

Xi? 1,8 (-)4

Xi? 0 (-)5

Xе? 0 (-)6

2. Построим в соответствии с ограничениями (1) - (6) область допустимых решений (многоугольник АБВГДЕ) в пространстве параметров Xe, Хi

1.при Xi=0, Xе =5 при Xе=0, Xi=3,15

2.при Xi=0, Xе =4,1 при Xе=0, Xi=9,11

3.при Xi=0, Xе = 1 при Xе=0, Xi= 1

Xi=1,8

Xi=0

Xе =0

В результате мы получили многогранник с вершинами в точках (узлах) A,B,C,D,E, F. Область допустимых решений, соответствующая ограничениям (1) - (6) лежит внутри этого многоугольника. Координаты узлов и значения целевой функции во всех узлах многоугольника представлены в следующей таблице:

Приравняем целевую функцию постоянной величине а:

4,5Xe+2,5Xi = а.

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

Для определения направления движения к оптимуму построим вектор-градиент G, т.е. вектор, перпендикулярный к линии градиента и направленный в сторону роста целевой функции D.

Решение исходной ЗЛП: max D = 18,45 и достигается при Xe=4,1; Xi=0.

Вывод

математический максимизация доход линейный программирование

Прибыль можно максимизировать если увеличить суточный объем производства изделия I Дальнейшее увеличение прибыли возможно, если увеличить мах запас изделия и с помощью рекламы или других организационных мер увеличить спрос на продукцию, при этом не стоит забывать о необходимости увеличения суточного объема производства изделия I. Максимальная прибыль находится в точке 18,45.

Размещено на Allbest.ru