Шурко Введение в системный анализ

11

L=7x1+5x2 max

2x1+3x2 + x3=19

2x1+ x2 + x4=13

3x2 + x5=15

3x1 + x6=18

Решение 1. Найдем ранг матрицы системы уравнений;

	2		3	1	0	0	0
		2	1	0	1	0
A =							0
		0	3	0	01	1	.
							0
			0	0	0	0
	3						1

Напомним некоторые определения:

1.Определитель R-го порядка, составленный из элементов матрицы,

расположенных на пересечении выделенных R произвольных строк и R

произвольных столбцов, называется минором R-го порядка матрицы.

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

отличного от нуля.

Минор 4-го порядка: (минор максимального порядка)

1	0	0	0
0	1	0	0	=4 0
0	0	1	0
0	0	0	1

Решение2.Найдем ранг расширенной матрицы:

	2		3	1	0	0	0	19
		2	1	0	1	0	0
A =								13
		0	3	0	0	1	0
								15

3 0 0 0 0 1 18

r(A)=4 - по той же причине.

12

Т.к. r(A)=r(A) следовательно:

1)система уравнений совместна

2)4 базисных переменных можно выразить через 2 свободных, т.е.

		х3=19-2х1-3х2
		х4=13-2х1-х2
		х5=15-3х2
		х6=18-3х1
х1,х2	-	свободные переменные,
х3,х4,х5,х6	-	базисные переменные.
		L - 7x1 - 5x2 = 0.

Имеем исходную таблицу 1.

Таблица 1.

Базис.п	Своб.ч.	X1	X2	X3	X4	X5	X6
X3	19	2	3	1	0	0	0
X4	13	2	1	0	1	0	0
X5	15	0	3	0	0	1	0
X6	18	3	0	0	0	0	1
L	0	-7	-5	0	0	0	0

Следуя 1 шагу можем выбрать 2 разрешающих столбца: X1 и X2 с оценками соответственно -7 и -5.

Возьмем, например, столбец X2. В нем имеется 3 положительных элемента: 3, 1, 3.

Для того, чтобы, следуя 2-му шагу, выбрать разрешающую строку,

разделим на числа 3, 1, 3 соответствующие свободные члены: 19/3, 13/1, 15/3.

Из полученных частных наименьшее - 15/3.

Следовательно, разрешающая, строка - X5.

Разрешающие строку и столбец выделяем стрелками. В базис введем переменную X2 и выведем переменную X5.

13

Следуя 3-му шагу, пересчитаем элементы разрешающей строки X5:

X5 5 0 1 0 0 1/3 0

Следуя 4-му шагу, вычисляем элементы всех остальных строк:

1) строка Х3: 19-5*3=4

2-0*3=2

3-1*3=0

1-0*3=1

0-0*3=0

0-1/3*3=-1

0-0*3=0

X3 4 2 0 1 0 -1 0

2) строка X4: 13-5*1=8

2-0*1=2

1-0*1=0

0-0*1=0

1-0*1=1

0-1/3*1=-1/3

0-0*1=0

X4 8 2 0 0 1 -1/3 0

3) строка Х6: 18-5*0=18

3-0*0=3

0-1*0=0

0-0*0=0

0-0*0=0

0-1/3*0=0

1-0*0=1

X6

18

3

0

0

0

0

1

4) строка L: 0-5*(-5)=25 -7-0*(-5)=-7 -5-1*(-5)=0 0-0*(-5)=0 0-1/3*(-5)=5/3 0-0*(-5)=0

14

L 25 -7 0 0 0 5/3 0

Новые базисные переменные: X3,X4,X2,X6.

Первая итерация завершена.

Получим таблицу 2.

Б.п.	С.ч.	X1	X2	X3	X4	X5	X6
X3	4	2	0	1	0	-1	0
X4	8	2	0	0	1	-1/3	0
X5	5	0	1	0	0	1/3	0
X6	18	3	0	0	0	0	1
L	25	-7	0	0	0	5/3	0

