Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Сибирский Государственный Университет Путей Сообщения

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

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

Скачиваний:

Добавлен:

01.07.2025

Размер:

592 Кб

Скачать

☆

<<< < Предыдущая 1 2 34 / 44

Методические указания к заданию № 3.

В хозяйстве необходимо за время уборки при заготовке силоса перевезти 3600 т зелёной массы с пяти поля к четырём силосным траншеям. Зелёная масса каждого поля равна: А₁= 400, А₂ = 500, А₃ = 700, А₄ = 900, А₅ = 1100 т; вместимости силосных траншей равны: В₁= 1200, В₂ = 600, В₃ = 800, В₄ =1000 т. Оплата за тонну зелёной массы, перевозимую с полей к силосным траншеям, приведена в табл. 26.

Расстояния между полями и приёмными пунктами Таблица 26

Поля	Силосные траншеи
Поля	1-ый	2-ой	3-ий	4-ый
1-е	5	6	2	2
2-е	9	7	4	6
3-е	7	1	4	5
4-е	5	2	2	4
5-е	6	4	3	4

Составить такой план перевозок, чтобы транспортные затраты были минимальными. Опорный план найти методом наименьшего элемента. Оптимальный план найти методом потенциалов.

Решение. Проверим баланс между общим объёмом А зелёной массы, вывозимой с полей и суммарной вместимостью В силосных траншей.

A = a₁+a₂+a₃+a₄+a₅ = 400+500+700+900+1100 = 3600,

В = b₁+b₂+b₃+b₄ = 1200+600+800+1000 =3600.

Так как А = В, то задача является закрытой.

Определим опорный план методом наименьшего элемента. Среди всех оплат за перевозку тонны зелёной массы с полями к силосным траншеям выберем самое наименьшее. Это оплата перевозки между третьим полем и второй силосной траншеей с₃₂=1. Осуществляем поставку в клетку (3;2).

1а	1200	600	800	1000	Остатки
400	⁵	⁶ –	²	²
500	⁹	⁷–	⁴	⁶
700	⁷	¹600	⁴	⁵	100
900	⁵	²–	²	⁴
1100	⁶	⁴–	³	⁴
Остатки		0

Определим объём поставки в эту клетку как минимум из остатка объёма зелёной массы 3 поля и остатка вместимости 2 силосной траншеи. Так как зелёная масса ещё не распределялась, то остатки равны начальным значениям массы и вместимости: 700 и 600 тонн. Минимальным будет остаток 600 т. Поставляем в клетку (3;2) 600 т. Пересчитываем остатки: с 3-го поля осталось перевезти 700 – 600 = 100 т, а остаток вместимости 2-ой силосной траншеи стал равным 600 – 600 = 0. 2-ую силосную траншею вычёркиваем из дальнейшего рассмотрения. Как и во втором задании, будем нумеровать таблицы в левом верхнем углу. Выполненные действия отметим в таблице 1а.

1б	1200	600	800	1000	Остатки
400	⁵–	⁶ –	²–	²400	0
500	⁹	⁷–	⁴	⁶
700	⁷	¹600	⁴	⁵	100
900	⁵	²–	²	⁴
1100	⁶	⁴–	³	⁴
Остатки		0		600

Среди всех оплат за перевозку тонны зелёной массы с полей к силосным траншеям в оставшейся части таблицы выберем минимальное. Это оплаты перевозки с₁₃=2, с₁₄=2 и с₄₃=2. Выбираем клетку (1;4). Определим объём поставки в эту клетку. Перевозки с 1-го поля к 4-той силосной траншее ещё не планировались, то остатки равны: для поля 400 т, для траншеи 1000 т. Минимальным будет остаток 400 т. Поставляем в клетку (1;4) 400 т. Пересчитываем остатки: для 1-го поля: 400 – 400 = 0 т, для 4-ой траншеи: 1000 – 400 = 600 т (табл. 1б). Вычёркиваем 1-ое поле из дальнейшего рассмотрения.

