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

Задание №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