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

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

x₁=15,

x₂=9,

z=10*9+3*15=135.

 

 

5. Прядильно-ниточное предприятие выпускает нитки с лавсаном (н/л) и нитки с капроном (н/к), для изготовления которых использует хлопок I сорта (х/1), а также и хлопок II сорта (х/2). На изготовление 1 тонны (н/л) требуется 85 кг (х/1) и 10 кг (х/2), на изготовление 1т (н/к)  требуется 6 кг (х/1) и 69 кг (х/2). Запасы хлопка на предприятии составляют соответственно:  285 кг - (х/1) и 375 кг - (х/2). 

Прибыль от реализации 1 т (н/л) составляет 1065 у.е., а от реализации 1 т (н/к) - 963 у.е.

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

Составим  математическую модель задачи:

Пусть x₁ – количество тонн выпускаемых ниток с лавсаном, а x₂ – количество выпускаемых ниток с капроном, тогда 1065x₁+963x₂ – суммарная прибыль.

85x₁+6x₂ – количество хлопка I сорта, необходимое для изготовления всех ниток, а 10x₁+69x₂ - количество хлопка II сорта, необходимое для изготовления всех ниток. Так как запасы хлопка на предприятии ограничены, получаем ограничения:

85x₁+6x₂≤285,

10x₁+69x₂≤365.

Количество  выпускаемых ниток не может быть отрицательным числом, значит x₁≥0, x₂≥0.

Таким образом, математическая модель задачи имеет  вид:

F(X)=1065x₁+963x₂→max

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

85x₁+6x₂≤285,

10x₁+69x₂≤365.

x₁≥0, x₂≥0.

Составим двойственную задачу:

y₁, y₂ – условные цены на хлопок первого и второго сортов,

Целевая функция будет иметь  вид: F(Y)=285y₁+365y₂. Так как в прямой задаче необходимо найти максимум, в двойственной необходимо найти минимум: F(Y)=285y₁+365y₂→min.

Ограничения для двойственной задачи:

85y₁+10y₂≥1065,

6y₁+69y₂≥963,

y₁≥0, y₂≥0.

Решаем прямую задачу графическим  методом:

F(X)=1065x₁+963x₂→max

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

85x₁+6x₂≤285,

10x₁+69x₂≤365.

x₁≥0, x₂≥0.

 
Решение достигается в точке пересечения двух прямых:_, . Решая систему уравнений получаем решение: X(3 4/387, 4 239/280). Подставим значение в целевую функцию: F(3 4/387, 4 239/280)=7880.

Решаем двойственную задачу графическим методом:

F(Y)=285y₁+365y₂→min.

85y₁+10y₂≥1065,

6y₁+69y₂≥963,

y₁≥0, y₂≥0.

 
Решение достигается в точке пересечения двух прямых:_, 6y₁+69y₂=963. Решая систему уравнений получаем решение: X(11, 13). Подставим значение в целевую функцию: F(11,13)=7880.

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

 

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

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

Найти такой  план перевозок, при котором суммарные  затраты  оказались бы минимальными.

«з»	ЗАПАС	B1	B2	B3	B4	B5
A1	70	4	3	5	2	7
A2	50	7	1	2	3	3
A3	60	9	2	4	5	1
A4	30	1	3	6	4	2
«п»	ПОТР	40	45	40	35	50

Проверим  необходимое и достаточное условие  разрешимости задачи: общие запасы равны потребностям:

70+50+60+30=210,

40+45+40+35+50=210.

Построим  первый опорный план методом северо-западного  угла:

	B1	B2	B3	B4	B5	Запасы
A1	4 [40]	3 [30]	5	2	7	70
A2	7	1 [15]	2 [35]	3	3	50
A3	9	2	4 [5]	5 [35]	1 [20]	60
A4	1	3	6	4	2 [30]	30
Потребности	40	45	40	35	50

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

Количество  занятых строк таблицы – 8, а  должно быть m+n-1=8. Значит опорный план невырожденный.

Проверяем оптимальность  опорного плана: найдем предварительные  потенциалы, полагая что u₁=0.

	v1=4	v2=3	v3=4	v4=5	v5=1
u1=0	4 [40]	3 [30]	5	2	7
u2=-2	7	1 [15]	2 [35]	3	3
u3=0	9	2	4 [5]	5 [35]	1 [20]
u4=1	1	3	6	4	2 [30]

Определяем  характеристики для свободных неизвестных  по формуле 

E_ij=C_ij-(U_i+V_j) и записываем их в таблицу:

	v1=4	v2=3	v3=4	v4=5	v5=1
u1=0	4 [40]	3 [30]	5 1	2 -3	7 6
u2=-2	7 5	1 [15]	2 [35]	3 0	3 4
u3=0	9 5	2 -1	4 [5]	5 [35]	1 [20]
u4=1	1 -4	3 -1	6 1	4 -2	2 [30]

Так как  есть отрицательные оценки, план не является оптимальным.

 

 

Строим  контур:

	v1=4	v2=3	v3=4	v4=5	v5=1
u1=0	4 [40] [-]	3 [30] [+]	5 1	2 -3	7 6
u2=-2	7 5	1 [15] [-]	2 [35] [+]	3 0	3 4
u3=0	9 5	2 -1	4 [5] [-]	5 [35]	1 [20] [+]
u4=1	1 [+] -4	3 -1	6 1	4 -2	2 [30] [-]

Получаем  новый опорный план:

	B1	B2	B3	B4	B5	Запасы
A1	4 [35]	3 [35]	5	2	7	70
A2	7	1 [10]	2 [40]	3	3	50
A3	9	2	4	5 [35]	1 [25]	60
A4	1 [5]	3	6	4	2 [25]	30
Потребности	40	45	40	35	50

Проверяем оптимальность  опорного плана: найдем предварительные  потенциалы, полагая что u₁=0.

	v1=4	v2=3	v3=4	v4=9	v5=5
u1=0	4 [35]	3 [35]	5	2	7
u2=-2	7	1 [10]	2 [40]	3	3
u3=-4	9	2	4	5 [35]	1 [25]
u4=-3	1 [5]	3	6	4	2 [25]

Определяем  характеристики для свободных неизвестных  по формуле 

E_ij=C_ij-(U_i+V_j) и записываем их в таблицу:

	v1=4	v2=3	v3=4	v4=9	v5=5
u1=0	4 [35]	3 [35]	5 1	2 -7	7 2
u2=-2	7 5	1 [10]	2 [40]	3 -4	3 0
u3=-4	9 0	2 3	4 0	5 [35]	1 [25]
u4=-3	1 [5]	3 3	6 5	4 -2	2 [25]

Так как  есть отрицательные оценки, план не является оптимальным.

 Строим  контур:

	v1=4	v2=3	v3=4	v4=9	v5=5
u1=0	4 [35] [-]	3 [35]	5 1	2 [+] -7	7 2
u2=-2	7 5	1 [10]	2 [40]	3 -4	3 0
u3=-4	9 0	2 3	4 0	5 [35] [-]	1 [25] [+]
u4=-3	1 [5] [+]	3 3	6 5	4 -2	2 [25] [-]

Получаем  новый опорный план:

	B1	B2	B3	B4	B5	Запасы
A1	4 [10]	3 [35]	5	2 [25]	7	70
A2	7	1 [10]	2 [40]	3	3	50
A3	9	2	4	5 [10]	1 [50]	60
A4	1 [30]	3	6	4	2	30
Потребности	40	45	40	35	50