Методы оптимальных решений

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Уральский государственный экономический университет

Контрольная работа

По дисциплине «Методы оптимальных решений»

2012

Задача № 1

На поверхности x2/96 + y2 + z2 = 1 найти точки, наиболее и наименее удаленные от плоскости 3x + 4y + 12z = 288

Метод Лагранжа

Рассмотрим точку M(x,y,z), лежащую на заданной поверхности. Расстояние от точки M до плоскости 3x + 4y + 12z = 288 вычисляется по формуле

Чтобы исследовать расстояние на экстремум, достаточно исследовать на экстремум более простую функцию f(x,y,z)= 3x + 4y + 12z = 288, причём надо учесть, что точка M(x,y,z) не произвольная точка пространства, а лежит на заданной поверхности

Составим функцию Лагранжа

Найдем частные производные этой функции по x,y,z л.

Приравняв частные производные к нулю, получим систему:

Решим систему

Подставим полученные x,y,z в последнее уравнение системы

Для получим критическую точку M1(-9;-1/8;-3/8)

Для получим критическую точку M2(9;1/8;3/8)

Вычислим расстояния от M1 и M2 до заданной плоскости:

Точка M1(-9;-1/8;-3/8) наиболее удалена от заданной плоскости

Точка M2(-9;-1/8;-3/8) наименее удалена от заданной плоскости

Задача № 2

Имеется N листов материала. Необходимо раскроить имеющийся материал для получения заготовок трех видов. Существует M разумных способов размещения заготовок на листе.

Известны:

цены реализации заготовок,

закупочная цена одного листа материала,

количество заготовок каждого из трех видов, получаемое с одного листа при каждом способе раскроя.

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

Решение:

Для решения данной задачи введём следующие обозначения:

k=3 - виды заготовок

m=6 способы раскроя

P- закупочная цена одного листа.

Сj j=(1,2,3)- цены реализации заготовок

Aij- (i=1..4 j=1..3) количество заготовок «i»-того вида, полученные «j»-тым способом раскроя

Xj (j=1..3) количество штук исходного материала, которое следует раскроить по «j»-тому способу

X1= X11+ X12+ X13+ X14

X2= X21+ X22+ X23+ X24

X3= X31+ X32+ X33+ X34

Постановка задачи

Z(X)=С1*X1+C2*X2+C3*X3-P > max максимальная прибыль

При ограничениях

Задача № 3

Качество готового продукта определяется содержанием двух примесей, повышение содержания одной из которых ухудшает, а второй - улучшает качество продукта.

Имеется К компонентов, смешивая которые, необходимо получить продукт с заданными параметрами качества. Каждая компонента характеризуется своим содержанием полезной и вредной примесей.

Известны:

цена 1 кг готового продукта,

закупочная цена 1 кг каждой из К компонент,

количество каждой компоненты, имеющееся в наличии (кг),

процентное содержание каждой из двух примесей в каждой из К компонент,

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

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

К=4

Решение:

Введём обозначения и составим таблицу.

Характеристики	Компонент
	1	2	3	4
Закупочная цена 1 кг	P1	P2	P3	P4
Количество в наличии	Q1	Q2	Q3	Q4
Процентное содержание первой примеси	A1	A2	A3	A4
Процентное содержание второй примеси	B1	B2	B3	B4

Пусть Xi- (i=1…4) - количество j-ой компоненты в готовом продукте.

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

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

P- цена 1 кг готового продукта

Тогда Z=(x1+x2+x3+x4)*P-(x1*P1+ x1*P1+ x1*P1+ x1*P1) чистая прибыль от реализации готового продукта

Математическая постановка задачи

Найти maxZ при ограничениях

i=1..4

Задача № 4

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

Исходные данные:

Операция	Предшествующие операции	Продолжительность, дней
А	-	2
Б	А	4
В	-	4
Г	А,Б,Д	1
Д	А,В	11
Е	А,Б,Г	6
Ж	А,Б,В,Г,Е	2
И	А,Б,В,Г,Е,Д	5
К	А,В,Д	10



Рассчитаем пути

P1=Н0 +А+Б+Г+Е+Ж =2+4+1+6+2=15

P2=Н0 +А +Б+Г+Е+И =2+4+1+6+5=18

P3=Н0 +А +Б+Г+Ж =2+4+1+2=9

P4=Н0 +А +Б+Г +И =2+4+1+5=12

P5=Н0 +А+ Б+Е+Ж =2+4+6+2=14

P6=Н0 +А+ Б+Е+И =2+4+6+5=17

P7=Н0 +А+ Б+Ж =2+4+2=8

P8=Н0 +А+ Б+И =2+4+5=11

P9=Н0 +А+ Г+Е+Ж =2+1+6+2=11

P10=Н0 +А+ Г+Е+И =2+1+6+1=10

P11=Н0 +А+ Г+Ж =2+1+2=5

P12=Н0 +А+ Г+И =2+1+1=4

P13=Н0 +А+Д+И = 2+11+5=18

P14=Н0 +А+Д+К = 2+11+10=23

P15=Н0 +А+Д+Г+Е+Ж =2+11+1+6+2 =22

P16=Н0 +А+Д+Г+Е+И =2+11+1+6+5 =25

P17=Н0 +А+Д+Г+Ж =2+11+1+2 =16

P18=Н0 +А+Д+Г+И =2+11+1+5 =19

P19=Н0 +А+Ж =2+2 =4

P20=Н0 +А+Е+Ж =2+6+2 =10

P21=Н0 +А+Е+И =2+6+5 =13

P22=Н0 +А+И =2+5 =7

P23=Н0 +А+К =2+10 =12

P24=Н0 +В+Г+Е+Ж =4+1+6+2 =13

P25=Н0 +В+Г+Е+И =4+1+6+5 =16

P26=Н0 +В+Г+Ж =4+1+2 =7

P27=Н0 +В+Г+И =4+1+5 =10

P28=Н0 +В+Ж =4+2 =6

P29=Н0 +В+И =4+5 =9

P30=Н0 +В+Д+И =4+11+5 =20

P31=Н0 +В+Д+К =4+11+10 =25

P32=Н0 +В+Д+Г+Е+Ж =4+11+1+6+2 =24

P33=Н0 +В+Д+Г+Е+И +0=4+11+1+6+5+0=27 Критический путь

P34=Н0 +В+Д+Г+Ж =4+11+1+2 =18

P35=Н0 +В+Д+Г+И =4+11+1+5 =21

Нахождение резервов времени

Vi Vj	(Vi ek Vj)	tk(vj)=t(ek)+tp(vj-1)	tp(vj)=max tk(vj)	tk(vi)=tp(vj)+ t(ek)	tп(vi)=min tk(vi)
Н0	-	0	0
А	Н0 (2) А	0+2=2	2	22-6=16 6-4=2 16-1=15 27-5=22 27-2=25 27-10=17 15-11=4	2
В	Н0 (4) В	0+4=4	4	15-11=4 27-5=22 27-2=25 27-10=17	4
Б	А (4) Б	2+4=6	6	27-5=22 22-6=16 16-1=15 27-2=25	15
Д	А (11) Д В (11) Д	2+11=13 4+11=15	15	27-5=22 16-1=15	15
Г	A (1) Г Б (1) Г Д (1) Г	2+1=3 6+1=7 15+1=16	16	22-6=16	16
Е	А (6) Е Б (6) Е Г (6) Е	2+10=12 6+10=16 16+6=22	22	27-5=22	22
Ж	А (2) Ж Б (2) Ж В (2) Ж Е (2) Ж	2+2=4 6+2=8 4+2=6 22+2=24	24	27-0=27	27
И	А (5) И Б (5) И В (5) И Г (5) И Е (5) И Д (5) И	2+5=7 6+5=11 4+5=9 16+5=21 22+5=27 15+5=20	27	27	27
К	А (10) К В (10) К Д (10) К	2+10=12 4+10=14 15+10=25	25	27-0=27	27

