И граничных условиях

Определить максимум целевой функции

Задача распределения ресурсов

Является задачей линейного программирования (ЗЛП), которая формулируется следующим образом:

F(x) = c₁x₁ + c₂x_{2 +…+} c_nx_n = max

при ограничениях:

а₁₁х₁ + а₁₂х₂ + … +а_1n ≤ b₁

а₂₁х₁ + а₂₂х₂ + … +а_2n ≤ b₂

_{………………………………………….}

аm₁х₁ + а_m2х₂ + … +а_mn ≤ b_m

x_j≥ 0, j = 1…n

Пример:Фирма выпускает товары трёх видов - x₁ , x₂ иx₃, используя ресурсы 1,2 и 3.

Каждая единица товара x₁приносит прибыль в 3 руб., товараx₂ -2 руб. и товараx₃ –1 руб.

Потребности в ресурсах:

Для выпуска товара x₁требуется 1 ед. ресурса 1, для выпуска x₂ -2 ед. ресурса 2.

Для выпуска x₁ требуется 1 ед. ресурса 1, для выпуска x₃ -1 ед. ресурса 3.

Для выпуска x₁ требуется 2 ед. ресурса 1, для выпуска x₂ -2 ед. ресурса 2.

Всего на складе 12 ед. ресурса 1, 4 ед. –ресурса 2 и 14 д. ресурса 3.

Все товары - x₁ , x₂ иx₃ ненулевые, т.е. x_i≥ 0, j = 1…n.

 

Определить распределение ресурсов по товарам для получения максимальной прибыли

 

Математическая модель ЗЛП примет вид:

F(x) = 2x₁ + 2x₂ + x₃ = max(1)

x₁ + 2x₂ ≤ 12(2)

x₁ + x₃ = 4(3)- система ограничений

2x₁ + 2x₂ ≤ 14(4)

Граничные условия:

x_j≥ 0, j = 1…n

Решение:

1. Выразим x₃ из второго уравнения и подставим в ЦФ - (1):

x₃ = 4 - x₁;(5)

F(x) = 2x₁ + 2x₂ + x₃ = 2x₁ + 2x₂ + 4 - x₁ = x₁ + 2x₂ + 4 =max

 

Из (3) следует, что т.к. x₃ ≥ 0, то 4 - x₁ ≥ 0 или x₁ ≤ 4.

2. Тогда система ограничений примет вид:

x₁ + 2x₂ ≤ 12

x₁ ≤ 4или-для уравнений в отрезках:

2x₁ + 2x₂ ≤ 14

.

 

Построим эти прямые на плоскости:

х1

Получили многоугольник – область определения решений (заштрихован), в котором нужно найти точку, где ЦФ F(x) = max.

 

3. Построение вектора-градиента.

Из целевой функции F(x) = 2x₁ + 2x₂ + 4берём коэффициенты при x₁иx₂, получаем вектор С = (2, 2), который соединяет т.О (0, 0) с т. (2, 2). Вектор С показывает направление увеличения ЦФ F(x).

Проводим перпендикулярно вектору-градиенту прямую и перемещаем её по вектору до пересечения с последней вершиной многоугольника – это т. (2, 5), в которой х₁ = 2, а х₂ =5.

Тогда из (5) x₃ = 4 - x₁ = 4 – 2 = 2, т.е. опорный план составит (2,5,2). При таких данных целевая функция

F(x) = 2x₁ + 2x₂ + x₃ = 4 + 10 + 2 = 16.

Таким образом, прибыль в 16 руб. будет получена, если выпускать товары x₁ и x₃ по 2 шт, а x₂ – в количестве 5 шт.

Подставляя значения опорного плана в систему ограничений (2-4), получим распределение ресурсов:

x₁ + 2x₂ ≤ 12или 2 + 10 = 12 – ресурс 1 истрачен полностью,

x₁ + x₃ = 4или 2 + 2 = 4 – ресурс 2 истрачен полностью,

2x₁ + 2x₂ ≤ 14или 4 + 10 = 14– ресурс 3 истрачен полностью.