Опять среди всех оплат за перевозку тонны зелёной массы с полей к силосным траншеям в оставшейся части таблицы находим минимальное. Это оплаты перевозки с₄₃=2. Выбираем клетку (4;3). Остатки равны: для поля – 900 т, для

1в	1200	600	800	1000	Остатки
400	⁵–	⁶ –	²–	²400	0
500	⁹	⁷–	⁴–	⁶
700	⁷	¹600	⁴–	⁵	100
900	⁵	²–	²800	⁴	100
1100	⁶	⁴–	³–	⁴
Остатки		0	0	600

траншеи 800 – т. Минимальным будет остаток 800 т. Поставляем в клетку (4;3) 800 т. Пересчитываем остатки: для поля: 900 – 800 = 100 т, для траншеи: 800 – 800 = 0 т

(табл. 1в). 3-ий пункт вычёркиваем из дальнейшего рассмотрения.

1г	1200	600	800	1000	Остатки
400	⁵–	⁶ –	²–	²400	0
500	⁹	⁷–	⁴–	⁶–
700	⁷	¹600	⁴–	⁵ –	100
900	⁵	²–	²800	⁴–	100
1100	⁶	⁴–	³–	⁴600	500
Остатки		0	0	600, 0

1д	1200	600	800	1000	Остатки
400	⁵–	⁶ –	²–	²400	0
500	⁹	⁷–	⁴–	⁶–
700	⁷	¹600	⁴–	⁵ –	100
900	⁵100	²–	²800	⁴–	100, 0
1100	⁶	⁴–	³–	⁴600	500
Остатки	1100	0	0	600, 0

Наименьшая оплата перевозки с₄₄=4, с₅₄=4. Выбираем клетку (5;4).Остатки равны: для поля 1100 т, для траншеи 600 т. Минимальным будет остаток 600 т. Пересчитываем остатки (табл. 1г): для поля 1100 – 600 = 500 т, для траншеи 600 – 600 = 0 т. Вычёркиваем 4-ый пункт.

Минимальная оплата перевозки с₄₁=5. Выбираем клетку (4;1). Остатки равны: для поля–100 т, для траншеи – 1200 т. Минимальным будет остаток 100 т. Делаем поставку в клетку (4;1) в объёме100 т. Пересчитываем остатки: для поля 100 – 100 = 0 т, для траншеи 1200 – 100 =1100 т (табл. 1д). 4-ое поле вычёркиваем из дальнейшего рассмотрения.

1е	1200	600	800	1000	Остатки
400	⁵–	⁶ –	²–	²400	0
500	⁹	⁷–	⁴–	⁶–
700	⁷	¹600	⁴–	⁵ –	100
900	⁵100	²–	²800	⁴–	100, 0
1100	⁶500	⁴–	³–	⁴600	500, 0
Остатки	1100, 600	0	0	600, 0

Оплата перевозки с₅₁=6. Выбираем клетку (5;1). Остатки равны: поле 500 т, траншея – 1100 т. Минимальным будет остаток 500 т. Поставляем в клетку (5;1) 500 т. Остатки: 500 – 500 = 0 т для поля, 1100–500=600 т для

1ж	1200	600	800	1000	Остатки
400	⁵–	⁶ –	²–	²400	0
500	⁹	⁷–	⁴–	⁶–
700	⁷100	¹600	⁴–	⁵ –	100, 0
900	⁵100	²–	²800	⁴–	100, 0
1100	⁶500	⁴–	³–	⁴600	500, 0
Остатки	1100, 600,500	0	0	600, 0

траншеи (табл. 1е). 5-ое поле вычёркиваем.

(табл. 1е). Оплата перевозки с₃₁=7. Выбираем клетку (3;1). Остатки: поле – 100 , траншея – 600 т. Минимальный остаток 100 т. Поставка в клетку (3;1) в объёме 100 т. Пересчитываем остатки: 100 т для поля,