P33=Н0 +В+Д+Г+Е+И =4+11+1+6+5=27 критический путь

В критический путь входят следующие операции: В Д Г Е И.

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

Вывод: в критический путь не входят события А, Б, Ж, К их резервы времени А(2 дня), Б(6-15 дней), Ж (24-27 дней), К(25-27 дней).

Задача № 5

Фабрика выпускает продукцию двух видов: П1 и П2. Продукция обоих видов поступает в оптовую продажу. Для производства этой продукции используются три исходных продукта - А, В, С. Максимально возможные суточные запасы этих продуктов составляют М, N и К т соответственно. Расходы сырья А, В, С на 1 тыс. изделий П1 и П2 приведены в табл. 1.1.

Таблица 1.1

Исходный продукт	Расход исходных продуктов на 1 тыс. изделий (т)	Максимально возможный запас (т)
	П1	П2
А	1	2	М
В	2	1	N
С	1	0,8	К

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

Оптовые цены 1 тыс. шт. изделий П1 равны 3 тыс. руб., 1 тыс. шт. П2 - 2 тыс.руб.

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

Построить математическую модель данной операции и решить оптимизационную задачу графическим и симплекс-методом.

М=7, N=9, К=6.

Построение математической модели

X1 - изделие П1

X2 - изделие П2

Тогда компоненты производственного плана должны (X1;X2) должны удовлетворять следующим условиям ограничениям

С другой стороны пара величин X1 и X2 может рассматриваться как некоторый вариант производственного плана.

Нужно найти план, приносящий наибольший доход:

Пришли к задаче линейного программирования

Графическое решение

OABCDE многоугольник решений

Вектор (3;2) вектор целевой функции.

Проведём через любую точку например (3;2) прямую P, перпендикулярно вектору .

Перемещаем прямую Р параллельно самой себе по направлению вектора , пока она не займёт относительно области OABC крайнего верхнего положения.

Это произойдёт, когда она пройдёт через точку С(11/3;5/3).

Оптимальное решение определяется координатами точки С(11/3;5/3) точка пересечения прямых 2x1+x2=9 и x1+2x2=7

Zmax=3*11/3+2*5/3=14.333

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

Введем дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

x1+2x2+x3=7

2x1+x2+x4=9

x1+0,8x2+x5=6

x2-x1+x6=1

x2+x7=2

эти дополнительные переменные по экономическому смыслу

означают неиспользуемое сырьё при данном плане производства

Преобразованную систему уравнений запишем в векторной форме:

x1*P1+x2*P2+x3*P3+x4*P4+x5*P5+ x5*P5+ x5*P5=P0,

где

P1= P2= P3= P4= P5= P0=

Cимплекс-таблица

	Базис	С.б.	P0	3	2	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7
1	P3	0	7	1	2	1	0	0	0	0
2	P4	0	9	2	1	0	1	0	0	0
3	P5	0	6	1	0.8	0	0	1	0	0
4	P6	0	1	-1	1	0	0	0	1	0
5	P7	0	2	0	1	0	0	0	0	1
			0	-3	-2	0	0	0	0	0

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

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

Вектор, который необходимо исключить P4.

Определяем наименьшее, среди отношений Bi/Pi, разрешающий элемент - 2.

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента

	Базис	С.б.	P0	3	2	0	0	0	0	0	множитель	мин
				P1	P2	P3	P4	P5	P6	P7
1	P3	0	2.5	0	1.5	1	-0.5	0	0	0	0.5	1.67
2	P1	3	4.5	1	0.5	0	0.5	0	0	0	1	9
3	P5	0	1.5	0	0.3	0	-0.5	1	0	0	0.5	5
4	P6	0	5.5	0	1.5	0	0.5	0	1	0	-0.5	3.67
5	P7	0	2	0	1	0	0	0	0	1	0	2
			13.5	0	-0.5	0	1.5	0	0	0

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

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

