Математические модели и методы исследования в экономике

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

1

Министерство образования и науки Российской Федерации

Филиал федерального государственного автономного образовательного учреждения высшего профессионального образования

«Российский государственный профессионально-педагогический

университет» в г. Советском

Кафедра профессионально-педагогического образования

Контрольная работа

по дисциплине

Математические модели и методы исследования в экономике

Выполнил:

студентка гр. Св-211 сГМУ

Конева Е.Р.

Советский 2015



СОДЕРЖАНИЕ

ЗАДАЧА 1

ЗАДАЧА 2

ЗАДАЧА 3

ЗАДАЧА 4

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ



ЗАДАЧА №1

1. Найти максимальное значение целевой функции методом Гомори (методом отсечений) , при условиях:

.

Дать геометрическую интерпретацию решения задачи.

РЕШЕНИЕ

Это задача целочисленного программирования. Ее решение методом отсечений распадается на несколько этапов. Первоначально необходимо решить задачу линейного программирования (ЛП) без учета целочисленности переменных. Такая задача решается стандартным симплекс-методом. Для применения симплекс-метода необходимо записать задачу ЛП в канонической форме. Добавим в левую часть ограничений-неравенств неотрицательные переменные x₃, x₄ для того, чтобы ограничения можно было представить в виде точных равенств, тогда

, x₁ 0, x₂ 0, x₃ 0, x₄ 0. Обозначим через

вектор-столбец переменных. В дальнейшем будем его записывать в транспонированном виде X^T=(x₁ x₂ x₃ x₄). Начальная таблица симплекс-метода и ее дальнейшие преобразования приводятся ниже.

0)	f	x1	x2	x3	x4	B
f-строка	1	-4	-1	0	0	0
	0	2	1	1	0	13
	0	-3	1	0	1	9
1)	f	x1	x2	x3	x4	B
f-строка	1	0	1	2	0	26
	0	1	1/2	1/2	0	13/2
	0	0	5/2	3/2	1	57/2

В приведенных таблицах стрелками указаны разрешающие столбцы и строки. Первоначальный план X₀^T=(0 0 13 9) есть неотрицательное базисное решение, которое не является оптимальным. На это указывают отрицательные элементы в f-строке. План X₁^T=(13/2 0 0 0) является оптимальным - в f-строке нет отрицательных элементов. Однако этот план не удовлетворяет условию целочисленности переменных. Графически этот план соответствует точке пересечения сплошной линий L₁ () и с координатной осью х₁ в точке (13/2, 0) приведенного ниже рисунка.

Так как полученное решение нецелочисленное, то в соответствии с методом Гомори, к ограничениям задачи необходимо добавить еще одно ограничение, которое отсекает полученный план и не должно отсекать ни одного целочисленного решения задачи. Такое ограничение называют правильным отсечением. Его строят по наибольшей дробной части нецелочисленных базисных переменных. Наибольшая дробная часть - у переменной x₁. Если перейти от последней таблицы к соответствующим ей уравнениям, то получим следующее выражение для базисных переменных через свободные:

Правильное отсечение таково:

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

.

Если в этом неравенстве переменную x₃ выразить, используя полученное выше уравнение, через x₁, то получится следующее ограничение:

x₁ 6.

На рисунке оно отсекает от области допустимых планов часть, содержащую найденное нецелочисленное решение, и вместе с тем. Графически граница этой области представлена пунктирной линией L₃. Точка пересечения этой линии с координатной осью х₁ и дает искомое целочисленное решение.

В канонической форме правильное отсечение примет вид:

.

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

2)	f	x1	x2	x3	x4	x5	B
f-строка	1	0	1	2	0	0	26
	0	1	1/2	1/2	0	0	13/2
	0	0	5/2	3/2	1	0	57/2
	0	0	1/2	1/2	0	-1	1/2
3)	f	x1	x2	x3	x4	x5	B
f-строка	1	0	0	1	0	2	25
	0	1	0	0	0	1	6
	0	0	3	2	1	0	29
	0	0	1	1	0	-2	1

Так как в f-строке нет отрицательных элементов, то полученное решение X₃^T=(6 1 0 29 0) является оптимальным. Оно также удовлетворяет и условию целочисленности и, следовательно, значения переменных x₁=6, x₂=1 дают решение исходной задачи.

ОТВЕТ: Максимальное значение целевой функции f(x₁,x₂)=4x₁+x₂ при заданных ограничениях и целочисленных значениях переменных равно 25 и достигается при x₁=6, x₂=1.

ЗАДАЧА №2

Решить транспортную задачу, заданную таблицей.

