Решение задач математического программирования

Размещено на http://www.allbest.ru/

Домашняя контрольная работа

По курсу «Математические модели в экономике»

Вариант 4

Задача 1

На трех железнодорожных станциях А₁, А₂ и А₃ скопилось 120, 110 и 130 незагруженных вагонов. Эти вагоны необходимо перегнать на железнодорожные станции В₁, В₂, В₃, В₄ и В₅. На каждой из этих станций потребность в вагонах соответственно равна 80, 60, 70, 100 и 50. Тарифы перегонки одного вагона определяются матрицей:

.

Составьте такой план перегонок вагонов, чтобы общая стоимость была минимальной.

Решение

Занесем исходные данные в распределительную таблицу.

	B1	B2	B3	B4	B5	Запасы
A1	2	4	1	6	7	120
A2	3	3	5	4	2	110
A3	8	9	6	3	4	130
Потребности	80	60	70	100	50

Проверим закрытость системы.

?А=120+110+130=360

?В=80+60+70+100+50=360

Условие баланса соблюдается. Запасы равны потребностям.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	B1	B2	B3	B4	B5	Запасы
A1	2[50]	4	1[70]	6	7	120
A2	3[30]	3[30]	5	4	2[50]	110
A3	8	9[30]	6	3[100]	4	130
Потребности	80	60	70	100	50

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

2. Подсчитаем число занятых клеток, их 7, а должно быть m+n-1=7. Следовательно, опорный план является невырожденным.

3. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i по занятым клеткам таблицы, в которых u_i+v_i=c_ij, полагая, что u_i=0.

u₁+v₁=2; 0+v₁=2; v₁=2.

u₁+v₃=1; 0+v₃=1; v₃=1.

u₂+v₁=3; u₂+2=3; u₂=1.

u₂+v₂=3; 1+v₂=3; v₂=2.

u₃+v₂=9; u₃+2=9; u₃=7.

u₃+v₄=3; 7+v₄=3; v₄=-4.

u₂+v₅=2; 1+v₅=2; v₅=1.

	v1=2	v2=2	v3=1	v4=-4	v5=1
u1=0	2[50]	4	1[70]	6	7
u2=1	3[30]	3[30]	5	4	2[50]
u3=7	8	9[30]	6	3[100]	4

Опорный план не является оптимальным, т.к. существуют оценки свободных клеток, для которых u_i+v_i>c_ij:

(3;1): 7+2>8; ?31=7+2-8=1.

(3;3): 7+1>6; ?33=7+1-6=2.

(3;5): 7+1>4; ?35=7+1-4=4.

Выбираем максимальную оценку свободной клетки (3;5): 4.

Для этого в перспективную клетку (3;5) ставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

	v1=2	v2=2	v3=1	v4=-4	v5=1
u1=0	2[50]	4	1[70]	6	7
u2=1	3[30]	3[30][+]	5	4	2[50][-]
u3=7	8	9[30][-]	6	3[100]	4[+]

Из грузов x_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. min(30,50)=30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из объемов грузов стоящих в минусовых клетках. В результате мы получим новый опорный план.

	B1	B2	B3	B4	B5	Запасы
A1	2[50]	4	1[70]	6	7	120
A2	3[30]	3[60]	5	4	2[20]	110
A3	8	9	6	3[100]	4[30]	130
Потребности	80	60	70	100	50

4. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i по занятым клеткам таблицы, в которых u_i+v_i=c_ij, полагая, что u_i=0.

u₁+v₁=2; 0+v₁=2; v₁=2

u₁+v₃=1; 0+v₃=1; v₃=1

u₂+v₁=3; u₂+2=3; u₂=1

u₂+v₂=3; 1+v₂=3; v₂=2

u₂+v₅=2; 1+v₅=2; v₅=1

u₃+v₅=4; u₃+1=4; u₃=3

u₃+v₄=3; 3+v₄=3; v₄=-0

	v1=2	v2=2	v3=1	v4=0	v5=1
u1=0	2[50]	4	1[70]	6	7
u2=1	3[30]	3[60]	5	4	2[20]
u3=3	8	9	6	3[100]	4[30]

Опорный план является оптимальным, т.к. для всех ui+vi?cij.

Затраты составят: F(x)=2*50+1*70+3*30+3*60+2*20+3*100+4*30=900.

Задача 2

Продукцией городского молочного завода являются молоко, кефир и сметана. На производство 1 т молока, кефира и сметаны требуется соответственно 1,01; 1,01 и 9,45 т молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино/час. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 час. Всего для производства цельномолочной продукции завод может использовать 136 т молока. Основное оборудование может быть занято в течение 21,4 машино/час, а автоматы по расфасовке сметаны -- в течение 16,25 час. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока. Определить объемы выпуска молочной продукции, позволяющие получить наибольшую прибыль.

Решение

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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x₄. В 2-м неравенстве смысла (?) вводим базисную переменную x₅. В 3-м неравенстве смысла (?) вводим базисную переменную x₆. В 4-м неравенстве смысла (?) вводим базисную переменную x₇ со знаком минус.

1.01x₁ + 1.01x₂ + 9.45x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ = 136

0.18x₁ + 0.19x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ = 21.4

0x₁ + 0x₂ + 3.25x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ = 16.25

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆-1x₇ = 100

Введем искусственные переменные x: в 4-м равенстве вводим переменную x₈;

1.01x₁ + 1.01x₂ + 9.45x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ = 136

0.18x₁ + 0.19x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ = 21.4

0x₁ + 0x₂ + 3.25x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ = 16.25

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆-1x₇ + 1x₈ = 100

Для постановки задачи на максимум целевую функцию запишем так:

F(X) = 30x₁+22x₂+136x₃ - Mx₈ > max

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

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

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

Из уравнений выражаем искусственные переменные:

x₈ = 100-x₁+x₇

которые подставим в целевую функцию:

F(X) = 30x₁ + 22x₂ + 136x₃ - M(100-x₁+x₇) > max

или

F(X) = (30+M)x₁+(22)x₂+(136)x₃+(-M)x₇+(-100M) > max

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

1.01	1.01	9.45	1	0	0	0	0
0.18	0.19	0	0	1	0	0	0
0	0	3.25	0	0	1	0	0
1	0	0	0	0	0	-1	1

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

Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x₄, x₅, x₆, x₈,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,136,21.4,16.25,0,100)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	X1	X2	X3	X4	X5	X6	X7	X8
x4	136	1.01	1.01	9.45	1	0	0	0	0
x5	21.4	0.18	0.19	0	0	1	0	0	0
x6	16.25	0	0	3.25	0	0	1	0	0
x8	100	1	0	0	0	0	0	-1	1
F(X0)	-100M	-30-M	-22	-136	0	0	0	M	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

Следовательно, 4-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₈ в план 1 войдет переменная x₁

Строка, соответствующая переменной x₁ в плане 1, получена в результате деления всех элементов строки x₈ плана 0 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₁ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₁ и столбец x₁ .

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

После преобразований получаем новую таблицу:

Базис	B	X1	X2	X3	X4	X5	X6	X7	X8
x4	35	0	1.01	9.45	1	0	0	1.01	-1.01
x5	3.4	0	0.19	0	0	1	0	0.18	-0.18
x6	16.25	0	0	3.25	0	0	1	0	0
x1	100	1	0	0	0	0	0	-1	1
F(X0)	3000	-22	-22	-136	0	0	0	-30	30+M

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (9.45) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₄ в план 2 войдет переменная x₃

Строка, соответствующая переменной x₃ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент РЭ=9.45

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₃ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₃ и столбец x₃ .

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

После преобразований получаем новую таблицу:

Базис	B	X1	X2	X3	X4	X5	X6	X7	X8
x3	3.7	0	0.11	1	0.11	0	0	0.11	-0.11
x5	3.4	0	0.19	0	0	1	0	0.18	-0.18
x6	4.21	0	-0.35	0	-0.34	0	1	-0.35	0.35
x1	100	1	0	0	0	0	0	-1	1
F(X0)	3503.7	0	-7.46	0	14.39	0	0	-15.46	15.46+M

Итерация №2.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В индексной строке F(x) выбираем максимальный по модулю элемент.

В качестве ведущего выберем столбец, соответствующий переменной x₇, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i7 и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (0.18) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы.

Вместо переменной x₅ в план 3 войдет переменная x₇

