Моделирование и прогнозирование экономических процессов

6x1 + 3x2 ≤ 36

3x1 + 2x2 ≤ 21

7x1 + 4x2 -> max

 

 

 

 

Задача №14

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

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

6x1 + 3x2≤36

3x1 + 2x2≤21

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

6x1 + 3x2 + 1x3 + 0x4 = 36

3x1 + 2x2 + 0x3 + 1x4 = 21

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

 

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

x3, x4,

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

X1 = (0,0,36,21)

Базис	B	x1	x2	x3	x4
x3	36	6	3	1	0
x4	21	3	2	0	1
F(X0)	0	-7	-4	0	0

 

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

Итерация №0.

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

...........................

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

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

Базис	B	x1	x2	x3	x4	min
x3	36	6	3	1	0	6
x4	21	3	2	0	1	7
F(X1)	0	-7	-4	0	0	0

 

 

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

.........................

Итерация №1.

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2

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

...........................

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

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

Базис	B	x1	x2	x3	x4	min
x1	6	1	1/2	1/6	0	12
x4	3	0	1/2	-1/2	1	6
F(X2)	42	0	-1/2	11/6	0	0

 

 

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

.........................

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

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

Базис	B	x1	x2	x3	x4
x1	3	1	0	2/3	-1
x2	6	0	1	-1	2
F(X3)	45	0	0	2/3	1

 

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

x1 = 3

x2 = 6

F(X) = 7•3 + 4•6 = 45

Задача №15

 

Пункты	Б1	Б2	Б3	Б4	Запасы
А1	1	2	3	1	100
А2	2	3	4	6	200
А3	3	4	7	12	300
Потребности	100	100	300	300

 

 

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

F = ∑∑cijxij,    (1)

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

∑xij = ai,  i = 1,2,…, m,   (2)

∑xij = bj,  j = 1,2,…, n,   (3)

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

	1	2	3	4	Запасы
1	1	2	3	1	100
2	2	3	4	6	200
3	3	4	7	12	300
Потребности	100	100	300	300

 

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

∑a = 100 + 200 + 300 = 600

∑b = 100 + 100 + 300 + 300 = 800

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

	1	2	3	4	Запасы
1	1	2	3	1	100
2	2	3	4	6	200
3	3	4	7	12	300
4	0	0	0	0	200
Потребности	100	100	300	300

 

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

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

	1	2	3	4	Запасы
1	1[100]	2	3	1	100
2	2	3[100]	4[100]	6	200
3	3	4	7[200]	12[100]	300
4	0	0	0	0[200]	200
Потребности	100	100	300	300

 

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

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

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

...........................

	1	2	3	4	Запасы
1	1	2[100]	3	1	100
2	2[100]	3	4[100]	6	200
3	3	4	7[200]	12[100]	300
4	0	0	0	0[200]	200
Потребности	100	100	300	300

 

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

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

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

...........................

	1	2	3	4	Запасы
1	1	2	3[100]	1	100
2	2[100]	3[100]	4	6	200
3	3	4	7[200]	12[100]	300
4	0	0	0	0[200]	200
Потребности	100	100	300	300

 

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

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

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

...........................

	1	2	3	4	Запасы
1	1	2	3	1[100]	100
2	2[100]	3[100]	4	6	200
3	3	4	7[300]	12	300
4	0	0	0	0[200]	200
Потребности	100	100	300	300