Вектор, который необходимо исключить P3.

Определяем наименьшее, среди отношений Bi/Pi, разрешающий элемент - 1.5. Преобразуем исходную симплекс-таблицу относительно разрешающего элемента

	Базис	С.б.	P0	3	2	0	0	0	0	0	множитель
				P1	P2	P3	P4	P5	P6	P7
1	P3	0	2	0	1.5	1	-0.5	0	0	0	0.5
2	P1	3	4	1	0.5	0	0.5	0	0	0	1
3	P5	0	1	0	0.3	0	-0.5	1	0	0	0.5
4	P6	0	5	0	1.5	0	0.5	0	1	0	-0.5
5	P7	0	2	0	1	0	0	0	0	1	0
			12	0	-0.5	0	1.5	0	0	0

Все ДZi>0, поэтому, полученное базисное решение

X1=3.6667 X2=1.6667 X5=1 X6=3 X7=0.333 является оптимальным, значение целевой функции для него равняется 14.333 усл. единицы.

Доход от реализации продукции был максимальным при X1=3.6667 X2=1.6667

Задача № 6

max (х1 + 3х2)

при

2х1 + 3х2 ? 6

х1 + 2х2 ?5

х1 ? 4

0 ? х2 ? 3.

Построим прямые 2х1 + 3х2 = 6 х1 + 2х2 =5 х1 = 4 х2 = 3. и вектор цели С(1;3)

И отметим области, которые они ограничивают

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



Задача № 7

Решить следующую ЗЛП:

max = (5х1 + 12х2 +4х3);

х1 + 2х2 + х3 ? 10;

2х1 - х2 + 3х3 = 8;

х2,3 ? 0.

х1, y2 не ограничены в знаке.

Найти решение задачи, двойственной к ЗЛП.

Решение:

Преобразуем ограничения задачи, для определения базиса

2х1 + 3х3-8 = х2

х1 + 2(2х1 + 3х3-8) + х3 ? 10

х1 + 4х1 + 6х3-16 + х3 ? 10

5х1 +7х3 ? 26

Получили ЗЛП

Исходная задача (L)

max = (5х1 + 12х2 +4х3)

при ограничениях

Двойственная ей задача (L*), будет иметь вид: найти

при ограничениях

Решим исходную задачу (L) симплекс методом в качестве начального базиса выбираем вектора x2 и x4.

x1*P1+x2*P2+x3*P3+x4*P4 =P0

где P1= P2= P3= P4= P0=

Cимплекс-таблица

	Базис	С.б.	P0	5	12	4	0
				P1	P2	P3	P4
1	P4	0	26	5	0	7	1
2	P2	12	-8	-2	1	-3	0
			-96	-24	12	-36	0

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

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

Определяем наименьшее, среди отношений Bi/Pi, разрешающий элемент - (-3).

Вектор, который необходимо исключить P2.

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента.

	Базис	С.б.	P0	5	12	4	0	множитель	мин
				P1	P2	P3	P4
1	P4	0	7.33	0.33	2.33	0	1	-2.33	3.14
2	P3	4	2.67	0.67	-0.33	1	0		-8
			10.67	2.67	-1.33	4	0

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

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

Определяем наименьшее, среди отношений Bi/Pi, разрешающий элемент - (2,33).

Вектор, который необходимо исключить P4.

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента

	Базис	С.б.	P0	5	12	4	0	множитель
				P1	P2	P3	P4
1	P2	12	3.14	0.14	1.00	0.00	0.43		22
2	P3	4	3.71	0.71	0.00	1.00	0.14	-0.14	5.2
			52.57	-0.43	0.00	0.00	5.71

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

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

Определяем наименьшее, среди отношений Bi/Pi, разрешающий элемент - (0,71).

Вектор, который необходимо исключить P3.

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента

	Базис	С.б.	P0	5	12	4	0
				P1	P2	P3	P4
1	P2	12	2.40	0.00	1.00	-0.20	0.40	0.2
2	P1	5	5.20	1.00	0.00	1.40	0.20
			54.80	0.00	0.00	0.60	5.80

