Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Составить математическую модель линейной производственной задачи

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

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

Институт информационных систем управления

Кафедра прикладной математики

Курсовая работа

по учебной дисциплине «Прикладная математика»

Вариант № 7

Исполнитель

Студентка Иванова Кристина группы БУ-2-2(в/о)

Руководитель курсовой работы

к.б.н., доцент _____________ В.Л. Супоницкий

(подпись)

Москва 2008

Содержание

Задание на курсовую работу

Линейная производственная задача

Двойственная задача

Задача о «расшивке узких мест производства»

Транспортная задача линейного программирования

Динамическое программирование.

Распределение капитальных вложений

Анализ доходности и риска финансовых операций

Задача формирования оптимального портфеля ценных бумаг

СПИСОК ЛИТЕРАТУРЫ:

Задание на курсовую работу

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

компактно записаны в виде

c1 c2 c3 c4

а11 а12 а13 а14 b1

a21 a22 a23 a24 b2

a31 a32 a33 a34 b3 .

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

В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных.

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

Если по оптимальной производственной программе какие-то два вида продукции не должны выпускаться, то в таблице исходных данных вычеркнуть соответствующие два столбца, составить математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решить эту задачу графически. Проверить решение исходной задачи симплексным методом с помощью ЭВМ (приложение 12).

2. Сформулировать задачу, двойственную линейной производственной задаче, как задачу определения расчетных оценок ресурсов, и найти ее решение, пользуясь второй основной теоремой двойственности (о дополняющей нежесткости). Указать оценку единицы каждого ресурса, минимальную суммарную оценку всех ресурсов, оценки технологий (см. раздел 5).

Применить найденные двойственные оценки ресурсов к решению следующей задачи.

3. Сформулировать задачу о "расшивке узких мест производства" и составить ее математическую модель (см. раздел 6). Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о ²расшивке узких мест производства² при условии, что дополнительно можно получить от поставщиков не более одной трети первоначально выделенного объема ресурса любого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительно возможную прибыль. Для пополненного вектора ресурсов найдите новую оптимальную производственную программу.

По пунктам 1, 2, 3 составить сводку результатов [см. стр. 31].в методичке по другому.

4. Составить математическую модель транспортной задачи по исходным данным из приложения 2, где вектор объемов производства А(a1,..., am), потребления - В (b1,..., bn) и матрица транспортных издержек С=(сij), i =; j = кратко записаны в виде

b1 b2 . . . bn

a1 c11 c12 . . . c1n

a2 c21 c22 . . . c2n

. . . . . . . . . . . . . . . . . . . .

am cm1 cm2 . . . cmn

Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов (см. раздел 7). Проверить решение транспортной задачи с помощью ЭВМ (приложение 12).

5. Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения (см. раздел 8), располагающего суммой в 700 тыс. руб., по исходным данным, приведенным в приложении 3 (выделяемые суммы кратны 100 тыс.).

16.Провести анализ доходности и риска финансовых операций (см. раздел 12) по исходным данным, приведенным в приложении 7.

17.Решить задачу формирования оптимального портфеля ценных бумаг (см. раздел 13): бумаги первого вида - безрисковые ожидаемой эффективности m0, а второго и третьего вида - некоррелированные рисковые ожидаемых эффективностей m1, m2 c рисками s1, s2. Исходные данные взять из приложения 8.

Линейная производственная задача

Исходные данные

35	41	22	12
2	2	3	4	151
3	1	0	2	156
1	4	4	0	162

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

2 2 3 4 151

А = 3 1 0 2 В= 156 С=(35,41,22,12)

1 4 4 0 162

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

Математическая модель задачи:

Найти производственную программу

X = (x1, x2, x3, x4)

Максимизирующую прибыль

z=35x1+41x2+22x3+12х4max (1)

z(x1, x2, x3, x4) = c1x1 + c2x2 + c3x3 + c4x4  max (z- целевая функция);

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

2x1 + 2x2 + 3x3 + 4x4  151

3x1 + x2 + + 2x4  156 (2)

x1 +4x2 + 4x3  162

a11x1+a12x2+a13x3+a14x4 < в1

а21х1+а22х2+а23х3+а34х4 < в2;

а31х1+а32х2+а33х3+а34х4 < в3

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

x10, x20, x30, x40 (3)

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

2x1 + 2x2 + 3x3 + 4x4 + x5 = 151

3x1 + x2 + + 2x4 + x6 = 156 (4)

