Задача 4. Смесь можно составить из n продуктов Сj (j=1,n)

Смесь можно составить из n продуктов С_j (j=1, n). В каждом из продуктов содержится m компонентов. Минимально допустимый объем содержания i-го компонента в смеси выражается величиной b_i (i=1, 3). Содержание i-го компонента в единице j-го продукта выражается величиной а_{ij .} Цена единицы j-го продукта равна с_{j .} Составить смесь, минимальную по стоимости, выбрав для решения данной задачи наиболее рациональный способ.

Смесь, минимальная по стоимости:

7x₁ + 5x₂ + 8x₃ ≥ 70

8x₁ + 2x₂ + 3x₃ ≥ 40

9x₁ + 6x₂ + 7x₃ ≥ 50

x₁ ≥ 0; x₂ ≥ 0; x₃ ≥ 0

F = 9x₁ + 6x₂ + 7x₃ → min

После транспонирования матрицы элементов a_ij, cсимметричная двойственная задача будет иметь вид:

S(y₁, y₂, y₃) = 70y₁ + 40y₂ + 50y₃ → max, при ограничениях:

7y₁ + 8y₂ + 9y₃ ≥ 9

5y₁ + 2y₂ + 6y₃ ≥ 6

8y₁ + 3y₂ + 7y₃ ≥ 7

y₁ ≥ 0; y₂ ≥ 0; y₃ ≥ 0

Для решения двойственной задачи линейного программирования симплекс – методом, приведём систему неравенств к виду системы уравнений:

7y₁ + 8y₂ + 9y₃ + y₄ ≥ 9

5y₁ + 2y₂ + 6y₃ + y₅ ≥ 6

8y₁ + 3y₂ + 7y₃ + y₆ ≥ 7

y₁≥ 0; y₂≥ 0; y₃≥ 0; y₁≥ 0; y₂≥ 0; y₃≥ 0

S(y₁, y₂, y₃) = 70y₁ + 40y₂ + 50y₃ → max

По правилу соответствия переменных, базисным переменным прямой задачи соответствуют свободные переменные двойственной задачи:

x₁ x₂ x₃ x₄ x₅ x₆

y₁ y₂ y₃ y₄ y₅ y₆

Первая симплексная таблица:

Вторая симплексная таблица:

Третья симплексная таблица:

В последней таблице в строке Δ нет отрицательных элементов. В соответствии с критерием оптимальности точка максимума S_max = 2950/43 достигнута при значениях: y₁ = 29/43; y₂ = 23/43; y₃ = 0.

По теореме двойственности: F_min = S_max = 2950/43.

На основании правила соответствия между переменными, оптимальное решение прямой задачи:

y₄ x₁ = 110/43 y₅ x₂ = 0 y₆ x₃ = 280/43

Ответ: В смесь минимальной стоимости 2950/43 целесообразно включить 110/43 единиц продукта C₁, 280/43 единиц продукта C₃, а продукт C₂ не включать.