для траншеи 100–100 =500 т (табл. 1ж). 3-е поле вычёркиваем.

1з	1200	600	800	1000	Остатки
400	⁵–	⁶ –	²–	²400	0
500	⁹500	⁷–	⁴–	⁶–	0
700	⁷100	¹600	⁴–	⁵ –	100, 0
900	⁵100	²–	²800	⁴–	100, 0
1100	⁶500	⁴–	³–	⁴600	500, 0
Остатки	1100, 600,500, 0	0	0	600, 0

Осталась последняя клетка, которая не заполнялась, это клетка (2;1). Проверяем баланс остатков: для поля остаток 500, для траншеи 500 т. Баланс есть. Поставляем в клетку остатки зелёной массы и поля и траншеи в размере 500 т и вычёркиваем из рассмотрения и поле, и траншею(табл. 1з).

Мы получили опорный план, построенный методом наименьшего элемента (табл. 1).

1	1200	600	800	1000
400	⁵	⁶	²	²400
500	⁹500	⁷	⁴	⁶
700	⁷100	¹600	⁴	⁵
900	⁵100	²	²800	⁴
1100	⁶500	⁴	³	⁴600

Будем искать оптимальный план. Для этого применим метод потенциалов.

Методом потенциалов оптимальный план будем находить пошагово. На каждом шаге метода осуществляем переход от одного опорного плана к другому, выполняя следующие действия:

1) вычислим потенциалы полей и силосных траншей;

2) вычислим косвенные издержки для свободных клеток;

3) проверим признак оптимальности плана;

4) одну из свободных клеток выбираем для перераспределения зелённой массы;

5) для выбранной клетки строим цикл перераспределения зелёной массы;

6) пометим клетки цикла знаками «+» и «–»;

7) определим объём перераспределения зелёной массы;

8) строим новый опорный план.

Выполняем действие 1). Вычислим потенциалы полей и силосных траншей по заполненным и условно заполненным клеткам.

2а	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	⁴	⁶
700	⁷100	¹600	⁴	⁵
900	⁵100	²	²800	⁴
1100	⁶500	⁴	³	⁴600
v_j				2

Произвольно задаём значение одного из потенциалов, например, положим значение потенциала для первого поля u₁равным нулю.

Рассматриваем первую строку (табл. 2а).

В ней ищем нерассмотренные заполненные и условно заполненные клетки. Это клетка (1; 4).

По этой клетке определяем потенциал 4-ой

силосной траншеи: v₄ = u₁ + c₁₄= 0 + 2 = 2.

Больше нерассмотренных заполненных и условно заполненных клеток в первой строке нет. Переходим к последнему вычисленному потенциалу, к потенциалу v₄ = 2. Это потенциал

2б	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	⁴*	⁶
700	⁷100	¹600	⁴	⁵
900	⁵100	²	²800	⁴
1100	⁶500	⁴	³	⁴600	-2
v_j				2

4-ой силосной траншеи.

Рассматриваем 4-ый столбец (табл. 2б). Находим в этом столбце нерассмотренные заполненные и условно заполненные клетки. Это клетка (5; 4). По этой клетке определяем потенциал 5-ого поля: u₅ = v₄ – c₅₄= 2 – 4 = –2. Больше нерассмотренных заполненных и условно

заполненных клеток в четвёртом столбце нет. Переходим к последнему вычисленному потенциалу, к потенциалу u₅ = –2. Это потенциал 5-ого поля.

2в	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	⁴*	⁶
700	⁷100	¹600	⁴	⁵
900	⁵100	²	²800	⁴
1100	⁶500	⁴	³	⁴600	-2
v_j	4			2

Рассматриваем 5-ую строку (табл. 2в). Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (5; 1). По этой клетке определяем потенциал 1-ой силосной траншеи: v₁ = u₅ + c₅₁= –2 + 6 = 4. Больше нерассмотренных заполненных и условно заполненных клеток в пятой строке нет.

