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

r(D)=2*1448/ 23  +236/23=3132/23=136.17

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

Пусть, наконец, r>136.17. Тогда оптимальная программа D окажется ниже уровня лимита по сырью. Эту ситуацию отражает положение пунктирной прямой (4). Сырье становится избыточным относительно оптимальной программы D, и его предельная эффективность становится нулевой в диапазоне (136.17, ∞).

На основе результатов выполненного анализа получим табличную запись функции предельной эффективности  поступающего сырья для данного  предприятия (табл. 2.1) и табличное  предоставление функции зависимости максимума выручки от увеличения производственного потребления сырья (табл. 2.2). Используя информацию из этих таблиц, построим графики этих функций (рис. 2.3 и рис. 2.4).

Таблица 2.1 Функция предельной эффективности  сырья

Предельная эффективность, y1 (руб./кг)	323	23	0
Сырье, R (кг)	(0, 26]	(26, 136.17]	(136.17, ∞)

 

 

Таблица 2.2 Зависимость максимума  выручки от сырья

Максимум выручки,    Z*(руб.)	323r	6460 + 23r	10932
Сырье, r (кг)	(0, 26]	(26, 136.17]	(136.17, ∞)

 

Рис. 3. График изменения предельной эффективности сырья на предприятии

Рис. 4 График максимума выручки в зависимости от поступления сырья

 

Задание 3

Необходимо доставить однородный груз от трех филиалов фирмы пяти потребителям:

		Филиал 1	Филиал 2	Филиал 3
Предложение  филиалов (ед.):		102	6	94
		потр.1	потр.2	потр.3	потр.4	потр.5
Спрос потребителей (ед.):		44	64	62	12	90
Известна матрица затрат на доставку единицы груза от каждого  поставщика потребителю (руб.).
		потр.1	потр.2	потр.3	потр.4	потр.5
Поставщик 1		10	11	9	6	8
Поставщик 2		11	12	9	7	10
Поставщик 3		10	8	7	7	8

 

1. Составить ЭММ расчета оптимального  плана перевозок.   

2. Определить исходный опорный план методом северо-западного угла. 

3. Найти оптимальный план перевозок  методом потенциалов и указать  соответствующие ему минимальные  транспортные затраты.   

РЕШЕНИЕ

Обозначим х_ij – объемы перевозок груза от поставщика а_i потребителю b_j, тогда стоимость перевозок .

44+64+62+12+90=272

102+6+94=202

Задача открытая, получаем математическую модель:

 

Для решения задачи необходимо  ввести фиктивного поставщика с тарифами c_4j=0 и запасами 70 ед.

Найдем начальный план методом  северо-западного угла. Среди элементов матрицы стоимостей выбираем  х₁₁. В соответствующую клетку (1, 1) записываем максимально возможный объем перевозки х₁₁ = min {A₁ B₁} = min {102, 44} = 44. Потребности первого потребителя удовлетворены, исключаем первую строку из рассмотрения. Рассмотрим второго потребителя, ему от первого поставщика можно доставить 102-44=58, значит   х₂₄= min {58, 64} =  58. В соответствующую клетку таблицы записываем перевозку х₂₄ = 58. Запасы 1-го поставщика исчерпаны, исключаем его из рассмотрения.  Распределяя запасы получаем план:

bj аi	44	64	62	12	90
102	10 44	11 58	9	6	8
6	11	12 6	9	7 0	10
94	10	8	7 62	7 12	8 20
70	0	0	0	0	0 70

 

Полученное решение _{Ошибка! Объект не может быть создан из кодов полей редактирования.} должно иметь m+n - 1=4 + 5— 1 = 8 занятых клеток. В данном случае решение имеет 7 занятых клеток, добавим произвольно нулевую перевозку  х₂₄=0.

Вычислим значение целевой функции на этом опорном решении

 f(X₁) = 44×10 +58×11+6×12 + 0×7 + 62×7+12×7 + 20×8+0×70 = 1828.

Для проверки оптимальности опорного решения необходимо найти  потенциалы занятых клеток по формуле u_i+v_j=c_ij.

Записываем систему уравнений  для нахождения потенциалов:

u₁+v₁=10

u₁+v₂=11

u₂+v₂=12

u₂+v₄=7

u₃+v₃=7

u₃+v₄=7

u₃+v₅=8

u₄+v₅=0

Система состоит из 8 уравнений и имеет 9 переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть u₃=0. Остальные потенциалы находятся однозначно:

bj аi	44	64	62	12	90	u
102	10 44	11 58	9	6	8	0
6	11	12 6-	9	7 0+	10	1
94	10	8 +	7 62	7 12-	8 20	1
70	0	0	0	0	0 70	-7
v	10	11	6	6	7

 

