Исследования операций в экономике методами линейного программирования

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

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

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

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

«Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых»

(ВлГУ)

Кафедра «Функциональный Анализ и его Приложения»

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

Исследования операций в экономике методами линейного программирования

Выполнила: Сапожкова Д. В.

Группа: ЗЭКсд-112

Принял: Беспалов М.С.

Владимир - 2013г.



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

при условиях

.

Решение

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

Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).

Определим максимальное значение целевой функции F(X) = x₁ + 3x₃ при следующих условиях-ограничений.

x₁ + x₂ + x₃=11

2x₁ - 3x₂ - x₄=1

x₁ - x₂ - x₅=3

Введем искусственные переменные x: в 1-м равенстве вводим переменную x₆; в 2-м равенстве вводим переменную x₇; в 3-м равенстве вводим переменную x₈;

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

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

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

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

F(X) = x₁+3x₃ - Mx₆ - Mx₇ - Mx₈ > max

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

x₆ = 11-x₁-x₂-x₃

x₇ = 1-2x₁+3x₂+x₄

x₈ = 3-x₁+x₂+x₅

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

F(X) = (1+4M)x₁+(-3M)x₂+(3+M)x₃+(-M)x₄+(-M)x₅+(-15M) > max

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

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

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

Полагая, что свободные переменные равны 0, получим первый опорный план: -X1 = (0,0,0,0,0,11,1,3)

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



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

Итерация №0.

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

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

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

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x6	11	1	1	1	0	0	1	0	0	11
x7	1	2	-3	0	-1	0	0	1	0	1/2
x8	3	1	-1	0	0	-1	0	0	1	3
F(X1)	-15M	-1-4M	3M	-3-M	M	M	0	0	0	0

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	101/2	0	21/2	1	1/2	0	1	-1/2	0
x1	1/2	1	-11/2	0	-1/2	0	0	1/2	0
x8	21/2	0	1/2	0	1/2	-1	0	-1/2	1
F(X1)	1/2-13M	0	-11/2-3M	-3-M	-1/2-M	M	0	1/2+2M	0

Итерация №1.

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

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

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

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

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

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x2	41/5	0	1	2/5	1/5	0	2/5	-1/5	0
x1	64/5	1	0	3/5	-1/5	0	3/5	1/5	0
x8	2/5	0	0	-1/5	2/5	-1	-1/5	-2/5	1
F(X2)	64/5-2/5M	0	0	-22/5+M	-1/5-2/5M	M	3/5+11/5M	1/5+12/5M	0

Итерация №2.

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

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

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

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x2	41/5	0	1	2/5	1/5	0	2/5	-1/5	0	21
x1	64/5	1	0	3/5	-1/5	0	3/5	1/5	0	-
x8	2/5	0	0	-1/5	2/5	-1	-1/5	-2/5	1	1
F(X3)	64/5-2/5M	0	0	-22/5+M	-1/5-2/5M	M	3/5+11/5M	1/5+12/5M	0	0

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x2	4	0	1	1/2	0	1/2	1/2	0	-1/2
x1	7	1	0	1/2	0	-1/2	1/2	0	1/2
x4	1	0	0	-1/2	1	-21/2	-1/2	-1	21/2
F(X3)	7	0	0	-21/2	0	-1/2	1/2+M	M	1/2+M

Итерация №3.

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

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

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

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x2	4	0	1	1/2	0	1/2	1/2	0	-1/2	8
x1	7	1	0	1/2	0	-1/2	1/2	0	1/2	14
x4	1	0	0	-1/2	1	-21/2	-1/2	-1	21/2	-
F(X4)	7	0	0	-21/2	0	-1/2	1/2+M	M	1/2+M	0

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	8	0	2	1	0	1	1	0	-1
x1	3	1	-1	0	0	-1	0	0	1
x4	5	0	1	0	1	-2	0	-1	2
F(X4)	27	0	5	0	0	2	3+M	M	-2+M

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

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	8	0	2	1	0	1	1	0	-1
x1	3	1	-1	0	0	-1	0	0	1
x4	5	0	1	0	1	-2	0	-1	2
F(X5)	27	0	5	0	0	2	3+M	M	-2+M

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

x₃ = 8

x₁ = 3

x₄ = 5

x₂ = 0