Все ДZi>0, поэтому, получено базисное решение

X1=5,2 X2=2,4 является оптимальным, значение целевой функции для него равняется 54,8 усл. единиц.

Решение двойственной задачи (12;5,8)

Fmax(5.2;2.4;0)= 5*5.2+ 12*2.4=54.8

F*min(12;5,8)= -8*12+26*5,8=54,8

Задача № 8

Фирма обеспечивает поставку товаров для продажи с базы А0 в четыре торговые точки А1, А2, А3, А4. Расстояния между всеми пунктами известны и заданы в километрах (см. варианты заданий).

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

А0 А1 А2 А3 А4

А0	0	150	200	170	210
А1		0	60	190	220
А2			0	250	130
А3				0	100
А4					0

Решение:

Возьмем в качестве произвольного маршрута:

X0 = (1,2);(2,3);(3,4);(4,5);(5,1)

Тогда F(X0) = 150 + 60 + 250 + 100 + = 560

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

di = min(j) dij

i j	1	2	3	4	5	di
1	M	150	200	170	210	150
2		M	60	190	220
3			M	250	130
4				M	100
5					M

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

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

dj = min(i) dij

i j	1	2	3	4	5
1	M	0	50	20	60
2		M	60	190	220
3			M	250	130
4				M	100
5					M
dj		0			60

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.

i j	1	2	3	4	5
1	M	0	50	20	0
2		M	60	190	160
3			M	250	70
4				M	40
5					M

Шаг №1.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j	1	2	3	4	5	di
1	M	0(0)	50	20	0(40)	0
2	(60)	M	60	190	160	60
3	(0)	(0)	M	250	70
4	(0)	(0)	(0)	M	40
5	(0)	(0)	(0)	(20)	M
dj		0		20	40	0

Наибольшая сумма констант приведения равна (60 + ) = 60 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(2*,1*) = 210 + 60 = 270

i j	1	2	3	4	5	di
1	M	0	50	20	0	0
2	M	M	60	190	160	60
3			M	250	70
4				M	40
5					M
dj		0			0	60

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

?di + ?dj = 0

После операции приведения сокращенная матрица будет иметь вид:

i j	2	3	4	5	di
1	M	50	20	0	0
3		M	250	70
4			M	40
5				M
dj				0	0

Нижняя граница подмножества (2,1) равна:

H(2,1) = 210 + 0 = 210 < 270

Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут.

Шаг №2.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j	2	3	4	5	di
1	M	50	20	0(60)	20
3	(70)	M	250	70	70
4	(0)	(0)	M	40
5	(0)	(0)	(20)	M
dj			20	40	0

Наибольшая сумма констант приведения равна (70 + ) = 70 для ребра (3,2), следовательно, множество разбивается на два подмножества (3,2) и (3*,2*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(3*,2*) = 210 + 70 = 280

i j	2	3	4	5	di
1	M	50	20	0	0
3	M	M	250	70	70
4			M	40
5				M
dj				0	70

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

?di + ?dj = 0

После операции приведения сокращенная матрица будет иметь вид:

i j	3	4	5	di
1	50	20	0	0
4		M	40
5			M
dj			0	0

Нижняя граница подмножества (3,2) равна:

H(3,2) = 210 + 0 = 210 < 280

Чтобы исключить подциклы, запретим следующие переходы: (1,3),

Поскольку нижняя граница этого подмножества (3,2) меньше, чем подмножества (3*,2*), то ребро (3,2) включаем в маршрут.

Шаг №3.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j	3	4	5	di
1	M	20	0(60)	20
4	(40)	M	40	40
5	(0)	(20)	M
dj		20	40	0

Наибольшая сумма констант приведения равна (20 + 40) = 60 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).

Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,5*) = 210 + 60 = 270

i j	3	4	5	di
1	M	20	M	20
4		M	40
5			M
dj			40	60

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

?di + ?dj = 0

