работа по дисциплине "Прикладная математика" (стр. 2 из 4)

Воспользуемся тем, что в оптимальной производственной программе x₂=0, x₃=0. Предположим, что четвертую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

ДВОЙСТВЕННАЯ ЗАДАЧА

Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям.

Теперь представим себе, что знакомый предприниматель П, занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у₁ рублей за каждую единицу первого ресурса, у₂ руб. – второго, у₃ руб. – третьего. Возникает вопрос: при каких ценах у₁, у₂, у₃ мы можем согласиться с предложением П.

Величины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.

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

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 2 единицы ресурса первого вида, 1 единицу ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах у₁, у₂, у₃ наши затраты составят 2у₁ + 1у₂ + 3у₃, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы продукции первого вида. На рынке за единицу первой продукции мы получили бы прибыль 34 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше 2у₁ + 1у₂ + 3у₃ ³ 34.

Аналогично, для трех оставшихся видов продукции:

+ 5у₂ + 4у₃³20

2у₁ + 4у₂ ³8

3у₁ + 2у₂ + 1у₃³23

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 142у₁ + 100у₂ + 122у₃ рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у₁, у₂, у₃, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.

Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок у(у₁, y₂, y₃) минимизирующий общую оценку всех ресурсов f = 142у₁ + 100у₂ + 122у₃ (1)

при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции

2у₁ + 1у₂ + 3у₃ ³ 34

+ 5у₂ + 4у₃³ 20 (2)

2у₁ + 4у₂ ³ 8

3у₁ + 2у₂ + 1у₃³ 23

причем оценки ресурсов не могут быть отрицательными y₁

0, y₂ 0, y₃ 0. (3)

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений

(х₁, х₂, х₃, х₄) и (y₁, y₂, y₃) пары двойственных задач необходимо и достаточно выполнение условий

x ₁ (2у₁ + у₂ + 3у₃ - 34) = 0 y₁ (2x₁ + 2x₃ + 3x₄ - 142) = 0

x ₂ ( 5у₂ + 4у₃- 20) = 0 y₂ ( x₁ +5x₂ + 4x₃ + 2x₄ - 100) = 0

x ₃ (2у₁ + 4у₂ - 8) = 0 y₃ (3x₁ +4x₂ + x₄- 122) = 0 .

x ₄ (3у₁ + 2у₂ + у₃ - 23) = 0

Ранее было найдено, что в решении исходной задачи х₁>0, x₄>0. Поэтому

2y₁ + y₂ + 3y₃ - 34 = 0

3y₁ + 2y₂ + y₃ - 23 = 0

Если же учесть, что второй ресурс был избыточным и, согласно той же теореме двойственности, ее двойственная оценка равна нулю у₂=0,

то приходим к системе уравнений

2y₁ + 3y₃ - 34 = 0

3y₁ + y₃ - 23 = 0

откуда следует у₁=5, у₃=8.

Таким образом, получили двойственные оценки ресурсов у₁=5; у₂=0; у₃=8, (4)

причем общая оценка всех ресурсов равна 1686.

Заметим, что решение (4) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка третьего ресурса у₃=8 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 8 единицы.

ЗАДАЧА О "РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА"

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют ²узкие места производства². Будем их заказывать дополнительно. Пусть T(t₁,t₂,t₃)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться услови

H + Q^-1T

0.

Задача состоит в том, чтобы найти вектор T (t₁, 0, t₃), максимизирующий суммарный прирост прибыли W = 5t₁ + 8t₃ (1) при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

(2)

предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида

(3)

причем по смыслу задачи t₁

0, t₃ 0. (4)

Переписав неравенства (2) и (3) в виде:

(5)

из условия (3) следует t1£142/3, t3£122/3 (6)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. 2.

I.) -3/7t1+2/7t3= 26

II.) 5/7t1-1/7t3= 16

III.) 1/7t1-3/7t3 = 32

M (458/15, 122/3)

Программа ²расшивки² имеет вид

t₁=458/15, t₂=0, t₃=122/3 и прирост прибыли составит 5*458/15+8*122/3=478.

Сводка результатов приведена в таблице:

Cj	34 8 20 33	b	x4+i	yi	ti
aij	2 0 2 3 1 5 4 2 3 4 0 1	142 100 122	0 16 0	5 0 8	488/15 0 122/3
Xj	32 0 0 26	1686	478
Dj	0 12 2 0

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Однородный продукт, сосредоточенный в 3 пунктах производства (хранения) в количествах 80; 60; 30 единиц, необходимо распределить между 4 пунктами потребления, которым необходимо соответственно 34; 40; 38; 53 единиц. Стоимость перевозки единицы продукта из пункта отправления в пункт назначения известна для всех маршрутов и равна

С =

.