Определить максимум целевой функции
Задача распределения ресурсов
Является задачей линейного программирования (ЗЛП), которая формулируется следующим образом:
F(x) = c1x1 + c2x2 +…+ cnxn = max
при ограничениях:
а11х1 + а12х2 + … +а1n ≤ b1
а21х1 + а22х2 + … +а2n ≤ b2
………………………………………….
аm1х1 + аm2х2 + … +аmn ≤ bm
xj ≥ 0, j = 1…n
Пример: Фирма выпускает товары трёх видов - x1, x2 и x3, используя ресурсы 1,2 и 3.
Каждая единица товара x1 приносит прибыль в 3 руб., товара x2 - 2 руб. и товара x3 – 1 руб.
Потребности в ресурсах:
Для выпуска товара x1 требуется 1 ед. ресурса 1, для выпуска x2 -2 ед. ресурса 2.
Для выпуска x1 требуется 1 ед. ресурса 1, для выпуска x3 - 1 ед. ресурса 3.
Для выпуска x1 требуется 2 ед. ресурса 1, для выпуска x2 - 2 ед. ресурса 2.
Всего на складе 12 ед. ресурса 1, 4 ед. –ресурса 2 и 14 д. ресурса 3.
Все товары - x1, x2 и x3 ненулевые, т.е. xi ≥ 0, j = 1…n.
Определить распределение ресурсов по товарам для получения максимальной прибыли
Математическая модель ЗЛП примет вид:
F(x) = 2x1 + 2x2 + x3 = max (1)
x1 + 2x2 ≤ 12 (2)
x1 + x3 = 4 (3)- система ограничений
2x1 + 2x2 ≤ 14 (4)
Граничные условия:
xj ≥ 0, j = 1…n
Решение:
1. Выразим x3 из второго уравнения и подставим в ЦФ - (1):
x3 = 4 - x1;(5)
F(x) = 2x1 + 2x2 + x3 = 2x1 + 2x2 + 4 - x1 = x1 + 2x2 + 4 =max
Из (3) следует, что т.к. x3 ≥ 0, то 4 - x1 ≥ 0 или x1 ≤ 4.
2. Тогда система ограничений примет вид:
x1 + 2x2 ≤ 12
x1 ≤ 4 или - для уравнений в отрезках:
2x1 + 2x2 ≤ 14
.
Построим эти прямые на плоскости:
|

Получили многоугольник – область определения решений (заштрихован), в котором нужно найти точку, где ЦФ F(x) = max.
3. Построение вектора-градиента.
Из целевой функции F(x) = 2x1 + 2x2 + 4 берём коэффициенты при x1 и x2, получаем вектор С = (2, 2), который соединяет т.О (0, 0) с т. (2, 2). Вектор С показывает направление увеличения ЦФ F(x).
Проводим перпендикулярно вектору-градиенту прямую и перемещаем её по вектору до пересечения с последней вершиной многоугольника – это т. (2, 5), в которой х1 = 2, а х2 =5.
Тогда из (5) x3 = 4 - x1 = 4 – 2 = 2, т.е. опорный план составит (2,5,2). При таких данных целевая функция
F(x) = 2x1 + 2x2 + x3 = 4 + 10 + 2 = 16.
Таким образом, прибыль в 16 руб. будет получена, если выпускать товары x1 и x3 по 2 шт, а x2 – в количестве 5 шт.
Подставляя значения опорного плана в систему ограничений (2-4), получим распределение ресурсов:
x1 + 2x2 ≤ 12 или 2 + 10 = 12 – ресурс 1 истрачен полностью,
x1 + x3 = 4 или 2 + 2 = 4 – ресурс 2 истрачен полностью,
2x1 + 2x2 ≤ 14 или 4 + 10 = 14– ресурс 3 истрачен полностью.