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

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

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

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

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

Вид сырья	Нормы расхода сырья на одно изделие, кг A B	Общее количество сырья, кг
I	2 4	300
II	4 4	120
III	12	252
Прибыль от реализации одного изделия, ден. ед.	30 40

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

Решение.

Обозначим через х₁ и х₂ количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (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), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные: