Задачи по "Математике"

Задание №1.

 

Необходимо найти минимальное  значение целевой функции F = 2x₁+x₂ → min, при системе ограничений:

x1+x2≤12	(1)
2x1-x2≤12	(2)
2x1-x2≥0	(3)
2x1+x2≥4	(4)
x1≥0	(5)
x2≥0	(6)

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

 

или

Границы области допустимых решений

 

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

 

 

 

 

 

 

 

 
Обозначим границы области многоугольника решений.

 

Рассмотрим целевую функцию  задачи F = 2x₁+x₂ → min. 

 
Построим прямую, отвечающую значению функции F = 0: F = 2x₁+x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Область допустимых решений представляет собой  многоугольник.

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых(3) и (4), то ее координаты удовлетворяют уравнениям этих прямых: 
2x₁-x₂≥0 
2x₁+x₂≥4 
 
Решив систему уравнений, получим: x₁ = 1, x₂ = 2 
Откуда найдем минимальное значение целевой функции: 
F(X) = 2*1 + 1*2 = 4 
Поскольку функция цели F(x) параллельна прямой (4), то на отрезке AB функция F(x) будет принимает одно и тоже минимальное значение. 
Для определения координат точки B решим систему двух линейных уравнений: 
x₂=0 
2x₁+x₂≥4 
 
Решив систему уравнений, получим: x₁ = 2, x₂ = 0 
Откуда найдем минимальное значение целевой функции: 
F(X) = 2*2 + 1*0 = 4

Решение задачи  симплекс-методом

 Целевая функция:

2X1+1X2+1X3-1X4→max

Условия:

1X1-1X2+1X3+0X4=1

2X1+1X2+0X3+1X4=3

 

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

 

1X1-1X2+1X3+0X4+R1=1

2X1+1X2+0X3+1X4+R2=3

 

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам  необходимо найти максимум целевой  функции, то в таблицу заносятся  коэффициенты с противоположным  знаком.