Проделаем все четыре шага применительно к таблице 2.
1 шаг: разрешающий столбец Х1.
2 шаг: 4/2, 8/2, 18/3			-разрешающая строка Х3. В базис введем переменную
Х1 и выведем переменную Х3.
3 шаг: пересчитаем элементы строки Х3:
	X3	2	1		0	1/2	0	-1/2	0

4 шаг: вычисляем элементы всех остальных строк:

1) строка Х4

8-2*2=4

2-1*2=0

0-0*2=0

0-1/2*2=-1

1-0*2=1

-1/3-(-1/2)*2=2/3

0-0*2=0

X4

4

0

0

-1

1

2/3

0

15

2)строка Х2. Так как разрешающий элемент в этой строке равен 0, то она не изменяется, строка Х6.

18- 2*3=12

3-1*3=0

0-0*3=0

0-1/2*3=-3/2

0-0*3=0

0-(-1/2)*3=3/2

1-0*3=1

X6

12

0

0

-3/2

0

3/2

1

Строка L : 25-2*(-7)=39 -7-1*(-7)=0 0-0*(-7)=0 0-1/2*(7)=7/2 0-0*(-7)=0 5/3-7/2=-11/6 0-0*(-7)=0

L	39	0	0	7/2	0	-11/6	0

Новые базисные переменные Х1, Х2, Х6.Завершена 2-я итерация.

Получим таблицу 3.

Б.п	С.ч.	X1	X2	X3	X4	X5	X6
X1	2	1	0	1/2	0	-1/2	0
X4	4	0	0	-1	1	2/3	0
X2	5	0	1	0	0	1/3	0
X6	12	0	0	-3/2	0	3/2	1
L	39	0	0	7/2	0	-11/6	0

Проделаем все 4 шага применительно к таблице 3.

1-й шаг: разрешающий столбец - Х5.

16

2-й шаг: находим разрешающую строку.

4*3/2=6, 5*3=15, 12*2/3=8 -разрешающая строка -Х4.

В базис введем переменную Х5 и выведем переменную Х4: 3-й шаг: пересчитываем элементы строки Х4:

X4

6

0

0

-3/2

3/2

1

0

4-й шаг: вычисляем элементы всех остальных строк.

1) строка Х1.

2-6*(-1/2)=5

1-0*(-1/2)=1

0-0*(-1/2)=0

1/2-(-3/2)*-(1/2)=-1/4

0-3/2*(-1/2)*1=3/4

(-1/2)-(-1/2)*1=0

0-0*(-1/2)=0

X1

5

1

0

-1/4

3/4

0

0

2) строка Х2.

5-6*(1/3)=3

0-0*(1/3)=0

1-0*1/3=1

0-(-3/2)*1/3=1/2

0-3/2*1/3=-1/2

1/3-1*1/3=0

0-0*1/3=0

X2

3

0

1

1/2

-1/2

0

0

3) строка Х6.

12-6*3/2=3

0-0*3/2=0

0-0*3/2=0

-3/2-(-3/2)*3/2=3/4 0-3/2*3/2=-9/4 3/2-1*3/2=0 1-0*3/2=1

17

X6

3

0

0

3/4

-9/4

0

1

4) строка L. 39-6*(-11/6)=50

0-0*(-11/6)=0

0-0*(-11/6)=0 7/2-(-3/2)*(-11/6)=3/4 0-3/2*(-11/6)=11/4 -11/6-1(-11/6)=0 0-0*(-11/6)=0

L	50	0	0	3/4	11/4	0	0

Новые базисные переменные: Х1, Х5, Х2, Х6.

Завершена 3-я итерация.

