Контрольная работа по курсу «Экономико-математическое моделирование»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НЕФТЕКАМСКИЙ ФИЛИАЛ

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО

ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БАШКИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

 

 

 

Экономико-математический факультет

 

Кафедра государственного управления и финансов

 

 

 

КОНТРОЛЬНАЯ РАБОТА

по курсу «Экономико-математическое моделирование»

 

 

 

 

 

                                                           

 

 

 

 

 

 

 

Научный руководитель:

      

 

 

 

 

Нефтекамск 2013

СОДЕРЖАНИЕ

 

	с
Задача №1.	3
Задача №2.	4
Задача №3.	7
Задача №4.	11
Задача №5.	19
Список используемой литературы	30

 

 

Задача №1.

Вариант  1

Молочный завод выпускает масло  двух  видов:  крестьянское (К) и бутербродное (Б).  Объем реализации масла К составляет  не  менее  70 % от общего  объема  реализации  продукции  обоих  видов.  Для производства  продукции К  и Б  используется молоко,  суточный  запас  которого  равен  120  кг.  Расход молока  на  килограмм масла К  равен  10  кг,  а  на килограмм масла Б – 7  кг,  цены  на масло К и Б – 60  и  45  рублей  соответственно.

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

 

Решение:

Искомой величиной в задаче является максимальный доход. Молочный завод выпускает два вида масла: крестьянское (К) и бутербродное (Б). Обьем продажи масла (К) не менее 70% от общего обьёма. Данные к задаче приведены в таблице.

x 1 – количество произведенного масла (К) , [кг.];

x2 – количество произведённого масла (Б), [кг.];

данные задачи в таблице:

 

	Масло (К)	Масло (Б)	Суточный запас, кг
Расход молока на 1 кг масла	10	7	120
Обьем реализации, %	70	30	100
Цена на 1 кг масла	60	45

 

Целевая функция:

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

Таким образом, целевая функция имеет вид:

,

Ограничения:

Возможные объемы реализации продукций ограничиваются следующими условиями:

· расход молока на 1 кг масла (К) равен 10 кг, а масла (Б) -7 кг;

·  объём реализации масла (К) не менее 70%  объёма реализации обоих видов.

 

Таким образом, математическая модель этой задачи имеет вид:

    ,

 

 

Задача №2.

Вариант – 1

Решить  задачу  линейного  программирования  графическим  методом.

Z(х)=х1+х2+30 min

Решение:

Необходимо найти минимальное значение целевой функции F = х1+х2+30 =>

min, при системе ограничений:

2x1+5x2≥12 (1)

2x1+x2≤6 (2)

x1+2x2≤0 (3)

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

 

Рисунок 1 – Область допустимых значений

 

Обозначим границы области многоугольника решений.

 

Рисунок 2 – Границы области многоугольника решений

 

Рассмотрим целевую функцию задачи F=X1X2+30 => min.  
Построим прямую, отвечающую значению функции F = 0: F = X1X2+30 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Рисунок 3 – Движение прямой

Нанесем равный масштаб.

 

Рисунок 4 – Равный масштаб

 

Область допустимых значений неограниченна.

 

Задача №3.

Вариант – 21

Решить задачу линейного программирования симплекс-методом.

 

Решение:

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. 
Определим минимальное значение целевой функции F(X) = - x1 - 4x2 - x3-7 при следующих условиях ограничений. 
При вычислениях значение Fc = -7 временно не учитываем. 
2x1 + 3x2 + 3x3=18 
x1 - 2x2 + x3 >= 2 
- x1 + 2x2 + x3 <= 4 
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 
2x1 + 3x2 + 3x3 + 0x4 + 0x5 = 18 
1x1-2x2 + 1x3-1x4 + 0x5 = 2 
-1x1 + 2x2 + 1x3 + 0x4 + 1x5 = 4 
Введем искусственные переменные x: в 1-м равенстве вводим переменную x6; во 2-м равенстве вводим переменную x7;  
2x1 + 3x2 + 3x3 + 0x4 + 0x5 + 1x6 + 0x7 = 18 
1x1-2x2 + 1x3-1x4 + 0x5 + 0x6 + 1x7 = 2 
-1x1 + 2x2 + 1x3 + 0x4 + 1x5 + 0x6 + 0x7 = 4 
Для постановки задачи на минимум целевую функцию запишем так: 
F(X) = -1x1-4x2-1x3+Mx4+Mx5+Mx6+Mx7 → min 
Из уравнений выражаем искусственные переменные: 
x6 = 18-2x1-3x2-3x3 
x7 = 2-x1+2x2-x3+x4 
которые подставим в целевую функцию: 
F(X) = (-1-3M)x1+(-4-M)x2+(-1-4M)x3+(M)x4+(20M) → min 
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

2	3	3	0	0	1	0
1	-2	1	-1	0	0	1
-1	2	1	0	1	0	0

 
Решим систему уравнений относительно базисных переменных: 
x6, x7, x5, 
Полагая, что свободные переменные равны 0, получим первый опорный план: 
X1 = (0,0,0,0,4,18,2)