x1 + 4x2 + 4x3 + x7 = 162

где x5, x6, x7 – остатки соответствующих ресурсов.

x10, x20, x30, x40, x50, x60, x70. (5)

Среди всех решений системы уравнений (4), удовлетворяющих условию (5), надо найти то решение, при котором функция (1) примет наибольшее значение.

Воспользуемся тем, что правые части всех уравнений системы (4) неотрицательны, а сама система имеет предпочитаемый вид – дополнительные переменные являются базисными. Приравняв к нулю свободные переменные х1, х2, х3, х4, получаем базисное неотрицательное решение:

x1=0, x2=0, x3=0, x4=0, x5=151, x6=156, x7=162 (6)

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

x1=0, x2=0, x3=0, x4=0 (7)

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

x5=151- 2x1 - 2x2 - 3x3 - 4x4

x6=156- 3x1 - x2 - - 2x4 (8)

x7=162- x1 - 4x2 - 4x3

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

151- 2x2 ≥ 0 x2≤ 75,5

156- x2 ≥ 0 x2≤ 156 т.е. 0≤ x2≤40,5 (9)

162 - 4x2 ≥ 0 x2≤ 40,5

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

x1=0, x2=40,5, x3=0, x4=0, x5=61, x6=115,5, x7=0 (10)

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

min (bi/ai2>0) = min (151/2,156/1,162/4) = 162/4,

где а32=4 будет разрешающим элементом разрешающее уравнение – 3

разрешающая переменная – x2

Совершим шаг Гаусса-Жордана, и применив известные формулы исключения, получаем для системы уравнений (4) новый предпочитаемый эквивалент:

3/2x1 +x3 + 4x4 + x5 - 1/2x7 = 70

11/4x1 - x3 + 2x4 + x6 - 1/4x7 = 231/2 (11)

1/4x1+ x2 + x3 + 1/4x7 = 162/4

Приравняв к нулю свободные переменные х2, х3, х4, х7, получаем базисное неотрицательное решение, совпадающее с (10), причем первые четыре компоненты его определяют новую производственную программу

x1=38, x2=0, x3=0, x4=0 (12)

Исследуем, является ли эта программа наилучшей, т.е. обеспечивает ли она наибольшую прибыль. Для этого выразим функцию прибыли (1) через новые свободные переменные х2, х3, х4, х7.

Из последнего уравнения системы (11) выражаем базисную переменную х1 через свободные и подставляем в (1). Получаем:

z = 48*(38-5/6x2 - 1/6x3 -1/6x7) +30x2+29x3+10х4 =

= 1824 - 40x2 -8x3 -8x7 +30x2 +29x3 +10x4 = 1824-10 x2+21 x3+10 x4-8 x7 (13)

Видим, что программа (12) не является наилучшей, так как прибыль будет расти, если мы начнем производить или третью, или четвертую продукцию, но наиболее быстро функция z растет при возрастании х3. Поэтому принимаем х3 в системе (11) за разрешающую неизвестную, находим разрешающее уравнение

min (24,30,228) = 24 - разрешающее ур-ние 1

Важно обратить внимание на то, что эти преобразования можно выполнить очень просто. Представим соотношение (1) в виде уравнения

-48x1-30x2-29x3-10х4 =0- z (14)

и припишем его к системе (4). Получается вспомогательная система уравнений

3x1 + 2x2 + 4x3 + 3x4 + x5 = 198

2x1 + 3x2 + x3 + 2x4 + x6 = 96 (15)

6x1 + 5x2 + x3 + x7 = 228

-48x1-30x2-29x3-10х4 =0- z

Теперь, если посмотреть на систему уравнений (15), то достаточно умножить третье уравнение системы (15) на 8 и прибавить к четвертому, получим

48 x1+40 x2+8 x3+8 x7=1824

10 x2-21 x3-10 x4+8 x7=1824 - z (16)

Таким образом, приписав к системе (11) уравнение (16), получаем:

-0,5x2 + 3,5x3 + 3x4 + x5 - 0,5 x7 = 84

4/3x2 +2/3 x3 +2x4 + x6 - 1/3x7 = 20 (17)

x1+ 5/6x2 + 1/6x3 +1/6x7 = 38

10 x2-21 x3-10 x4+8 x7=1824 - z