Поставщики и их запасы	Потребители и потребительский спрос
	В1	В2	В3	В4
	95	65	65	65
А1	120	9	4	5	6
А2	70	2	3	6	11
А3	100	4	9	8	3

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

РЕШЕНИЕ

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

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

Потребности Запасы
		9		4		5		6
	- 95	25 +
		2		3		6		11
	+ *	40 -	30
		4		9		8		3
			35	65

При этом суммарная стоимость перевозок равна

.

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

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

,

,

,

Находим наибольшую положительную оценку .

Для найденной свободной клетки (3, 2) построим цикл пересчета:

(2, 1) -- (1, 1) -- (1, 2) -- (2, 2).

Производим перераспределение поставок вдоль цикла пересчета (на ), получаем второе базисное допустимое решение:

95	25					55	65
*	40					40

Потребности Запасы
		9		4		5		6
	55	65
		2		3		6		11
	- 40		30 +
		4		9		8		3
	+ *		35 -	65

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

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

,

,

,

Находим наибольшую положительную оценку .

Для найденной свободной клетки (3, 1) построим цикл пересчета:

(3, 1) -- (2, 1) -- (2, 3) -- (3, 3).

Производим перераспределение поставок вдоль цикла пересчета (на ), получаем третье базисное допустимое решение:

программирование перевозка гомори

40		30						5		65
*		35						35

Потребности Запасы
		9		4	+	5		6
	- 55	65
		2		3		6		11
	+ 5		65 -
		4		9		8		3
	35			65

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

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

,

,

,

Находим наибольшую положительную оценку .

Для найденной свободной клетки (1, 3) построим цикл пересчета:

(1, 3) -- (2, 3) -- (2, 1) -- (1, 3).

Производим перераспределение поставок вдоль цикла пересчета (на ), получаем третье базисное допустимое решение:

55	65	*			65				65	55
5		65						60		10

Потребности Запасы
		9		4		5		6
		65	55
		2		3		6		11
	60		10
		4		9		8		3
	35			65

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

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

,

,

,

Поскольку все оценки неположительны, базисное допустимое решение

является оптимальным.

При этом суммарная стоимость перевозок равна , это на 680 ед. меньше, чем в исходном варианте.

ЗАДАЧА №3

Решить задачу о распределении ресурсов методом динамического программирования. Составить оптимальный план распределения капиталовложений между четырьмя предприятиями, обеспечивающий максимальное увеличение выпуска продукции, при исходных данных относительно и , приведенных в таблице, а также с учетом того, что общий объем капиталовложений S=200 усл. ед.

Объем капиталовложений,	Прирост выпуска продукции в зависимости от объема капиталовложений
	предпр.1	предпр. 2	предпр. 3	предпр. 4
0	0	0	0	0
40	12	14	13	18
80	33	28	38	39
120	44	38	47	48
160	64	56	60	65
200	78	80	75	82

РЕШЕНИЕ

Таблица 1

	Объем капиталовложений, усл.ед.
№ предприятия	0	40	80	120	160	200
	Прирост выпуска продукции в зависимости от объема капиталовложений
1	0	12	33	44	64	78
2	0	14	28	38	56	80
3	0	13	38	47	60	75
4	0	18	39	48	65	82

Пусть х₁, х₂, х₃, х₄ - вложения соответственно первого, второго, третьего и четвертого предприятия, 0 х_i 200, i = 1,4. Обозначим f₁(x), f₂(x), f₃(x), f₄(x) - функции изменения прироста выпуска продукции первого, второго, третьего и четвертого предприятия при вложении в них х усл.ед. Этим функциям соответствуют строки 1, 2, 3, 4 в табл.1.

Определим максимум функции цели

F (х₁, х₂, х₃, х₄) = f₁(x) + f₂(x) + f₃(x) + f₄(x).

При этом на вложения х₁, х₂, х₃, х₄ наложены ограничения

х₁ + х₂ + х₃ + х₄ = А, усл.ед.

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

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

Выделим в нашей задаче 3 шага:

- А усл.ед.. вкладываются в первое, второе предприятия одновременно;

- А усл.ед. вкладываются в первое, второе, третье предприятия вместе;

- А усл.ед. вкладываются в четыре предприятия одновременно.

Обозначим: F_1,2 (А), F_1,2,3 (А), F_1,2,3,4 (А) - соответственно оптимальные распределения средств для первого, второго и третьего шагов.

Алгоритм метода динамического программирования состоит из двух этапов. На первом этапе выполняется условная оптимизация, заключающаяся в том, что для каждого из трех шагов находят условный оптимальный выигрыш F_1,2 (А), F_1,2,3 (А), F_1,2,3,4 (А) для . На втором этапе выполняется безусловная оптимизация. Используя результаты первого этапа, находят величины вложений в предприятия х₁, х₂, х₃, х₄, обеспечивающие максимальный прирост выпуска группы предприятий.