Строка, соответствующая переменной x₇ в плане 3, получена в результате деления всех элементов строки x₅ плана 2 на разрешающий элемент РЭ=0.18.

На месте разрешающего элемента в плане 3 получаем 1.

В остальных клетках столбца x₇ плана 3 записываем нули.

Таким образом, в новом плане 3 заполнены строка x₇ и столбец x₇ .

Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.

После преобразований получаем новую таблицу:

Базис	B	X1	X2	X3	X4	X5	X6	X7	X8
x3	1.68	0	-0.00594	1	0.11	-0.59	0	0	0
x7	18.89	0	1.06	0	0	5.56	0	1	-1
x6	10.77	0	0.0193	0	-0.34	1.93	1	0	0
x1	118.89	1	1.06	0	0	5.56	0	0	0
F(X0)	3795.81	0	8.86	0	14.39	85.91	0	0	M

Итерация №3.

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

x₃ = 1.68

x₁ = 118.89

F(X) = 30*118.89 + 136*1.68 = 3795.81

Задача 3

Для трехотраслевой экономической системы задана матрица коэффициентов прямых затрат и вектор конечного потребления:

А =, .

Требуется:

1) Определить, продуктивна ли матрица А?

2) Найти коэффициенты полных материальных затрат.

3) Найти вектор валовой продукции.

4) Заполнить схему межотраслевого баланса.

5) Определить абсолютное изменение валового выпуска продукции третьей отрасли, если спрос на товары 1-й отрасли увеличился на 60 единиц, а спрос на товары 3-й отрасли сократился на 80 единиц.

Решение

1. Одним из критериев продуктивности матрицы А является отличие определителя матрицы (E-A) от нуля.

Находим матрицу (E-A):

Вычисляем обратную матрицу (E-A)^-1:

Определитель равен: ?=0.5*(0.7*0.7-(-0.1*0))-(-0.6*(-0.2*0.7-(-0.1*(-0.1))))+(-0.2*(-0.2*0-0.7*(-0.1)))=0.141.

Определитель отличен от нуля, следовательно матрица является невырожденной и продуктивной и для нее можно найти обратную матрицу A^-1.

2. Если ввести в рассмотрение матрицу коэффициентов прямых затрат A = (a_ij), вектор-столбец валовой продукции X = (X_i) и вектор-столбец конечной продукции Y = (Y_i), то математическая модель межотраслевого баланса примет вид:

X = AX +Y