Так как среди исходного  набора условий были равенства, мы ввели  искусственные переменные R. Это значит, что в симплекс таблицу нам необходимо добавить дополнительную строку M, элементы которой рассчитываются как сумма соответствующих элементов условий-равенств (тех которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.

 

 

 

 

Из данных задачи составляем исходную симплекс таблицу.

 

X1 X2 X3 X4 Своб. член

F -2 -1 -1 1 0

R1 1 -1 1 0 1

R2 2 1 0 1 3

M -3 0 -1 -1 -4

 

Так как в столбце свободных  членов нет отрицательных элементов, то найдено допустимое решение. В строке M имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -3 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 1.

 

X2 X3 X4 Своб. член

F -3 1 1 2

X1 -1 1 0 1

R2 3 -2 1 1

M -3 2 -1 -1

 

 

В строке M имеются отрицательные  элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -3 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R2, а ведущий элемент: 3.

 

X3 X4 Своб. член

F -1 2 3

X1 0 0 1

X2 -1 0 0

M 0 0 0

 

 В строке M отрицательные  элементы отсутствуют. Рассмотрим  строку F в которой имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -1 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X1, а ведущий элемент: 0.

 

X1 X4 Своб. член

F 3 3 7

X3 3 1 4

X2 2 1 3

M 0 0 0

 

Так как в строке F нет  отрицательных элементов, то найдено  оптимальное решение F=7

при значениях переменных равных: X3=4, X2=3,

 

 

 

 

 

Задача:

Имеется 3 склада содержащие некоторое количество единиц однотипной продукции (см. таблицу 1), имеется также 4 потребителя нуждающиеся в определенном количестве данной продукции (см. таблицу 2). При перевозке одной единицы продукции со склада i потребителю j возникают издержки P_ij. Величины издержек приведены в таблице 3. При перевозке K единиц продукции со склада i потребителю j суммарные затраты на перевозку составляют K*P_ij. 
 
Требуется найти такой план перевозок при котором общие затраты на перевозку всей продукции, по всем потребителям, будут минимальны.

Таблица 1 Склад №  Запас ед. продукции  1 9 2 16 3 5 Таблица 2 Потребитель №  Потребность в ед. продукции  1 11 2 7 3 8 4 4 Таблица 3   Потребители Склад №  1 2 3 4 1 2 5 8 1 2 8 3 9 2 3 7 4 6 3

 
Издержки на перевозку единицы  продукции со склада i потребителю j

 

 

 
 

Шаг:1 
Проверка на сбалансированность

Общее число запасов на складах :

30

; Общая потребность :

30

Задача является  сбалансированной (закрытой). 
 
 
Шаг:2 
Отыскание начального решения. Метод северо-западного угла

Запишем настоящую задачу в виде транспортной таблицы. В верхней строке перечислим потребности потребителей по порядку  номеров. В левом столбце перечислим имеющиеся запасы на складах. На пересечении j-го столбца и i-й строки будем записывать количество продукции, поставляемое с i-го склада j-му потребителю. Пока начальное решение не найдено, оставим эти клетки пустыми.

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9
a2= 16
a3= 5

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

 

 

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	X				9
a2= 16					16
a3= 5					5
	11	7	8	4

 

 

Итерация: 1 
Заполним клетку a₁,b₁. 
Сравним значения остатков для производителя a₁ и потребителя b₁.

Нераспределенных  остатков по запасам для a₁ меньше (см. таблицу выше, серый шрифт), запишем меньшее число в клетку a₁,b₁ одновременно вычитая его из обеих клеток остатков (см. таблицу ниже). При этом клетка остатков по запасам обнулится указывая, что все запасы производителя a₁ использованы (см. таблицу ниже). Поэтому исключим строку a₁ из дальнейшего рассмотрения (серый фон).  
Ненулевое значение остатка по потребностям для b₁ показывает, сколько единиц продукции ему еще требуется.

 

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9				0
a2= 16	X				16
a3= 5					5
	2	7	8	4

 

 

 

 

 

 

 

 

 

 

Итерация: 2 
Заполним клетку a₂,b₁. 
Сравним значения остатков для производителя a₂ и потребителя b₁.

Нераспределенных  остатков по потребностям для b₁ меньше (см. таблицу выше, серый шрифт), запишем меньшее число в клетку a₂,b₁ одновременно вычитая его из обеих клеток остатков (см. таблицу ниже). При этом клетка остатков по потребностям обнулится указывая, что все потребности для b₁ удовлетворены (см. таблицу ниже). Поэтому исключим столбец b₁ из дальнейшего рассмотрения (заштрихованный фон).  
Ненулевое значение остатка по запасам для a₂ показывает, сколько единиц продукции у него осталось не потребленной.

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9				0
a2= 16	2	X			14
a3= 5					5
	0	7	8	4

 
Итерация: 3

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9				0
a2= 16	2	7	X		7
a3= 5					5
	0	0	8	4

 

Итерация: 4

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9				0
a2= 16	2	7	7		0
a3= 5			X		5
	0	0	1	4

Итерация: 5

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9				0
a2= 16	2	7	7		0
a3= 5			1	X	4
	0	0	0	4

Итерация: 6

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9				0
a2= 16	2	7	7		0
a3= 5			1	4	0
	0	0	0	0

Получено  допустимое начальное решение (опорный план) (см. таблицу ниже), удовлетворены нужды всех потребителей и использованы все запасы производителей.

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9
a2= 16	2	7	7
a3= 5			1	4

 

Шаг:3

Проверим  полученный опорный план на не вырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=6, n+m=4+3=7 , что удовлетворяет условию не вырожденности плана.

 Шаг:4

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

 

 

 

 

 

 

 

 

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9     2
a2= 16	2     8	7     3	7     9
a3= 5			1     6	4     3

Перемножим  числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим. Получим значение суммарных затрат, для данного  начального решения.

Pнач=

136

 
Шаг:5 
 
Проведем поэтапное улучшение начального решения, используя метод потенциалов. 
 
Итерация: 1

 
Составим вспомогательную рабочую  матрицу затрат. Она строится из исходной матрицы издержек (см. Таблицу 3) путем переноса только тех ячеек  P_ij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми. 
Кроме того, введем вспомогательный столбец в который внесем значения неизвестных U₁ ... U₃ (3,это m - число складов) и вспомогательную строку в которую внесем значения неизвестных V₁ ... V₄ (4,это n - число потребителей). На рисунке они представлены серым цветом. Эти n+m неизвестных должны для всех (i,j), соответствующих загруженным клеткам, удовлетворять линейной системе уравнений 
 
U_i+V_j=P_ij 
 
Эту систему всегда можно решить следующим способом: На первом шаге полагают V₄=0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения U_i+V_j=P_ij, так как значение другой неизвестной в этом уравнении уже известно. То какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные U_i и V_j называются симплекс-множителями или потенциалами. 
Рабочая матрица затрат с рассчитанными потенциалами представлена ниже.

 

	b1	b2	b3	b4
a1	2				u1= 0
a2	8	3	9		u2= 6
a3			6	3	u3= 3
	v1= 2	v2= -3	v3= 3	v4= 0

 

Порядок вычисления потенциалов  был следующий: 
   1) Пусть V₄ = 0 ; 
   2) U₃ = P_3,4 - V₄ ; 
   3) V₃ = P_3,3 - U₃ ; 
   4) U₂ = P_2,3 - V₃ ; 
   5) V₁ = P_2,1 - U₂ ; 
   6) V₂ = P_2,2 - U₂ ; 
   7) U₁ = P_1,1 - V₁ ;

 
Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки S_ij, по формуле S_ij = P_ij – U_i - V_j (синий цвет). Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза. Таким образом, если среди оценок имеются отрицательные (затраты уменьшаются) то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции.

Если  же среди оценок нет отрицательных - план является оптимальным. 
Рабочая матрица затрат с заполненными оценками клетками представлена ниже.

	b1	b2	b3	b4
a1	2	8	5	1	u1= 0
a2	8	3	9	-4	u2= 6
a3	2	4	6	3	u3= 3
	v1= 2	v2= -3	v3= 3	v4= 0

 

Из  всех отрицательных оценок имеет  смысл выбрать наибольшую по модулю (серый цвет), так как ее воздействие на общие затраты является максимальным. В нашем случае такая оценка находится в ячейке а₂,b₄ (серый цвет), в соответствующую ячейку транспортной таблицы мы должны переместить некоторое количество продукции т.е. загрузить ее. Отметим в транспортной таблице ячейку а₂,b₄ знаком + . Кроме нее мы пометим знаками - и + другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков + будет равно числу знаков - . Это всегда можно сделать единственным образом, причем в каждой строке и каждом столбце содержится по одному + и - .То есть помеченные знаками клетки должны образовывать цикл.

 

 

 

 

 

 

 

	b1= 11	b2= 7	b3= 8	b4= 4
a1= 9	9
a2= 16	2	7	7     -	+
a3= 5			1     +	4     -