Курсовая работа: Использование линейного программирования для решения задач оптимизации

То есть, минимальная общая стоимость перевозок f = 1080.

Покажем на рисунке схему доставки сырья на заводы. (Числа указывают количество сырья в тоннах).

2.2 Решение производственной задачи

Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице.

Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной при условии, что изделие В надо выпустить не менее, чем изделия А.

Решение.

Обозначим через х₁ и х₂ количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х₁ +4х₂ ) единиц ресурса I, (4х₁ +4х₂ ) единиц ресурса II, (3х₁ +12х₂ ) единиц ресурса III. Так кА потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

12х₁ +4х₂ ≤ 300; 3х₁ + х₂ ≤ 75;

4х₁ +4х₂ ≤ 120; или х₁ + х₂ ≤ 30; (6)

3х₁ +12х₂ ≤ 252. х₁ +4х₂ ≤ 84.

По смыслу задачи переменные х₁ ≥ 0, х₂ ≥ 0. (7)

Суммарная прибыль А составит 30х₁ от реализации продукции А и 40х ₂ от реализации продукции В, то есть : F = 30х₁ +40х ₂ (8)

Далее будем решать задачу двумя методами:

1способ – симплексный метод

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком « + », так как все неравенства имеют вид « ≤ ».

Получим систему ограничений в виде :

3₁ +х₂ +х₃ ≤ 75;

х₁ +х₂ + х₄ ≤ 30; (9)

х₁ + 4х₂ + х₅ ≤ 84.

Для нахождения первоначального базисного решения разобьём переменные на две группы – основные и не основные. Так как определитель, составленный из коэффициентов при дополнительных переменных х₃ , х₄ , х₅ отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи.

I шаг.

Основные переменные: х₃ , х₄ , х_5.

Не основные переменные: х₁ , х_{2. .}

Выразим основные переменные через не основные :

х₃ = 75 - 3х₁ - х₂ ;

х₄ = 30 х₁ - х₂ ; (10)

х₅ = 84 - х₁ - 4х_2.

Положив основные переменные равными нулю, то есть х₁ = 0, х₂ = 0, получим базисное решение Х₁ = (0, 0, 75, 30, 84), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные: