Задачи и решения по прикладной математикеРефераты >> Математика >> Задачи и решения по прикладной математике
Используя формулы исключения получаем для системы уравнений (5) новый предпочитаемый эквивалент и новую вспомогательную систему:
(11)
Первые три уравнения этой системы представляют некоторый предпочитаемый эквивалент системы уравнений (5) и определяют базисное неотрицательное решение (10) и производственную программу х1=, х2=0, х3=0, х4=0, а из последнего уравнения системы (11) получается выражение функции цели через свободные переменные:
Очевидно, если имеется хотя бы один отрицательный коэффициент Dj при какой-нибудь переменной xj в последнем уравнении системы (11), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. Мы нашли в последнем уравнении системы (11) наименьший отрицательный коэффициент min(Dj<0) = -= D4. Поэтому принимаем х4 в системе (11) за разрешающую неизвестную, находим разрешающее уравнение по (12)
и исключаем х4 из всех уравнений системы (11), кроме первого уравнения. Укажем разрешающий элемент а14= .
Преобразуем вспомогательную систему (11), по формулам исключения.
та система преобразуется к виду
(13)
Первые три уравнения системы (13) представляют некоторый предпочитаемый эквивалент системы уравнений (5) и определяют базисное неотрицательное решение системы условий рассматриваемой задачи
x1=32, x2=0, x3=0, x4=26, x5=0, x6=16, x7=0 (14)
т.е. определяют производственную программу x1=32, x2=0, x3=0, x4=26 (15)
и остатки ресурсов:
первого вида х5=0
второго вида х6=16 (16)
третьего вида х7=0
Последнее уравнение системы (13) мы получаем, исключая х4. В последнем уравнении системы (13) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательные переменные
z = 1686 - - 2x3 - 5x5 - 8 x7 (17)
то становится совершенно очевидным (в силу того, что все xj³0), что прибыль будет наибольшей тогда, когда
x2=0, x3=0, x5=0, x7=0 (18)
Это означает, что производственная программа (15) является наилучшей и обеспечивает предприятию наибольшую прибыль zmax = 1686 (19)
Проверим соотношение H=Q-1B
Итак, организовав направленный перебор базисных неотрицательных решений системы условий задачи, мы пришли к оптимальной производственной программе и указали остатки ресурсов, а также максимальную прибыль.
Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент D2=12 при переменной х2 показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 12 единиц.
Воспользуемся тем, что в оптимальной производственной программе x2=0, x3=0. Предположим, что четвертую и третью продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:
ДВОЙСТВЕННАЯ ЗАДАЧА
Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям.
Теперь представим себе, что знакомый предприниматель П, занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у1 рублей за каждую единицу первого ресурса, у2 руб. – второго, у3 руб. – третьего. Возникает вопрос: при каких ценах у1, у2, у3 мы можем согласиться с предложением П.
Величины у1, у2, у3 принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.
Напомним, что в нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид
Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 2 единицы ресурса первого вида, 1 единицу ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах у1, у2, у3 наши затраты составят 2у1 + 1у2 + 3у3, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы продукции первого вида. На рынке за единицу первой продукции мы получили бы прибыль 34 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше 2у1 + 1у2 + 3у3 ³ 34.
Аналогично, для трех оставшихся видов продукции:
+ 5у2 + 4у3³20
2у1 + 4у2 ³8
3у1 + 2у2 + 1у3³23
Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 142у1 + 100у2 + 122у3 рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у1, у2, у3, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.
Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок у(у1, y2, y3) минимизирующий общую оценку всех ресурсов f = 142у1 + 100у2 + 122у3 (1)
при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции
2у1 + 1у2 + 3у3 ³ 34
+ 5у2 + 4у3³ 20 (2)
2у1 + 4у2 ³ 8
3у1 + 2у2 + 1у3³ 23
причем оценки ресурсов не могут быть отрицательными y10, y20, y30. (3)