Основы теории и практики моделирования

 

3х летний курс обучения

 

Данилкин Вадим Юрьевич шифр 558

 

 

Город Шатура

 

 

Вариант контрольного задания определяется суммой двух последних цифр шифра студента и указан в первой строке таблицы. Во второй строке таблицы указан номер первого задания (В1) по варианту, в третьей – второго задания (В2).

 

Задание 1

 

Вариант 13

 

В1 – 8

 

Привести к канонической форме следующие задачи линейного программирования.

 

2x₁ - x₂ - x₃ + x₄≤6

x₁ + 2x₂ + x₃ - x₄≥8

3x₁ - x₂ + 2x₃ + 2x₄≤10

- x₁ + 3x₂ + 5x₃ - 3x₄=15

Х₁ ≥0, Х₂≥0, Х₃≥0, Х₄≥0

F(X) = - x₁ + 2x₂ - x₃ + x₄ ---> min

 

Симплекс-метод.

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

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

2x₁ - x₂ - x₃ + x₄≤6

x₁ + 2x₂ + x₃ - x₄≥8

3x₁ - x₂ + 2x₃ + 2x₄≤10

- x₁ + 3x₂ + 5x₃ - 3x₄=15

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x₅. В 2-м неравенстве смысла (≥) вводим базисную переменную x₆ со знаком минус. В 3-м неравенстве смысла (≤) вводим базисную переменную x₇.

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

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

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

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

Введем искусственные переменные x: в 2-м равенстве вводим переменную x₈; в 4-м равенстве вводим переменную x₉;

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

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

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

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

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

F(X) = -1x₁+2x₂-1x₃+x₄+Mx₈+Mx₉ → min

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

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

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

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

x₈ = 8-x₁-2x₂-x₃+x₄+x₆

x₉ = 15+x₁-3x₂-5x₃+3x₄

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

F(X) = -x₁ + 2x₂-x₃ + x₄ + M(8-x₁-2x₂-x₃+x₄+x₆) + M(15+x₁-3x₂-5x₃+3x₄) → min

или

F(X) = (-1)x₁+(2-5M)x₂+(-1-6M)x₃+(1+4M)x₄+(M)x₆+(23M) → min

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

 

	-1	-1
			-1		-1
	-1
-1			-3

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

Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

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

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

X1 = (0,0,0,0,6,0,10,8,15)

Базисное решение называется допустимым, если оно неотрицательно.

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5			-1	-1
x8					-1		-1
x7			-1
x9		-1			-3
F(X0)	23M		-2+5M	1+6M	-1-4M		-M

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

Итерация №0.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

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

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

min (-, 8: 1, 10: 2, 15: 5) = 3

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

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x5			-1	-1							-
x8					-1		-1
x7			-1
x9		-1			-3
F(X1)	23M		-2+5M	1+6M	-1-4M		-M

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₉ в план 1 войдет переменная x₃.

Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₉ плана 0 на разрешающий элемент РЭ=5

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₃ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃.

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

 

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5		9/5	-2/5		2/5					1/5
x8		6/5	7/5		-2/5		-1			-1/5
x7		17/5	-11/5		16/5					-2/5
x3		-1/5	3/5		-3/5					1/5
F(X1)	-3+5M	11/5+11/5M	-23/5+12/5M		-2/5-2/5M		-M			-1/5-11/5M

Итерация №1.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

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

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

min (-, 5: 1²/₅, -, 3: ³/₅) = 3⁴/₇

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

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x5		14/5	-2/5		2/5					1/5	-
x8		11/5	12/5		-2/5		-1			-1/5	34/7
x7		32/5	-21/5		31/5					-2/5	-
x3		-1/5	3/5		-3/5					1/5
F(X2)	-3+5M	11/5+11/5M	-23/5+12/5M		-2/5-2/5M		-M			-1/5-11/5M

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₈ в план 2 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₈ плана 1 на разрешающий элемент РЭ=1²/₅

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂.

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

 

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	73/7	15/7			2/7		-2/7		2/7	1/7
x2	25/7	6/7			-2/7		-5/7		5/7	-1/7
x7	83/7	37/7			18/7		-11/7		11/7	-5/7
x3	6/7	-5/7			-3/7		3/7		-3/7	2/7
F(X2)	62/7	33/7			-11/7		-16/7		16/7-M	-4/7-M

Итерация №2.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

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

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

min (10³/₇: 2¹/₇, 3⁴/₇: ⁶/₇, 11⁶/₇: 5²/₇, -) = 2⁹/₃₇

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

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x5	103/7	21/7			2/7		-2/7		2/7	1/7	413/15
x2	34/7	6/7			-2/7		-5/7		5/7	-1/7	41/6
x7	116/7	52/7			24/7		-14/7		14/7	-5/7	29/37
x3	6/7	-5/7			-3/7		3/7		-3/7	2/7	-
F(X3)	62/7	33/7			-11/7		-16/7		16/7-M	-4/7-M

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₇ в план 3 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 3, получена в результате деления всех элементов строки x₇ плана 2 на разрешающий элемент РЭ=5²/₇

На месте разрешающего элемента в плане 3 получаем 1.

В остальных клетках столбца x₁ плана 3 записываем нули.

Таким образом, в новом плане 3 заполнены строка x₁ и столбец x₁.

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

 

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	208/37				-28/37		13/37	-15/37	-13/37	16/37
x2	61/37				-26/37		-17/37	-6/37	17/37	-1/37
x1	83/37				18/37		-11/37	7/37	11/37	-5/37
x3	91/37				-3/37		8/37	5/37	-8/37	7/37
F(X3)	-115/37				-230/37		-31/37	-24/37	31/37-M	-4/37-M

1. Проверка критерия оптимальности.

Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	208/37				-28/37		13/37	-15/37	-13/37	16/37
x2	61/37				-26/37		-17/37	-6/37	17/37	-1/37
x1	83/37				18/37		-11/37	7/37	11/37	-5/37
x3	91/37				-3/37		8/37	5/37	-8/37	7/37
F(X4)	-115/37				-230/37		-31/37	-24/37	31/37-M	-4/37-M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

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

x₂ = 1²⁴/₃₇

x₁ = 2⁹/₃₇

x₃ = 2¹⁷/₃₇

F(X) = 2•1²⁴/₃₇ -1•2⁹/₃₇ -1•2¹⁷/₃₇ = -1¹⁵/₃₇

Анализ оптимального плана.

В оптимальный план вошла дополнительная переменная x₅. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 5²³/₃₇

Значение 0 в столбце x₁ означает, что использование x₁ - выгодно.

Значение 0 в столбце x₂ означает, что использование x₂ - выгодно.

Значение 0 в столбце x₃ означает, что использование x₃ - выгодно.

Значение -2³⁰/₃₇> 0 в столбце x₄ означает, что использование x₄ - не выгодно.

Значение ^-31/₃₇ в столбце x₆ означает, что теневая цена (двойственная оценка) равна ^-31/₃₇.

Значение ^-24/₃₇ в столбце x₇ означает, что теневая цена (двойственная оценка) равна ^-24/₃₇.

Значение ³¹/₃₇-1M в столбце x₈ означает, что теневая цена (двойственная оценка) равна ³¹/₃₇-1M.

Значение ^-4/₃₇-1M в столбце x₉ означает, что теневая цена (двойственная оценка) равна ^-4/₃₇-1M.

 

Задание 2

Вариант 13

 

В2 – 11

 

Bi Аi	B1	B2	B3	B4	B5	Запасы ai
А1	80 2	40 4	1	6	7
А2	3	20 3	70 5	20 4	2
А3	8	9	6	80 3 3	50 4 4
Потребности bj

 

Получил 7 заполненных клеток – данный план является опорным

(m+n-1=5+3-1=7).

Вычислю общую сумму затрат на перевозки груза по этому плану:

Z₁= 80*2+40*4+20*3+70*5+20*4+80*3+50*4=1250

 

Bi Аi	B1	B2	B3	B4	B5	Запасы ai
А1	50 2	4	70 1	6	7
А2	30 3	30 3	5	4	50 2
А3	8	30 9	6	100 4 3	4
Потребности bj

 

Получил 7 заполненных клеток – данный план является опорным

(m+n-1=5+3-1=7).

Вычислю общую сумму затрат на перевозки груза по этому плану:

 

Z₂= 50*2+30*3+30*3+30*9+70*1+100*4+50*2=1120