Проверяем опорное решение  X₁ на оптимальность. С этой целью вычисляем оценки D_ij для всех незаполненных клеток таблицы:

D₁₃=u₁+v₃-c₁₃=0+6-9=-3

D₁₄=u₁+v₄-c₁₄=0+6-6=0

D₁₅=u₁+v₅-c₁₅=0+7-8=-1

D₂₁=u₂+v₁-c₂₁=1+10-11=0

D₂₃=u₂+v₃-c₂₃=1+6-9=-2

D₂₅=u₂+v₅-c₂₅=1+7-10=-2

D₃₁=u₃+v₁-c₃₁=1+10-10=1

D₃₂=u₃+v₂-c₃₂=1+11-8=4

D₄₁=u₄+v₁-c₄₁=-7+10-0=3

D₄₂=u₄+v₂-c₄₂=-7+11-0=4

D₄₃=u₄+v₃-c₄₃=-7+6-0=-1

D₄₄=u₄+v₄-c₄₄=-7+6-0=-1

Решение не оптимально, так как D₃₁, D₃₂, D₄₁, D₄₂>0

Построим цикл для клетки (3,2)

Определяем величину груза _q, перераспределяемого по циклу. Она равна значению наименьшей из перевозок в клетках цикла, отмеченных знаком «-»,_q= min{6, 12} = 6. Осуществляем сдвиг по циклу на величину _q = 6. Получаем второе опорное решение _{Ошибка! Объект не может быть создан из кодов полей редактирования.}

bj аi	44	64	62	12	90	u
102	10 44	11 58-	9	6 +	8	0
6	11	12	9	7 6	10	-3
94	10	8 6+	7 62	7 6-	8 20	-3
70	0	0	0	0	0 70	-11
v	10	11	10	10	11

 

Вычисляем значение целевой функции  на втором опорном решении:

f(X₂)= 44×10 +58×11+6×7 + 6×8+ 62×7+6×7 + 20×8+70×0 = 1804.

Проверяем опорное решение  X₂ на оптимальность.

D₁₃=u₁+v₃-c₁₃=0+10-9=1

D₁₄=u₁+v₄-c₁₄=0+10-6=4

D₁₅=u₁+v₅-c₁₅=0+11-8=3

Построим цикл для клетки (1,4). Определяем величину груза _q, перераспределяемого по циклу. _q= min{6, 58} = 6. Осуществляем сдвиг по циклу на величину _q = 6. Получаем третье опорное решение Х₃

bj аi	44	64	62	12	90	u
102	10 44	11 52-	9	6 6	8 +	0
6	11	12	9	7 6	10	1
94	10	8 12+	7 62	7	8 20-	-3
70	0	0	0	0	0 70	-11
v	10	11	10	6	11

f(X₃)= 44×10 +52×11+6×6 + 6×7+ 12×8+62×7 + 20×8+70×0 = 1780.

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

D₁₃=u₁+v₃-c₁₃=0+10-9=1

D₁₅=u₁+v₅-c₁₅=0+11-8=3

D₂₃=u₂+v₃-c₂₃=1+10-9=2

D₂₅=u₂+v₅-c₂₅=1+11-10=2

Построим цикл для клетки (1,5). Определяем величину груза _q, перераспределяемого по циклу. _q= min{20 52} = 20. Осуществляем сдвиг по циклу на величину _q = 20. Получаем опорное решение Х₄

 

 

 

 

 

bj аi	44	64	62	12	90	u
102	10 44	11 32-	9	6 6	8 20+	0
6	11	12	9	7 6	10	1
94	10	8 32	7 62	7	8	-3
70	0	0 +	0	0	0 70-	-8
v	10	11	10	6	8

f(X₄)= 44×10 +32×11+6×6 + 20×8+ 6×7+32×8 + 62×7+70×0 = 1720.

D₁₃=u₁+v₃-c₁₃=0+10-9=1

D₄₁=u₄+v₁-c₄₁=-8+10-0=2

D₄₂=u₄+v₂-c₄₂=-8+11-0=3

D₄₃=u₄+v₃-c₄₃=-8+10-0=2

Построим цикл для клетки (4,2). Определяем величину груза _q, перераспределяемого по циклу. _q= min{32 70} = 32. Осуществляем сдвиг по циклу на величину _q = 32. Получаем опорное решение Х₅

bj аi	44	64	62	12	90	u
102	10 44-	11	9	6 6	8 52+	0
6	11	12	9	7 6	10	1
94	10	8 32	7 62	7	8	0
70	0 +	0 32	0	0	0 38-	-8
v	10	8	7	6	8