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

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

КУРСОВАЯ РАБОТА

по дисциплине "Прикладная математика"

14 вариант

Выполнил: Рудковский Ф.А.

Москва 2004

ОГЛАВЛЕНИЕ

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

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

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

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

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. РАСПРЕДЕЛЕНИЕ КАПИТАЛЬНЫХ ВЛОЖЕНИЙ

АНАЛИЗ ДОХОДНОСТИ И РИСКА ФИНАНСОВЫХ ОПЕРАЦИЙ

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

Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица А затрат любого ресурса на единицу каждой продукции, вектор В объемов ресурсов и вектор С удельной прибыли

(1)

Требуется составить производственную программу (x₁, x₂, x₃, x₄), максимизирующую прибыль

(2)

при ограничениях по ресурсам:

(3)

где по смыслу задачи

(4)

Получили задачу на условный экстремум. Для ее решения систему неравенств (3) при помощи дополнительных неотрицательных неизвестных х₅, х₆, х₇ заменим системой линейных алгебраических

уравнений

(5)

где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений (5), удовлетворяющих условию неотрицательности х₁³0, х₂³0,… ,х₅³0,…, х₇³0. (6)

надо найти то решение, при котором функция (2) примет наибольшее значение.

Воспользуемся тем, что правые части всех уравнений системы (5) неотрицательны, а сама система имеет предпочитаемый вид – дополнительные переменные являются базисными. Приравняв к нулю свободные переменные х₁, х₂, х₃, х₄, получаем базисное неотрицательное решение

x₁=0, x₂=0, x₃=0, x₄=0, x₅=142, x₆=100, x₇=122 (7)

первые четыре компоненты которого определяют производственную программу x₁=0, x₂=0, x₃=0, x₄=0 (8)

по которой мы пока ничего не производим. Из выражения (2) видно, что наиболее выгодно начинать производить продукцию первого вида, так как прибыль на единицу продукции здесь наибольшая. Чем больше выпуск в этой продукции, тем больше прибыль. Выясним, до каких пор наши ресурсы позволяют увеличить выпуск этой продукции. Для этого придется записать для системы уравнений (5) общее решение

(9)

Мы пока сохраняем в общем решении х₂=х₃=х₄=0 и увеличиваем только х₁. При этом значения базисных переменных должны оставаться неотрицательными, что приводит к системе неравенств

или

т.е. 0 £ х₁£

Дадим х₁ наибольшее значение х₁=

, которое она может принять при нулевых значениях других свободных неизвестных, и подставим его в (9). Получаем для системы уравнений (5) частное неотрицательное решение:

х₁=

, х₂=0, х₃=0, х₄=0; x₅=

; x₆=

; x₇=0 (10)

Нетрудно убедиться, что это решение является новым базисным неотрицательным решением системы линейных алгебраических уравнений (5), для получения которого достаточно было принять в системе (5) неизвестную х₁ за разрешающую и перейти к новому предпочитаемому виду этой системы, сохранив правые части уравнений неотрицательными, для чего за разрешающее уравнение мы обязаны принять третье, так как

, а разрешающим элементом будет а₃₁=3.

Остается заметить, что процесс решения обычно записывается в виде некоторой таблицы 1.

~ С	34 20 8 23 0 0 0
~ С	Базис	Н	x₁ x₂ x₃ x₄ x₅ x₆ x₇	Пояснения
0	Х₅	142	2 0 2 3 1 0 0	z₀ = H
0	Х₆	100	1 5 4 2 0 1 0
0	Х₇	122	3 4 0 1 0 0 1
z₀ -z	0 - z	-34 -20 -8 -50 0 0 0
0	Х₅		0 -8/3 2 7/3 1 0 -2/3	min (26; 35,6;122)=26
0	Х₆		0 11/3 4 5/3 0 1 -1/3
34	Х₁		1 4/3 0 1/3 0 0 1/3
z₀ -z	4148/3-z	0 76/3 -8 -35/3 0 0 34/3
23	Х₄	26	0 -8/7 6/7 1 3/7 0 -2/7
0	Х₆	16	0 39/7 18/7 0 -5/7 1 1/7
34	Х₁	32	1 12/7 -2/7 0 -1/7 0 3/7
z₀ -z	1686-z	0 12 2 0 5 0 8	все D_j³0

Используя формулы исключения получаем для системы уравнений (5) новый предпочитаемый эквивалент и новую вспомогательную систему:

(11)

Первые три уравнения этой системы представляют некоторый предпочитаемый эквивалент системы уравнений (5) и определяют базисное неотрицательное решение (10) и производственную программу х₁=

, х₂=0, х₃=0, х₄=0, а из последнего уравнения системы (11) получается выражение функции цели через свободные переменные:

Очевидно, если имеется хотя бы один отрицательный коэффициент Dj при какой-нибудь переменной x_j в последнем уравнении системы (11), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. Мы нашли в последнем уравнении системы (11) наименьший отрицательный коэффициент min(Dj<0) = -

= D_4. Поэтому принимаем х₄ в системе (11) за разрешающую неизвестную, находим разрешающее уравнение по

(12)

и исключаем х₄ из всех уравнений системы (11), кроме первого уравнения. Укажем разрешающий элемент а₁₄=

Преобразуем вспомогательную систему (11), по формулам исключения.

та система преобразуется к виду

(13)

Первые три уравнения системы (13) представляют некоторый предпочитаемый эквивалент системы уравнений (5) и определяют базисное неотрицательное решение системы условий рассматриваемой задачи

x₁=32, x₂=0, x₃=0, x₄=26, x₅=0, x₆=16, x₇=0 (14)

т.е. определяют производственную программу x₁=32, x₂=0, x₃=0, x₄=26 (15)

и остатки ресурсов:

первого вида х₅=0

второго вида х₆=16 (16)

третьего вида х₇=0

Последнее уравнение системы (13) мы получаем, исключая х₄. В последнем уравнении системы (13) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательные переменные

z = 1686 -

- 2x₃ - 5x₅ - 8 x₇ (17)

то становится совершенно очевидным (в силу того, что все xj³0), что прибыль будет наибольшей тогда, когда

x₂=0, x₃=0, x₅=0, x₇=0 (18)

Это означает, что производственная программа (15) является наилучшей и обеспечивает предприятию наибольшую прибыль z_max = 1686 (19)

Проверим соотношение H=Q^-1B

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

Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент D₂=12 при переменной х₂ показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 12 единиц.