Первый этап включает следующие шаги:

1) Вычисление максимума критерия оптимизации для различных значений вложений х = 0, 40, 80, 120, 160, 200, которые используются только для предприятий 1 и 2. Расчет ведется по формуле

F_1,2 ( А ) = max [ f₁( x ) + f₂ ( A - x ) ]; 0 x 200; 0 A 200.

Результаты расчета представлены в табл.2.

Таблица 2

		х2 = А - х
х1	f1( x )	0	40	80	120	160	200
		f2( А - x )
		0	14	28	38	56	80
0	0	0	14	28	38	56	80
40	12	12	26	40	50	68
80	33	33	47	61	71
120	44	44	58	72
160	64	64	78
200	78	78

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

F₂ ( 0) = 0; F₂ ( 40) = max (12, 14) = 14; F₂ ( 80) = max ( 33, 26, 28) = 33; F₂ ( 120) = max ( 44, 47, 40, 38) = 47; F₂ ( 160) = max (64, 58, 61, 50, 56) =65; F₂ ( 200) = max ( 78, 78, 72, 71, 68, 80) =80.

2) Вычисление максимума критерия оптимизации для различных значений капиталовложений х = 0, 40, 80, 120, 160, 200, которые используются только для предприятий 1,2 и 3. Расчет ведется по формуле

F_1,2,3 ( А ) = max [ F_1,2( A ) + f₃ ( A - x ) ]; 0 x 200; 0 A 200.

Результаты расчетов занесем в табл.3, которая аналогична табл.2, только вместо f₁( x ) в ней указаны значения F₂ ( А ), а f₂ ( A - x ) заменена на f₃ ( A - x ).

Таблица 3

		х3 = А - х
A	F1,2(A)	0	40	80	120	160	200
		f3( А - x )
		0	13	38	47	60	75
0	0	0	13	38	47	60	75
40	14	14	27	52	61	74
80	33	33	46	71	80
120	47	47	60	85
160	64	64	104
200	80	80

Значения F_1,2,3 ( A ) будут следующими:

F_1,2,3 ( 0 ) = 0; F_1,2,3 ( 40 ) = 14; F_1,2,3 ( 80) = 38;

F_1,2,3 ( 120 ) = 52; F_1,2,3 ( 160 ) = 71; F_1,2,3 ( 200 ) = 104.

3) Вычисление максимума критерия оптимизации для различных значений капиталовложений х = 0, 40, 80, 120, 160, 200, которые используются для всех предприятий.

Расчет ведется по формуле

F_1,2,3,4 ( А ) = max [ F_1,2,3( A ) + f₄ ( A - x ) ]; 0 x 100; 0 A 100.

Результаты расчетов заносим в табл.4.

Таблица 4

		х4 = А - х
A	F1,2,3(А)	0	40	80	120	160	200
		f4( А - x )
		0	11	25	45	36	65
0	0	0	11	25	45	36	65
40	14	14	25	39	59	50
80	38	38	49	63	83
120	52	52	63	77
160	71	71	82
200	104	104

Значения F_1,2,3,4 ( А ) в результате расчета будут следующими:

F_1,2,3,4 ( 0 ) = 0; F_1,2,3,4 ( 40 ) = 14; F_1,2,3,4 ( 80 ) = 38;

F_1,2,3,4 ( 120 ) = 52; F_1,2,3,4 ( 160 ) = 71; F_1,2,3,4 ( 200 ) = 104

На этом первый этап решения задачи динамического программирования заканчивается.

Перейдем ко второму этапу решения задачи динамического программирования - безусловной оптимизации. На этом этапе используются табл. 4, 3, 2. Определим оптимальные капиталовложения в развитие предприятий для А = 0, 40, 80, 120, 160, 200. Для этого выполним следующие расчеты.

Пусть объем капиталовложений, выделенный на развитие предприятий, составляет А = 200 усл.ед.

Определим объем вложений в четвертое предприятие. Для этого используем табл. 4. Выберем на ней диагональ, соответствующую А = 200 - это значения 104, 82, 77, 83, 50, 65. Из этих чисел возьмем максимальное F_1,2,3,4 (200) = 104. Отмечаем столбец, в котором стоит эта величина. Далее определяем в отмеченном столбце объем вложений в четвертое предприятие х₄ = 0.

На развитие первого, второго и третьего предприятий остается

А = 200 - х₄ = 200 усл.ед.