Переходим к последнему вычисленному потенциалу, к потенциалу v₁ = –2. Это потенциал

1-ой силосной траншеи.

2г	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	⁴*	⁶	-5
700	⁷100	¹600	⁴	⁵	-3
900	⁵100	²	²800	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4			2

Рассматриваем 1-ый столбец (табл. 2г). Находим в этом столбце нерассмотренные заполненные и условно заполненные клетки. Это клетки (2; 1), (3; 1) и (4; 1). По этим клеткам определяем потенциалы 2-ого, 3-его и 4-го полей: u₂ = v₁ – c₂₁= 4 – 9 = –5, u₃ = v₁ – c₃₁= 4 – 7 = –3, u₄ = v₁ – c₄₁= 4 – 5 = –1.

Больше нерассмотренных заполненных и условно заполненных клеток в четвёртом столбце нет. Переходим к последним вычисленным потенциалам, к потенциалам u₂ = –5, u₃ = –3 и

u₄ = –1. Это потенциалы 2-ого поля, 3-его поля и 4-ого поля.

Сначала рассмотрим 2-ую строку (табл. 12). Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Таких клеток нет.

Переходим к следующему вычисленному потенциалу, к потенциалу u₃ = –3. Это потенциал 3-его поля.

2д	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	⁴	⁶	-5
700	⁷100	¹600	⁴	⁵	-3
900	⁵100	²	²800	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4	-2		2

Рассматриваем 3-ю строку (табл. 2д). Находим в этой строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (3; 2). По этой клетке определяем потенциал 2-ой силосной траншеи: v₂ = u₃ + c₃₂= –3 + 1 = –2. Больше нерассмотренных заполненных и условно заполненных клеток в третьей строке нет.

2е	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	⁴	⁶	-5
700	⁷100	¹600	⁴	⁵	-3
900	⁵100	²	²800	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4	-2	1	2

Переходим к следующему вычисленному потенциалу, к потенциалу u₄ = –1. Это потенциал 4-тьего поля.

Рассматриваем 4-ую строку (табл. 2е). Находим в этом строке нерассмотренные заполненные и условно заполненные клетки. Это клетка (4; 3). По этой клетке определяем потенциал

2	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	⁴	⁶	-5
700	⁷100	¹600	⁴	⁵	-3
900	⁵100	²	²800	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4	-2	1	2

3-ей силосной траншеи: v₃ = u₄ + c₄₃= –1 + 2 = 1. Больше нерассмотренных заполненных и условно заполненных клеток в четвёртой строке нет.

Мы вычислили все потенциалы. Результаты вычислений представлены таблицей 2.

Переходим к выполнению следующего пункта шага метода потенциалов.

2) вычислим косвенные издержки для свободных клеток, которые обозначим Δ_ij .

Косвенные издержки для свободных клеток вычисляем по формуле: Δ_ij = c_ij – ( v_j – u_i ).

Δ₁₁ = 5 – (4 – 0) = 1 ; Δ₁₂ = 6–(-2–0) =8; Δ₁₃= 2 – (1 – 0) = 1; Δ₂₂=7 – ( – 2+5)= 4;

Δ₂₃ = 4 – (1+5) = – 2; Δ₂₄ = 6–(2+5) = – 1; Δ₃₃ = 4 – (1+ 3) = 0; Δ₃₄= 5 – (2+3)= 0;

Δ₄₂=2–( – 2+1) = 3; Δ₄₄=4–(2+1)=1; Δ₅₂ =4 – (–2+2) = 4; Δ₅₃ = 3 – (1+2) = 0.

3) Проверяем признак оптимальности плана: если для всех свободных клеток косвенные издержки положительные (Δ_ij ≥ 0), то опорный план является оптимальным.

План не оптимальный, так как Δ₂₃ = – 2 < 0 и Δ₂₄ = – 1 < 0.