Матрица A имеет неотрицательные элементы и удовлетворяет критерию продуктивности (при любом j сумма элементов столбца ?a_ij ? 1.

Определим матрицу коэффициентов полных затрат точно с помощью формул обращения невырожденных матриц. Коэффициент полных затрат (bij) показывает, какое количество продукции i-й отрасли нужно произвести, чтобы с учетом прямых и косвенных затрат этой продукции получить единицу конечной продукции j-й отрасли.

Полные затраты отражают использование ресурса на всех этапах изготовления и равны сумме прямых и косвенных затрат на всех предыдущих стадиях производства продукции.

Транспонируем матрицу

Найдем для нее алгебраические дополнения

Обратная матрица



3 Найдем вектор валовой продукции трех отраслей

4. Для определения элементов первого квадранта материального межотраслевого баланса воспользуемся формулой x_ij = a_ij * X_j. Составляющие третьего квадранта (условно-чистая продукция) находятся как разность между объемами валовой продукции и суммами элементов соответствующих столбцов найденного первого квадранта. Межотраслевой баланс состоит из четырех квадрантов (табл.). Первый квадрант отражает межотраслевые потоки продукции. Второй характеризует отраслевую материальную структуру национального дохода. Третий представляет национальный доход как стоимость условно-чистой продукции (Z_j), равной сумме амортизации (c_j), оплаты труда (v_j) и чистого дохода j-й отрасли (m_j). Четвертый квадрант показывает конечное распределение и использование национального дохода.

Производящие отрасли	Потребляющие отрасли			Конечный продукт	Валовый продукт
	1	2	3
1	1450,35	782,98	167,38	500	2900,71
2	1740,43	1174,47	0	1000	3914,89
3	580,14	391,49	502,13	200	1673,76
Чистый доход	-870,21	1565,96	1004,26	1700
Валовый продукт	2900,71	3914,89	1673,76		8489,36

5. Чтобы определить абсолютное изменение валового выпуска продукции третьей отрасли подставим данные в уравнение вида , где - коэффициенты полных затрат, а - изменение спроса на товары j-й отрасли. Получаем:

Т.е. валовый выпуск продукции третьей отрасли уменьшится на 45,2 единиц.

Задача 4

транспортный математический модель симплекс матрица

Руководителю требуется принять решение в условиях полной неопределенности. Он владеет информацией о возможных последствиях принятия решения, заданных матрицей

Q =

Составить матрицу рисков и определить оптимальное решение по правилам Вальда, Сэвиджа, Гурвица, если л=1/3.

Решение

Для составления матрицы рисков найдем

Теперь составим матрицу рисков по формуле

Правило Вальда рекомендует принять такое решение , что

Для начала найдем

:

Согласно правилу Вальда нужно принять третье решение т.к.

.

Правило Сэвиджа рекомендует принять такое решение , что

Определим

:

Согласно правилу Сэвиджа рекомендует принять 1-е или 3-е решение, т.к.

.

По правилу Гурвица следует принять такое решение, которое соответствует формуле

, где

Определим

,

следовательно, нужно принять третье решение. Исходя их всех правил нужно принять третье решение.

Задача 5

Проект строительства плавательного бассейна состоит из девяти работ.

Работа	Непосредственно предшествующая работа	Время выполнения работы, нед.
A	-	5
B	-	4
C	A, B	6
D	A, B	9
E	B	3
F	C	2
G	D	8
H	D, F	8
I	E, G, H	4

Постройте сетевую модель выполнения проекта. Каков ожидаемый срок завершения проекта?

Решение

Для построения построим для начала сетевой график, используя правила построения и порядок следования событий.

1-е событие, это начало работ. Далее следует одновременное начало работ А и В. С учетом что событие «окончание работы В» наступит раньше чем «закончена работа А и В» то порядковый номер 2 присваиваем событию, которое наступает после действия В и соответственно событию «закончена работа А и В» присваивается номер 3. Для того чтобы обозначить событие одновременного завершение работ А и В добавляем фиктивную работу, которая обозначается пунктирной стрелкой.

После наступления события «закончена работа А и В» следуют работы С и D. А после наступления события «закончена работа С» следует работа F. С учетом того что длительность работы С меньше чем длительность одновременно начинающейся работы D, то присваиваем событию «закончена работа С» номер 4.

Размещено на http://www.allbest.ru/

Т.к. общая продолжительность работ С и F меньше чем длительность работы D, то событие «окончание работы F» получает порядковый номер 5, а соответственно событие «закончена работа D» получает номер 6. Параллельно с тем после события «закончена работа В» началась работа Е. Отобразим промежуточный сетевой график.

Размещено на http://www.allbest.ru/

Событие 5 имеет следует после завершение работы F и работы D, значит нужно ввести фиктивную работу в виде пунктирной стрелки, которая соединяет событие «закончена работа D» и событие «закончена работа F». После события «закончена работа D и F» следует работа H. После события «закончена работа D» следует работа G. Три работы H,G и Е завершаются событием «закончены работы H,G и Е», после которого следует работа I, которая является итоговой. Отобразим окончательный сетевой график.

Размещено на http://www.allbest.ru/

Рассчитаем временные параметры событий.

- ранний срок наступления события i, минимально необходимый для выполнения всех работ, которые предшествуют событию i;

- поздний срок наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети;

- резерв события i, т.е. время, на которое может быть отсрочено наступление события i без нарушения сроков завершения проекта в целом.

Временные параметры отображаются в событиях на сетевом графике следующим образом

Ранние сроки свершения событий рассчитываются от исходного (И) к завершающему (З) событию следующим образом:

1) для исходного события И ;

2) для всех остальных событий I

,

где максимум берется по всем работам , входящим в событие i; - длительность работы

Поздние сроки свершения событий рассчитываются от завершающего к исходному событию:

1) для завершающего события З ;

2) для всех остальных событий ,

где минимум берется по всем работам , выходящим из события i; - длительность работы (k,i)

Заполним параметрами события в сетевом графике. Итоговый график отображен ниже.

Размещено на http://www.allbest.ru/

Время выполнения проекта равно 26 недель.

Размещено на Allbest.ru

...