Базис	B	x1	x2	x3	x4	x5	x6	x7
x6	18	2	3	3	0	0	1	0
x7	2	1	-2	1	-1	0	0	1
x5	4	-1	2	1	0	1	0	0
F(X0)	20M	1+3M	4+M	1+4M	-M	0	0	0

 
Переходим к основному алгоритму симплекс-метода. 
Итерация №0. 
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x3, так 2-ая строка является ведущей. 
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x6	18	2	3	3	0	0	1	0	6
x7	2	1	-2	1	-1	0	0	1	2
x5	4	-1	2	1	0	1	0	0	4
F(X1)	20M	1+3M	4+M	1+4M	-M	0	0	0	0

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x6	12	-1	9	0	3	0	1	-3
x3	2	1	-2	1	-1	0	0	1
x5	2	-2	4	0	1	1	0	-1
F(X1)	-2+12M	-M	6+9M	0	1+3M	0	0	-1-4M

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x6	12	-1	9	0	3	0	1	-3	11/3
x3	2	1	-2	1	-1	0	0	1	-
x5	2	-2	4	0	1	1	0	-1
F(X2)	-2+12M	-M	6+9M	0	1+3M	0	0	-1-4M	0

 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x6	71/2	31/2	0	0	3/4	-21/4	1	-3/4
x3	3	0	0	1	-1/2	1/2	0	1/2
x2	1/2	-1/2	1	0	1/4	1/4	0	-1/4
F(X2)	-5+71/2M	3+31/2M	0	0	-1/2+3/4M	-11/2-21/4M	0	1/2-13/4M

Итерация №2. 
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент, 1-ая строка является ведущей. 
Разрешающий элемент равен (31/2) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x6	71/2		0	0	3/4	-21/4	1	-3/4
x3	3	0	0	1	-1/2	1/2	0	1/2	-
x2	1/2	-1/2	1	0	1/4	1/4	0	-1/4	-
F(X3)	-5+71/2M	3+31/2M	0	0	-1/2+3/4M	-11/2-21/4M	0	1/2-13/4M	0

 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x1	21/7	1	0	0	3/14	-9/14	2/7	-3/14
x3	3	0	0	1	-1/2	1/2	0	1/2
x2	14/7	0	1	0	5/14	-1/14	1/7	-5/14
F(X3)	-113/7	0	0	0	-11/7	3/7	-6/7-M	11/7-M

Итерация №3. 
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x5, так как это наибольший коэффициент . 
Вычислим значения Di по строкам как частное от деления: bi / ai5 
и из них выберем наименьшее, далее 2-ая строка является ведущей. 
Разрешающий элемент равен (1/2) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x1	21/7	1	0	0	3/14	-9/14	2/7	-3/14	-
x3	3	0	0	1	-1/2		0	1/2	6
x2	14/7	0	1	0	5/14	-1/14	1/7	-5/14	-
F(X4)	-113/7	0	0	0	-11/7		-6/7-M	11/7-M	0

 
Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x1	6	1	0	12/7	-3/7	0	2/7	3/7
x5	6	0	0	2	-1	1	0	1
x2	2	0	1	1/7	2/7	0	1/7	-2/7
F(X4)	-14	0	0	-6/7	-5/7	0	-6/7-M	5/7-M

 
Конец итераций: индексная строка не содержит положительных элементов - найден оптимальный план 
Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x1	6	1	0	12/7	-3/7	0	2/7	3/7
x5	6	0	0	2	-1	1	0	1
x2	2	0	1	1/7	2/7	0	1/7	-2/7
F(X5)	-14	0	0	-6/7	-5/7	0	-6/7-M	5/7-M

 
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. 
Оптимальный план можно записать так: 
x1 = 6 
x2 = 2 
F(X) = -1•6 -4•2 -7 = -21

Задача №4.

Вариант  1

 

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

Составьте  план  перевозок продуктов  из n  пунктов  отправления  (Аi)  в  m  пункты  назначения  (Bj).  План  должен  обеспечить  минимальные  транспортные  издержки  и  полностью  удовлетворить  спрос  потребителей  на продукты.  Запас  (аi),  потребность  (bj)  и  стоимость  перевозки  1  единицы измерения  продуктов  (сij)  приведены  в  табл. 1-10.

 

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

Пункты отправления (Аi)	Пункты потребления (Bj)					Запас (аi)
	В1	В2	В3	В4	В5
	Стоимость перевозки 1 ед изм продуктов (сij)
А1	7	3	5	4	2	40
А2	6	2	3	1	7	150
А3	3	5	2	6	4	100
Потребность (bj)	20	80	90	60	40

 

Решение:

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	5	Запасы
1	7	3	5	4	2	40
2	6	2	3	1	7	150
3	3	5	2	6	4	100
Потребности	20	80	90	60	40

 Проверим необходимое и достаточное  условие разрешимости задачи.

 ∑a = 40 + 150 + 100 = 290

 ∑b = 20 + 80 + 90 + 60 + 40 = 290

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

	1	2	3	4	5	Запасы
1	7	3	5	4	2	40
2	6	2	3	1	7	150
3	3	5	2	6	4	100
Потребности	20	80	90	60	40

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

	1	2	3	4	5	Запасы
1	7	3	5	4	2[40]	40
2	6[10]	2[80]	3	1[60]	7	150
3	3[10]	5	2[90]	6	4	100
Потребности	20	80	90	60	40

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

 Строим новый план.

 Значение целевой функции  для этого опорного плана равно:

F(x) = 2*40 + 6*10 + 2*80 + 1*60 + 3*10 + 2*90 = 570

 

 

	1	2	3	4	5	Запасы
1	7	3[40]	5	4	2	40
2	6[10]	2[40]	3	1[60]	7[40]	150
3	3[10]	5	2[90]	6	4	100
Потребности	20	80	90	60	40

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

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

 Значение целевой функции  для этого опорного плана равно:

F(x) = 3*40 + 6*10 + 2*40 + 1*60 + 7*40 + 3*10 + 2*90  = 810

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

	v1=7	v2=3	v3=6	v4=2	v5=8
u1=0	7	3[40]	5	4	2
u2=-1	6[10]	2[40]	3	1[60]	7[40]
u3=-4	3[10]	5	2[90]	6	4