4) Выбираем клетку для перераспределения зелённой массы. Это одна из клеток таблицы, для которой косвенные издержки строго отрицательные. Выбираем клетку (2;3).

5) Для выбранной клетки (2;3) строим цикл перераспределения зелёной массы.

2ж	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	^{4 *}	⁶	-5
700	⁷100	¹600	⁴	⁵	-3
900	⁵100	²	²800	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4	-2	1	2

Выбранную свободную клетку (2;3) включаем в цикл. Далее рассматриваем строку,

содержащую эту клетку. Это вторая строка. Во второй строке ищем заполненные и условно

2з	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	^{4 *}	⁶	-5
700	⁷100	¹600	⁴	⁵	-3
900	⁵100	²	²800	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4	-2	1	2

заполненные клетки (табл. 2ж). Такие клетки есть, это клетка (2;1). Так как она единственная, то её включаем в цикл (рис. 3а) и переходим к ней.

Рассматриваем столбец, содержащий включённую в цикл клетку (2;1). Это первый столбец. В первом столбце находим нерассмотренные заполненные и условно заполненные клетки. Это клетки (3;1), (4;1) и (5;1) (табл. 2з). Выбираем любую из них, например клетку (3;1). Включаем её в цикл (рис. 3б). Переходим к ней.

Рассматриваем строку, содержащую эту клетку. Это третья строка.

2и	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	^{4 *}	⁶	-5
700	⁷100	¹600	⁴	⁵	-3
900	⁵100	²	²800	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4	-2	1	2

В третьей строке ищем нерассмотренные заполненные и условно заполненные клетки (табл. 2и). Такие клетки есть, это клетка (3;2). Так как она единственная, то её включаем в цикл (рис. 3в) и переходим к ней.

Рассматриваем столбец, содержащий клетку (3;2). Это второй столбец. В столбце находим нерассмотренные заполненные и условно заполненные клетки. Таких клеток нет. Вычёркиваем клетку (3;2) из цикла и переходим к предыдущей клетке цикла, к клетке (3;1) (рис. 3г).

Опять рассматриваем третью строку.

В третьей строке ищем нерассмотренные заполненные и условно заполненные клетки (табл. 2и). Клетки (3;1) и (3;2) уже рассматривались, других клеток нет. Вычёркиваем клетку (3;1) из цикла и переходим к предыдущей клетке цикла, к клетке (2;1) (рис. 3д).

Снова рассматриваем столбец, содержащий клетку (2;1). В первом столбце находим нерассмотренные заполненные и условно заполненные клетки. Это клетки (4;1) и (5;1), клетки (2;1) и (3;1) уже рассматривались (табл. 2з). Выбираем любую из них, например клетку (4;1). Включаем её в цикл (рис. 3е). Переходим к ней.

2к	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹500	⁷	^{4 *}	⁶	-5
700	⁷100	¹600	⁴	⁵	-3
900	⁵100	²	²800	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4	-2	1	2

Рассматриваем строку, содержащую клетку (4;1). Это четвёртая строка (табл. 2к). В этой строке есть заполненная клетка, которая располагается в том же столбце, что и начальная клетка цикла, клетка (2; 3). Это клетка (4; 3). Автоматически её включаем в цикл, и цикл замыкаем (рис. 3е).

Построенный цикл для свободной клетки (2; 3) изображён на рисунке 3ж.

6) Пометим клетки цикла знаками «+» и «–». Помечать клетки цикла начнём со свободной клетки цикла, клетки (2; 3). Её пометим знаком «+». Далее, двигаясь по циклу в направлении его построения, помечаем остальные клетки цикла, чередуя знаки (рис. 4).

К летку (2; 1) пометим знаком «–», клетку (4;1) знаком «+», клетку (4;3) знаком «–». В клетки, помеченные знаком «+» зелёную массу будем добавлять, а из клеток, помеченных знаком «–» зелёную массу будем забирать. Клетками, откуда зелёная масса забирается, будут (2;1) и (4;3).

