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

⇐ ПредыдущаяСтр 5 из 24Следующая ⇒

Компания R&M производит краску для внутренних и наружных работ из сырья 2-х типов: М1 и М2. Расход сырья для производства 1 т краски указан в таблице 2.1.

Таблица 2.1 – Исходные данные

	Расход сырья (в т) на 1 т краски		Максимальный ежедневный расход сырья, т
	для наружных работ	для внутренних работ	Максимальный ежедневный расход сырья, т
Сырьё М1	6	4	24
Сырьё М2	1	2	6
Доход (тыс. руб.) на 1 т краски	5	4

Отдел маркетинга компании ограничил ежедневное производство краски для внутренних работ до 2 т (из-за отсутствия надлежащего спроса), а также поставил условие, чтобы ежедневное производство краски для внутренних работ не менее чем на 1 т превышало ежедневный объём производства краски для наружных работ. Требуется определить наилучшее соотношение между видами выпускаемой продукции для получения максимального ежедневного дохода.

Решение. Прежде чем построить математическую модель задачи, необходимо ответить на следующие вопросы:

- что является искомыми величинами?

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

- какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Эти условия устанавливают, как должны соотноситься друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве, и его запас на складе; количество выпускаемой продукции и ёмкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос на эту продукцию, и т. д.

Первый этап разработки модели – определение переменных. В данном примере необходимо определить ежедневные объёмы производства краски для внутренних и наружных работ. Обозначим эти объёмы как переменные:

х₁– объём производства краски для наружных работ, т/сутки;

х₂ – объём производства краски для внутренних работ, т/сутки.

В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции. Т. е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи краски обоих видов, необходимо знать объёмы производства красок, т. е. х₁и х₂ тонн краски в сутки, а также цену 1 тонны краски каждого вида – согласно условию, это 5 и 4 тыс. руб. за тонну соответственно. Таким образом, доход от продажи краски для наружных работ в сутки составит 5х₁ тыс. руб., а доход от продажи краски для внутренних работ – 4х₂ тыс. руб. Поэтому запишем целевую функцию, обозначив её как z (она измеряется в тысячах рублей), в виде суммы дохода от продажи красок обоих видов

z = 5х₁ + 4х₂ → max.

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

Ограничения на сырьё можно записать следующим образом:

объём сырья для производства краски

≤

максимальный суточный расход сырья

Из таблицы с исходными данными имеем следующее:

- используемый объём сырья М1: С₁ = 6х₁ + 4х₂ (т);

- используемый объём сырья М2: С₂ = 1х₁ + 2х₂ (т).

Поскольку ежедневный расход сырья ограничен, получаем:

- сырьё М1: 6х₁ + 4х₂ ≤ 24;

- сырьё М2: 1х₁ + 2х₂ ≤ 6.

Существует ещё два ограничения по спросу на готовую продукцию. Первое ограничение показывает, что ежедневный объём производства краски для внутренних работ х₂ не должен превышать ежедневный объём производства краски для наружных работ х₁ больше чем на тонну, то есть х₂ – х₁ ≤ 1. Второе ограничение: максимальный ежедневный объём производства краски для внутренних работ не должен превышать двух тонн, то есть х₂ ≤ 2.

Ещё одно неявное ограничение состоит в том, что объёмы производства краски не могут быть отрицательными, т. е. х₁ ≥ 0, х₂ ≥ 0.

Окончательно задача записывается в виде:

максимизировать целевую функцию

z = 5х₁ + 4х₂ → max,

при выполнении ограничений

6х₁ + 4х₂ ≤ 24,

1х₁ + 2х₂ ≤ 6,

х₂ – х₁ ≤ 1,

х₂ ≤ 2,

х₁ ≥ 0,

х₂ ≥ 0.

Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение х₁ = 3, х₂ = 1 является допустимым, так как не нарушает ни одного ограничения. В целом, задача имеет бесконечное множество допустимых решений, поэтому искать оптимальное путём простого перебора всех решений нецелесообразно.

Для поиска оптимального допустимого решения, то есть такого сочетания х₁ и х₂, при котором значение целевой функции (доходов) будет максимальным, воспользуемся графо-аналитическим методом. Данный метод включает два основных этапа:

1) построение области допустимых решений, удовлетворяющих всем ограничениям модели;

2) поиск оптимального решения среди всех точек пространства допустимых решений.

Выполним построение области допустимых решений на координатной плоскости x₁Ox₂ (рис. 2.2). Условие неотрицательности переменных х₁ и х₂ говорит о том, что область допустимых решений будет лежать в первом квадранте (между положительными направлениями осей).

Чтобы учесть остальные ограничения, заменим неравенства на равенства и получим уравнения прямых. Например, неравенство 6х₁ + 4х₂ ≤ 24 заменяется уравнением прямой 6х₁ + 4х₂ = 24. Чтобы провести эту линию, необходимо найти две точки, принадлежащие этой прямой. Через х₁ = 0 получим х₂ = 24/4 = 6, через х₂ = 0 получим х₂ = 24/6 = 4. Аналогично строятся остальные прямые.

Рис. 2.2. Область допустимых решений задачи

Рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость на два полупространства, которые располагаются по обе стороны соответствующей прямой. Точки по одну сторону прямой удовлетворяют неравенству, по другую сторону – нет. «Тестовой» точкой, проверяющей, точки какого полупространства удовлетворяют неравенству, а какого – нет, может служить точка (0, 0).

Точки в области допустимого решения удовлетворяют всем ограничениям задачи. Эта область ограничена отрезками А- F-Е- D- C- B. Чтобы найти оптимальное решение, необходимо определить направление возрастания целевой функции. Для этого целевую функцию z можно приравнять к двум значениям, например, к 10 и к 15, и получить уравнения прямых. На рис. 2.3 эти прямые показаны штриховыми линиями, а направление возрастания целевой функции – жирной стрелкой. Целевая функция может возрастать до тех пор, пока прямые, соответствующие значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей максимально возможному значению целевой функции, и будет точкой оптимума.

Рис. 2.3. Поиск оптимального решения

На рис. 2.3 видно, что оптимальное решение соответствует точке пересечения прямых (1) и (2), поэтому её координаты х₁ и х₂ находятся как решение системы уравнений, задающих эти прямые:

6х₁ + 4х₂ = 24, 1х₁ + 2х₂ = 6.

Отсюда оптимальное решение задачи: х₁ = 3; х₂ = 1,5; z = 21. Полученное решение означает, что для компании оптимальным выбором будет ежедневное производство 3 т краски для наружных работ и 1,5 т – для внутренних работ с ежедневным доходом в 21 тыс. руб.

Дата добавления: 2018-11-24; просмотров: 1248; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!