x₅ = 0

F(X) = 3*8 + 1*3 + 0*5 = 27

Задача 2. Сформулировать двойственную задачу к задаче 1 и решить ее

Решение

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

y₁ + 2y₂ - y₃?1

y₁ - 3y₂ + y₃?0

y₁?3

- y₂?0

y₃?0

11y₁ + y₂ - 3y₃ > min

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

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

Из теоремы двойственности следует, что Y = C*A^-1.

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

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда

Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 3

y₂ = 0

y₃ = 2

Z(Y) = 11*3+1*0+-3*2 = 27

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

при условиях

Решение

Запишем задачу в виде основной задачи линейного программирования

Решим задачу симплексным методом

- базисные переменные

- свободные переменные

начальное решение (0; 0; 0; 20; 30).

Б	З	х1	х2	х3	х4	х5
х4	20	2	5	4	1	0
х5	30	4	3	5	0	1
f	0	-6	-2	-3	0	0

Поскольку в f-ой строке есть отрицательные элементы, то начальное решение не оптимально. Выбираем первый столбец в качестве ведущего. х₁ перейдёт в базис - покинет базис.

Б	З	х1	х2	х3	х4	х5
х4	5	0	7/2	3/2	1	-1/2
х1	15/2	1	3/4	5/4	0	1/4
f	45	0	5/2	9/2	0	3/2

Поскольку в f-ой строке нет отрицательных элементов, то решение оптимально.

Получаем следующий план:

z=x₃ = 0

x=x₁ = 7.5

y=x₂ = 0

f = 6*7.5 + 2*0 + 3*0 = 45

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

Указание. Начальный план выбираем по методу северо-западного угла или минимальной стоимости. Оптимизацию следует проводить методом потенциалов.

	В1	В2	В3	В4	запасы
А1	5	3	2	3	100
А2	3	5	4	3	200
А3	4	2	3	7	150
А4	8	6	7	2	150
потребности	170	80	140	190

Решение

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

F = ??c_ijx_ij, (1)

при условиях:

?x_ij = a_i, i = 1,2,…, m, (2)

?x_ij = b_j, j = 1,2,…, n, (3)

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

	1	2	3	4	Запасы
1	5	3	2	3	100
2	3	5	4	3	200
3	4	2	3	7	150
4	8	6	7	2	150
Потребности	170	80	140	190

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

?a = 100 + 200 + 150 + 150 = 600

?b = 170 + 80 + 140 + 190 = 580

?a ??b Задача является открытой.

Вводим фиктивного потребителя B5 с потребностью 20 ед.

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

	1	2	3	4	5	Запасы
1	5	3	2	3	0	100
2	3	5	4	3	0	200
3	4	2	3	7	0	150
4	8	6	7	2	0	150
Потребности	170	80	140	190	20



Этап I. Поиск первого опорного плана.

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

	1	2	3	4	5	Запасы
1	5	3	2[100]	3	0	100
2	3[170]	5	4	3[30]	0	200
3	4	2[80]	3[40]	7[10]	0[20]	150
4	8	6	7	2[150]	0	150
Потребности	170	80	140	190	20

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

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

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

Этап II. Улучшение опорного плана.

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

	v1=6	v2=1	v3=2	v4=6	v5=-1
u1=0	5	3	2[100]	3	0
u2=-3	3[170]	5	4	3[30]	0
u3=1	4	2[80]	3[40]	7[10]	0[20]
u4=-4	8	6	7	2[150]	0

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

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

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

	1	2	3	4	5	Запасы
1	5	3	2[100][-]	3[+]	0	100
2	3[170]	5	4	3[30]	0	200
3	4	2[80]	3[40][+]	7[10][-]	0[20]	150
4	8	6	7	2[150]	0	150
Потребности	170	80	140	190	20

Цикл приведен в таблице (1,4; 1,3; 3,3; 3,4;).

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

	1	2	3	4	5	Запасы
1	5	3	2[90]	3[10]	0	100
2	3[170]	5	4	3[30]	0	200
3	4	2[80]	3[50]	7	0[20]	150
4	8	6	7	2[150]	0	150
Потребности	170	80	140	190	20

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

	v1=3	v2=1	v3=2	v4=3	v5=-1
