Методы решения систем линейных уравнений

 

Второй цикл:

Ц₂ = (2, 5) – (1, 5) – (1, 4) – (3, 4) – (3, 2) – (2, 2)

k₂γ₂ = -γ₂

k₂ = 75 ед.

Пересчитаем транспортную таблицу  с учетом приведенного цикла.

 

Таблица 4. Второй цикл

Пункт отправления	В1		В2		В3		В4		В5		Запасы, аi (тонн)
А1	-	14	-	8	-	17	85	5	35	3	120
А2	-	21	-	10	105	7	-	11	75	6	180
А3	70	3	120	5	-	8	40	4	-	9	230
Потребности, bj (тонн)	70		120		105		125		110		530

 

Проверяем оптимальность  найденного решения Х₂. Для этого вычислим потенциалы. В каждой занятой клетке сумма потенциалов равна стоимости: u_i + v_j = c_ij (x_ij > 0).

 

Получаем систему из 7 уравнений и 8 неизвестных – неопределенная. Определим произвольно u₃=0, тогда остальные потенциалы найдем однозначно.

u₁ = 1, u₂ = 4, u₃ = 0, v₁ = 3, v₂ = 5, v₃ = 3, v₄ = 4, v₅ = 2.

Вычисляем оценки всех свободных  клеток таблицы: _ij = u_i + v_j - c_ij (x_ij = 0).

₁₁ = 1 + 3 – 14 = -10 < 0,

₂₁ = 4 + 3 – 21 = –14 < 0,

₁₂  = 1 + 5 – 8 = -2 < 0, 

₂₂ = 4 + 5 – 10 = -1 < 0,

₁₃ = 1 + 3 – 17 = -13 < 0,

₃₃ = 0 + 3 – 8 = -5 < 0,

₂₄ = 4 + 4 – 11 = -3 < 0,

₃₅ = 0 + 2 – 9 = -7 < 0.

Решение Х₂ является оптимальным, т.к. не имеется положительных оценок.

При нем достигается минимальная  стоимость перевозок:

Z(X₂) = 70∙3 + 120∙5 + 105∙7 + 85∙5 + 40∙4 + 35∙3 + 75∙6 = 2685 д. ед.

Ответ:

 

Z(X₂) = 2685 д. ед.        min

Задача №5.

Распределить а=100 единиц средств по четырём предприятиям с целью получения максимальной суммарной прибыли. Прибыль с предприятий задаётся таблицей:

x	g1	g2	g3	g4
0	0	0	0	0
20	12	26	31	32
40	49	30	45	45
60	45	59	60	56
80	85	58	83	85
100	86	89	21	95

 

Решение.

Управление каждого шага состоит в выделении средств  какому-то определенному предприятию, поэтому разбиваем управление на 4 шага, номер шага будет соответствовать  номеру предприятия.

Состояние системы будем  связывать с имеющимися для распределения  средствами, тогда S₀ = 100, а . Управлением каждого шага x_k будет отражать количество выделяемых средств к k-му предприятию.

Система S – распределяемые денежные средства.

Она имеет следующие средства:

S_нач = S₀ – начальные средства

S₁ – средства выделены первому предприятию, остальным еще не распределялись.

S₂ – средства выделены первому и второму предприятиям, остальным еще не распределялись.

S₃ – средства выделены первому, второму и третьему предприятиям, четвертому еще не распределялись.

S₄ = Sкон – все средства распределены между четырьмя предприятиями.

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

Составим уравнение Беллмана:

Составим таблицу для  вычислений (см. таблицу 5).

Вывод:

При S₀ = 100, z_max = 138 (д. ед.)  x₁*(100) = 40

S₁ = S₀ – x₁* = 100 – 40 = 60

x₂*(S₁) = x₂*(60) = 20

S₂ = S₁ – x₂* = 60 – 20 = 40

x₃*(S₂) = x₃*(40) = 20

S₃ = S₂ – x₃* = 40 – 20 = 20

x₄*(S₃) = x₄*(20) = S₃ = 20

Ответ.

х* = (40; 20; 20; 20), z_max = 138 (д. ед.)

Оптимальное распределение  средств S₀ = 100 единиц между четырьмя предприятиями:

- первому предприятию  – 40 д. ед.;

- второму предприятию  – 20 д. ед.;

- третьему предприятию  – 20 д. ед.;

- четвертому предприятию  – 20 д. ед.

Полученная прибыль составляет 138 д. ед. и является максимальной.

 

 

Таблица 5.

Sk-1	xk	Sk	k = 3			k = 2			k = 1
			f3(x3)+z4*(S3)	z3(S2)	x3(S2)	f2(x2)+z3*(S2)	z2(S1)	x2(S1)	f1(x1)+z2*(S1)	z1(S0)	x1(S0)
0	0	0	0 + 0 = 0	0	0	0 + 0 = 0	0	0	0 + 0 = 0	0	0
20	0	20	0 + 32 = 32	32	0	0 + 32 = 32	32	0	0 + 32 = 32	32	0
	20	0	31 + 0 = 31			26 + 0 = 26			12 + 0 = 12
40	0	40	0 + 45 = 45			0 + 63 = 63	63	0	0 + 63 = 63	63	0
	20	20	31 + 32 = 63	63	20	26 + 32 = 58			12 + 32 = 44
	40	0	45 + 0 = 45			30 + 0 = 30			49 + 0 = 49
60	0	60	0 + 56 = 56			0 + 77 = 77			0 + 89 = 89	89	0
	20	40	31 + 45 = 76			26 + 63 = 89	89	20	12 + 63 = 75
	40	20	45 + 32 = 77	77	40	30 + 32 = 62			49 + 32 = 81
	60	0	60 + 0 = 60			59 + 0 = 59			45 + 0 = 45
80	0	80	0 + 85 = 85			0 + 92 = 92			0 + 103 = 103
	20	60	31 + 56 = 87			26 + 77 = 103	103	20	12 + 89 = 101
	40	40	45 + 45 = 90			30 + 63 = 93			49 + 63 = 112	112	40
	60	20	60 + 32 = 92	92	60	59 + 32 = 91			45 + 32 = 77
	80	0	83 + 0 = 83			58 + 0 = 58			85 + 0 = 85
100	0	100	0 + 95 = 95			0 + 116 = 116			0 + 122 = 122
	20	80	31 + 85 = 116	116	20	26 + 92 = 118			12 + 103 = 115
	40	60	45 + 56 = 101			30 + 77 = 107			49 + 89 = 138	138	40
	60	40	60 + 45 = 105			59 + 63 = 122	122	60	45 + 63 = 108
	80	20	83 + 32 = 115			58 + 32 = 90			85 + 32 = 117
	100	0	21 + 0 = 21			89 + 0 = 89			86 + 0 = 86

Заключение

В выполненной курсовой работе были описаны теоретические вопросы  по некоторым методам решения систем линейных уровнений. Рассмотрены соответствующие примеры решения.

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

 

Список литературы

 

1. Т. Шуп. Решение интегральных задач на ЭВМ. Мир., М.,2002
2. Л. Коллатц, Ю. Альберхт. Задачи по прикладной математике. Мир., М.,1998.
3. Т.А. Обгадзе. Элементы математического моделирования. Учебное пособие. Грузинский Политехнический Институт им. В.И. Ленина, Тбилисси, 1999.