Очевидно, если имеется хотя бы один отрицательный коэффициент j при какой-нибудь переменной xj в последнем уравнении системы (17), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. С помощью (13) мы выяснили, что следует начинать производить продукцию третьего вида, т.е. фактически мы нашли в последнем уравнении системы (17) наименьший отрицательный коэффициент

min(j<0) = min(-21,-10) = -21 = 3

и решили перевести свободную переменную х3 в число базисных, для чего, определили разрешающее уравнение и указали разрешающий элемент а13=4.

Учитывая сказанное выше, теперь мы будем преобразовывать не систему (11), а всю вспомогательную систему (17), по правилу прямоугольника:

аij = аrj/ аrs , r = i

а11= 0

а12 = -1/7

а13 =1

а14 =6/7

а15 =2/7

а16 = 0

а17 = -1/7

аij = аij – аis/ аrs * аrj , i≠r

а21= 0

а22 =30/21

а23 =0

а24 =10/7

а25 = -4/7

а26 =1

а27 = -5/21

а31 =1

а32 = 6/7

а33=0

а34 = -1/7

а35 = -1/21

а36 =0

а37 = 4/21

а41 = 0

а42 =7

а43=0

а44 =8

а45 =6

а46 =0

а47 = 5

bi = br/ аrs , r = i

b1= 24

bi = bi - аis/ аrs* br , i≠r

b2 = 4

b3 = 34

b4 = 2328-z

-1/7x2 + x3 + 6/7x4 +2/7 x5 – 1/7 x7 = 24

30/21x2 +10/7 x4 - 4/21x5 + x6 - 5/21x7 = 4 (18)

x1+ 6/7x2 – 1/7x4- 1/21x5 +4/21x7 = 34

7 x2+8 x4+6x5 +5 x7=2328 - z

x1=34, x2=0, x3=24, x4=0, x5=0, x6=4, x7=0 (19)

т.е. определяют производственную программу

x1=34, x2=0, x3=24, x4= 0 (20)

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

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

второго вида х6=4 (21)

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

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

Z = 2328 -7 x2-8 x4-6x5 -5 x7 (22)

то становится совершенно очевидным (в силу того, что все xj0), что прибыль будет наибольшей тогда, когда x2=0, x4=0, x5=0, x7=0 (23)

Это означает, что производственная программа (20) является наилучшей и обеспечивает предприятию наибольшую прибыль zmax = 2328 (24)

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

Процесс решения обычно записывается в виде симплексной таблицы, где представлены расширенные матрицы вспомогательных систем уравнений (15)  (17)  (18):

			48 30 29 10 0 0 0	Пояснения
	Базис	Н	x1 x2 x3 x4 x5 x6 x7
0	х5	198	3 2 4 3 1 0 0	z0 = H
0	х6	96	2 3 1 2 0 1 0
0	х7	228	6 5 1 0 0 0 1	Min(j<0)=-48
	z	0	-48 -30 -29 -10 0 0 0	Min (bi/ai1>0)=228/6
0	х5	84	0 -0,5 3,5 3 1 0 -0,5	Min (-21, -10)=-21
0	х6	20	0 4/3 2/3 2 0 1 -1/3
48	х1	38	1 5/6 1/6 0 0 0 1/6	Min (24,30,228)= 24
	z	1824	0 10 -21 -10 0 0 8
29	х3	24	0 -1/7 1 6/7 2/7 0 -1/7
0	х6	4	0 30/21 0 10/7 -4/21 1 -5/21	все j 0
48	х1	34	1 6/7 0 -1/7 -1/21 0 4/21
	z	2328	0 7 0 8 6 0 5

Проверим получившийся результат.

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

X (x1, x3) - ?

Z = 48x1 + 29x3  max

3x1 + 4x3  198 x3  198/4-3/4 x1 I

2x1 + x3  96 x3  96 - 2x1 II

6x1 + x3  228 x3  228 - 6x1 III

x1  0, x2  0

198/4

38 48 66 x1

III II I

Точка A находится на пересечении I и III линий.

x3 = 198/4-3/4 x1 x1 =34

x3 = 228 - 6x1 x3 =24

Из графика видно, что результаты совпадают.

Для того, чтобы убедиться в правильности полученного решения, следует проверить отношение Н = Q-1 * В:

24 198 2/7 0 -1/7

Н = 4 В= 96 Q-1 = -4/21 1 -5/21

34 228 -1/21 0 4/21

24 2/7 0 -1/7 198

4 = -4/21 1 -5/21 * 96

34 -1/21 0 4/21 228

Обращенный базис сходится.