7) Определим объём перераспределения зелёной массы.

О бъём перераспределения зелённой массы ΔV равняется наименьшему из объёмов отрицательных клеток цикла. В клетке (2; 1) объём поставки зелёной массы равняется 500 т, а в клетке (4;3) – 800 т (рис. 5). Поэтому объём перераспределения зелёной массы ΔV равен: ΔV = min500; 800= 500 т.

8) Строим новый опорный план.

Сначала пересчитываем объёмы зелёной массы для клеток цикла (табл. 3): для клетки (2; 3) новый объём равен

x₂₃ = 0 + 500 = 500 т, для клетки (2; 1) новый объём равен x₂₁ = 500 – 500 = 0 т, для клетки (4; 1) новый объём равен x₄₁ = 100 + 500 = 600 т, для клетки (4; 3) новый объём равен x₄₃ = 800 – 500 = 300 т.

3	1200	600	800	1000	u_i
400	⁵	⁶	²	²400	0
500	⁹	⁷	⁴500	⁶	-3
700	⁷100	¹600	⁴	⁵	-3
900	⁵600	²	²300	⁴	-1
1100	⁶500	⁴	³	⁴600	-2
v_j	4	-2	1	2

Объём клетки (2; 1) стал равным нулю, её переводим в ранг свободных, а клетку (2; 3) переводим в ранг заполненных. Объёмы остальных клеток таблицы, не вошедших в цикл, не меняются: x₁₄ = 400, x₃₁ = 100, x₃₂ = 600, x₅₁ = 500, x₅₄ = 600 (табл. 3). Шаг метода потенциалов закончен.

Переходим к новому шагу. В качестве опорного рассматриваем план, соответствующий таблице 3.

1) Вычислим потенциалы полей и силосных траншей (табл. 3).

2) Вычислим косвенные издержки для свободных клеток:

Δ₁₁ = 5 – (4 – 0) = 1 ; Δ₁₂ = 6 – ( – 2 – 0) = 8; Δ₁₃ = 2 – (1 – 0) = 1; Δ₂₁ = 9 – (4+3) = 2;

Δ₂₂ = 7 – ( – 2+3) = 6; Δ₂₄= 6 –(2+3) = 1; Δ₃₃= 4–(1+3) = 0; Δ₃₄= 5–(2+3) = 0; Δ₄₂=2–( – 2 +1) = 3;

Δ₄₄ = 4 – (2+1) = 1; Δ₅₂= 4 – (– 2+2) = 4; Δ₅₃= 3 – (1+2) = 0.

3) Проверим признак оптимальности плана.

План оптимальный, так как для всех свободных клеток косвенные издержки больше либо равны нуля (Δ_ij ≥ 0).

По таблице 3 выписываем оптимальный план:

X* = .

Для оптимального плана рассчитываем суммарные транспортные издержки:

Z_min = 2∙400 +4∙500 +7∙100 +1∙600 +5∙600+ +2∙300 +6∙500 +4∙600 = 13100.

Выписываем ответ: X* = ; Z_min= 13100.

<<< < Предыдущая 1 2 34 / 44

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
18.09.2019239 Кб10Методичка по практике.doc
#
01.07.2025996 Кб1Методичка по тепловым излучениям.doc
#
22.08.20195 Мб32Методичка тех.нормы..doc
#
17.04.2015722 Кб108методичка_практика_посл.doc
#
01.03.20252 Мб6методичка. Курсоваяработа по маркетингу.doc
#
01.07.2025592 Кб3Методы оптимальных решений. Контрольные работы...doc
#
01.07.2025309 Кб1Метрология РГР.docx
#
01.07.2025424 Кб5Метрология, стандартизация и сертификация.doc
#
17.04.2015164 Кб19метрология.doc
#
31.08.20191 Мб7метрология.docx
#
01.08.2019225 Кб28Механика Грунтов.docx