u1=0	5	3	2[90]	3[10]	0
u2=0	3[170]	5	4	3[30]	0
u3=1	4	2[80]	3[50]	7	0[20]
u4=-1	8	6	7	2[150]	0

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

	В1	В2	В3	В4
А1			90	10
А2	170			30
А3		80	50
А4				150

Минимальные затраты составят:

экономический линейное программирование симплексный

F(x) = 2*90 + 3*10 + 3*170 + 3*30 + 2*80 + 3*50 + 2*150 = 1420

Задача 5. Оптимальное поэтапное распределение средств между предприятиями в течении планового периода

Руководство фирмы, имеющей договор о сотрудничестве с тремя малыми предприятия, на плановый годовой период выделила для них оборотные средства в объеме 100000 у. е. Для каждого предприятия известны функции поквартального дохода и поквартального остатка оборотных средств в зависимости от выделенной на квартал суммы x. В начале квартала средства распределяются полностью между тремя предприятиями (из этих вложенных средств и вычисляется доход), а по окончанию квартала остатки средств аккумулируются у руководства фирмы и снова распределяются полностью между предприятиями. Составить план поквартального распределения средств на год (4 квартала), позволяющего достичь максимальный общий доход за год.

Решение

Решаем задачу с помощью модуля «Поиск решения» MS Excel.

Заполняем исходную таблицу следующим образом.

	A	B	C	D	E	F	G
1		x1	x2	x3			Средства на начало периода
2	1 квартал	0	0	0	0	=	100000
3	доход	1,2	1,5	2	0
4	остатки	0,7	0,6	0,1	0
5	2 квартал	0	0	0	0	=	0
6	доход	1,2	1,5	2	0
7	остатки	0,7	0,6	0,1	0
8	3 квартал	0	0	0	0	=	0
9	доход	1,2	1,5	2	0
10	остатки	0,7	0,6	0,1	0
11	4 квартал	0	0	0	0	=	0
12	доход	1,2	1,5	2	0
13	остатки	0,7	0,6	0,1	0
14	Конец года						0

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

	x1	x2	x3			Средства на начало периода
1 квартал	0	0	0	=СУММ(B2:D2)	=	100000
доход	1,2	1,5	2	=СУММПРОИЗВ($B$2:$D$2;B3:D3)
остатки	0,7	0,6	0,1	=СУММПРОИЗВ($B$2:$D$2;B4:D4)
2 квартал	0	0	0	=СУММ(B5:D5)	=	=E3+E4
доход	1,2	1,5	2	=СУММПРОИЗВ($B$5:$D$5;B6:D6)
остатки	0,7	0,6	0,1	=СУММПРОИЗВ($B$5:$D$5;B7:D7)
3 квартал	0	0	0	=СУММ(B8:D8)	=	=E6+E5
доход	1,2	1,5	2	=СУММПРОИЗВ($B$8:$D$8;B9:D9)
остатки	0,7	0,6	0,1	=СУММПРОИЗВ($B$8:$D$8;B10:D10)
4 квартал	0	0	0	=СУММ(B11:D11)	=	=E9+E10
доход	1,2	1,5	2	=СУММПРОИЗВ($B$11:$D$11;B12:D12)
остатки	0,7	0,6	0,1	=СУММПРОИЗВ($B$11:$D$11;B13:D13)
Конец года						=E12+E13

Вызываем «поиск решения»

Получаем следующий результат

	x1	x2	x3			Средства на начало периода
1 квартал	0	100000	0	100000	=	100000
доход	1,2	1,5	2	150000
остатки	0,7	0,6	0,1	60000
2 квартал	0	0	210000	210000	=	210000
доход	1,2	1,5	2	420000
остатки	0,7	0,6	0,1	21000
3 квартал	0	630000	0	630000	=	630000
доход	1,2	1,5	2	945000
остатки	0,7	0,6	0,1	378000
4 квартал	0	1323000	0	1323000	=	1323000
доход	1,2	1,5	2	1984500
остатки	0,7	0,6	0,1	793800
Конец года						2778300

Необходимо все день в 1 квартале направить 2-му предприятию, во втором квартале -- 3-му предприятию, в третьем квартале -- 2-му предприятию, в четвертом квартале -- 2-му предприятию. Суммарный доход на конец года составит 2778300 у.е.

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