Получим таблицу 4.

	Б.п	С.ч.	X1	X2	X3		X4	X5	X6
	X1	5	1	0	-1/4		3/4	0	0
	X5	6	0	0	-3/2		3/2	1	0
	X2	3	0	1	1/2		-1/2	0	0
	X6	3	0	0	3/4		-9/4	0	1
	L	50	0	0	3/4		11/4	0	0
Поскольку все оценки неотрицательные,							то мы получим		оптимальный

план:

Х1=5, Х2=3, Х3=0, Х4=0, Х5=6, Х6=3

Lmax =50

Замечание. Если стоит задача минимизации целевой функции n

L= CiXi + C0 min

i=1

18

при соответствующих линейных ограничениях, то заменой L1(x) =-L(x) она сводится к максимизации новой целевой функции L1(x) при тех же линейных ограничениях.

Транспортная задача

Транспортная задача является одной из самых распространенных задач линейного программирования.

Имеется m предприятий А1,А2,...,Аm, производящих один и тот же продукт в количествах, равных соответственно а1,а2,...,аm. Есть и n потребителей этого продукта, находящихся в пунктах В1,В2,...,Вn, причем потребности их известны и равны b1,b2,...,bn. Предполагается, что суммарный объем потребления равен суммарному объему выпуска всех предприятий. Перевозка продукта от i-го предприятия к j-му потребителю ведет к затратам и составляет Сij. Нужно определить наилучший план перевозок.

Математическая модель транспортной задачи выглядит следующим образом: Хij- количество продукта, перевозимого с i-го предприятия к j- му потребителю.

1) Хij 0, i=1,2,...,m; j=1,2,...,n - перевозимые количества продуктов не могут быть отрицательными.

m

2)SXij=bj, j=1,2,...,n -каждый потребитель должен получить ровно столько, i=1

сколько ему потребуется. n

3)SXij=ai, i=1,2,...,m -с каждого предприятия продукт должен вывозиться

j=1	полностью, т.к. производится столько же, сколько и
	и потребляется.

19

L - суммарные затраты на перевозку: m n

L=S S cij*xij i=1 j=1 L min.

Транспортная задача представляет собой задачу ЛП с (m*n) переменными и

(m+n) ограничениями-равенствами.

Матрицу переменных

Х=(хij, i=1,..., m, j=1,..., n)

называют планом перевозок, а переменные xij - перевозками. План Хорт, при котором целевая функция минимальна, называют оптимальным планом.

Матрица коэффициентов целевой функции С=(сij,i=1,...,m,j=1,...,n) называется

матрицей транспортных издержек.

Для разрешимости транспортной задачи необходимо и достаточно, чтобы

выполнялось балансовое соотношение:
			m	n
			Sаi = Sbj
			i=1	j=1
т.е., чтобы объем производства был равен объему потребления.
	Существует ряд практических задач, в которых условие баланса не
выполняется, такие задачи называются открытыми. Возможны два случая:
m	n	m	n
1) Sai < Sbj		2) S ai > S bj
i=1	j=1	i=1	j=1
В первом случае вводят фиктивного поставщика с объемом производства
			n	m
			S bj - S ai ,
			j=1	i=1,

во втором случае - фиктивного потребителя с потребностью

20

m n

Sai - Sbj, i=1 j=1

и транспортными издержками, равными нулю.

Опорным планом транспортной задачи называют любое ее допустимое базисное решение.

Методы нахождения начальных опорных планов рассмотрим на примере следующей транспортной задачи.

1. МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

Заполнение таблицы начинается с левого верхнего элемента, что и обусловило название метода.

Объемы				Запросы потребителей
произ-ва	41		49		53		57
63		30		24		20		22
		41
95		12		14		8		10
				27		53		15
42		16		18		16		17
								42

Сравним a1=63 и b1=41, выбираем меньшее из них и записываем в таблицу.

Переходим ко второму столбцу. Сравнивая a1 =63-41=22 и b2=49, выбираем меньшее из них и записываем в таблицу, и т.д.