После операции приведения сокращенная матрица будет иметь вид:

i j	3	4	di
4		M
5
dj			0

Нижняя граница подмножества (1,5) равна:

H(1,5) = 210 + 0 = 210 < 270

Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут.

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,3) и (5,4).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(2,1), (1,5), (5,4), (4,3), (3,2),

Длина маршрута равна F(Mk) = 210

Задача № 9

Решить транспортную задачу. С - матрица стоимостей.

Прочерк означает невозможность перевозки по данному маршруту.

ai - запасы поставщиков,

bj - заявка потребителей.

b1 = 60;

b2 = 40;

b3 = 36;

b4 = 14.

Решение:

Поставщики	Потребители и потребительский спрос	Запасы
	B1	B2	B3	B4
A1	5	1	2	4		92
A2	2	5	нет	3		45
			перевозки
A3	нет	2	2	5		63
	перевозки
	60	40	36	14

Проверим сбалансированность транспортной задачи

Потребительский спрос 60+40+36+14=150

Запасы 92+45+63=200

Потребительский спрос меньше чем запасы.

Добавляем фиктивного потребителя В5=50. В клетку с невозможной перевозкой помещаем заведомо высокий тариф перевозки.

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

Поставщики	Потребители и потребительский спрос	Запасы
	B1 V1=	B2 V2=	B3 V3=	B4 V4=	B5 V5=
	5	1	2	4	0
A1 U1=	5	1	2	4	0	92
0	15	40	30	6	1
A2 U2=	2	5	100	3	0	45
3	45
A3 U3=	100	2	2	5	0	63
0			6	8	49
	60	40	36	14	50	200

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

Метод потенциалов.

Сосчитаем потенциалы по формуле

vj -ui=Cij

i=1,2,3; j=1,2,3,4

В расчёте участвуют только занятые клетки

Предполагаем u1=0 и постепенно вычисляем остальные числа.

Клетка А1В1: v1 -u1=C11 v1 -0=5 v1 =13

Клетка А1В2: v2 -u1=C12 v2 -0=1 v2 =1

Клетка А1В3: v3 -u1=C13 v3-0=2 v3=2

Клетка А1В4: v4 -u1=C14 v4 -0=4 v4=4

Клетка А1В5: v5 -u1=C15 v5 -0=0 v5=0

Клетка А2В1: v1 -u2=C21 5-u2=2 u2 =3

Клетка А3В3: v2 -u3=C32 2 -u3=2 u3 =2

После того как все потенциалы найдены для каждой из свободных клеток определяем числа:

ij=vj -ui -Cij

Клетка А2В2: 22=v2 -u2 -C22 22=-7

Клетка А2В3: 23=v2 -u2 -C23 23= -101

Клетка А2В4: 24=v2 -u2-C24 24= -2

Клетка А2В5: 25=v2 -u2-C25 25= -3

Клетка А3В1: 31=v3 -u1 -C31 31= -96

Клетка А3В2: 32=v3 -u2 -C32 32= -2

	-7	-101	-2	-3
-96	-2

Среди чисел ij нет положительных чисел.

Значит план оптимальный.

S=5*15+1*40+2*30+4*6+0*1+2*45+2*6+5*8+0*49=341 усл. единиц.

Задача № 10

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

mх1 + х12 руб.

При изготовлении х2 изделий вторым способом они составляют:

nх2 + х22 руб.

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

m = 2, n = 16, k = 100.

Решение:

Математическая постановка задачи состоит в определении минимального значения функции

плоскость лагранж раскрой смесь

при условиях

Решим задачу, использую метод множителей Лагранжа

Вычислим частные производные и приравняем их к нулю:

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

Решая это уравнение совместно с уравнением

точка подозрительная на экстремум

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

Найдём



Значит в точке (53.5;46.5) условный минимум

Общие затраты на производство продукции будут минимальными при следующем плане производства X1=53.5 X2=46.5

F(53.5;46.5)=5875.5 усл. единиц.

Размещено на Allbest.ru

...