Определим объем вложений, выделенные на развитие третьего предприятия.

Для этого используем табл. 3. Выберем в этой таблице диагональ, соответствующую А = 200 - это значения 80, 104, 85, 80, 74, 75. Отмечаем столбец, в котором стоит максимальная величина прироста выпуска F_1,2,3 ( 200 ) = 104. Определяем значение х₃ = 40 усл.ед. в отмеченном столбце.

На развитие первого и второго предприятия остается сумма

А = 200 - х₄ - х₃ = 160 усл.ед.

Определим объем капиталовложений на развитие второго предприятия. Используем для этого табл. 2. Выберем в таблице диагональ, соответствующую А = 160 - это значения 64, 58, 61, 50, 56. Отмечаем столбец с максимальной величиной производительности F_1,2 ( 160 ) = 64. Тогда в этом столбце х₂ =0.

Определим объем капиталовложений на развитие первого предприятия. На развитие первого предприятия средства выделяются в размере 160 усл.ед.

Таким образом, для вложений объемом А = 200 усл. ед. оптимальным является вложение в развитие третьего предприятия - 40 усл.ед. и первого - 160 усл.ед., во второе и четвертое предприятия средства не выделяются. При этом суммарная производительность четырех предприятий составит 104.

ЗАДАЧА №4

Рассмотрите сеть, заданную следующими условиями:

Номер дуги	Имя дуги	Начальный узел	Конечный узел	Расстояние
1	С21	2	1	1
2	С31	3	1	4
3	С41	4	1	4
4	С51	5	1	6
5	С64	6	4	3
6	С65	6	5	2
7	С72	7	2	8
8	С76	7	6	1
9	С43	4	3	1
10	С54	5	4	2
11	С84	8	4	4
12	С86	8	6	4
13	С87	8	7	1
14	С74	7	4	5

Найти кратчайшие маршруты из всех узлов в узел 1 и определить их длину.

РЕШЕНИЕ

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

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

1

Рисунок 1

Ясно, что длины кратчайших маршрутов из узла j в узел 1 и из узла 1 в узел j одинаковы (а последовательности узлов маршрутов взаимно обратны). Будем определять кратчайшие расстояния от узла 1 до каждого из узлов сети j (т.е. следовать против направления стрелок).

Введем следующие обозначения:

d_ij - расстояние между смежными узлами i и j (длина дуги C_ij).

u_j - кратчайшее расстояние между узлами 1 и j, u₁ = 0.

Общая формула для вычисления u_j имеет вид:



Кратчайшее расстояние u_j до узла j можно вычислить лишь после того, как определено кратчайшее расстояние до каждого предыдущего узла i, соединенного дугой с узлом j.

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

Этап 1: u₁=0.

Этап 2: u₂ = u₁+ d₁₂ = 0+1 = 1 (из 1),

u₃ = u₁+ d₁₃ = 0+4 = 4 (из 1),

u₄ = u₁+ d₁₄ = 0+4 = 4 (из 1),

u₅ = u₁+ d₁₅ = 0+6 = 6 (из 1).

Этап 3: u₇ =min{u₇+ u₁, u₅+ d₆₇, d₇₄+u₃+ d₄₃} = min{8+1, 5+4, 4+1+5}=9 (из 3).

Этап 4: u₆ =min{u₄+ d₆₄, u₅+ d₆₅} = min{4+3, 6+2}=2 (из 2).

Этап 5: u₈=min{u₇+ d₈₇, u₄+ d_84, u₆+ d₈₆} = min{9+1, 4+4, 7+4}=8 (из 3).

Найденные минимальные расстояния u_j указаны на графическом изображении сети. Проделанные выкладки позволяют сформулировать ответ.

Кратчайшие маршруты из каждого узла j сети в узел 1 и их длины u_j таковы:

2 1, u₂ = 1;

3 1, u₃ = 4;

4 1, u₄ = 4;

5 1, u₅ = 6;

6 4 1, u₆ = 7;

721, u₇ = 9, 741, u₇ = 9,

841, u₈ = 8.



СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Данциг Д. Линейное программирование, его обобщение и применение. - М.: Прогресс, 2005.

2. Замков ОО., Толстопятко А.В., Черемных Ю.Н. Математические методы в экономике. - М.: «ДИС», 2006.

3. Исследование операций в экономике: Учебное пособие для вузов (под ред. Проф. Н.Ш. Кремера). - М.: Банки и биржи, ЮНИТИ, 2007.

4. Конышева Л.К. Дискретная математика. - Издательство ГОУ ВПО «Российский государственный профессионально-педагогический университет». Екатеринбург, 2010.

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

...