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

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

Базис	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