ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.04.2024
Просмотров: 218
Скачиваний: 0
кие Xj, при которых для перевозоки груза Qj потребовалось бы наименьшее количество вагонов. Задача может быть сформулирована в эквивалентной форме: требуется найти такие Xj, которые бы максимизировали суммарное количество груза в вагоне. В такой формулировке она более удобна для решения и может быть записана следующим образом:
R* = m ax 2 Xj, |
(П .2) |
Xj /= 1 если на Х) наложены следующие ограничения:
|
|
X j ^ |
0; |
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
(ІІ.З) |
|
|
m |
|
|
|
|
|
_ |
/ = |
1 |
т |
т |
|
|
2 Q j — Q j 2 x j , |
(11.4) |
|||||
QJ |
т |
X j |
||||
|
|
|
/ = і |
/ = і |
|
1j
/= I
где Р — грузоподъемность вагона; V — вместимость вагона;
Уі — объемный вес груза /.
Первое ограничение системы (ІІ.З ) Еытекает из физического смысла задачи. Второе и третье соответственно означают, что суммарное количест во груза должно быть не больше грузоподъемности и вместимости вагона; и, наконец, ( I I .4) имеет тот смысл, что общее количество груза, погружен
ное |
в вагоны, равно его наличию на грузовом пункте. Д ва последних усло |
вия |
(ІІ.З ) в некоторых случаях альтернативны и могут быть заменены ра |
венствами. Задача решается |
методами линейного программирования. |
|
|||
V = |
Пример. На грузовой пункт подают четырехосные крытые вагоны вместимостью |
||||
120 |
ж3 |
и грузоподъемностью Р = 62 т. Удельная грузоподъемность |
вагона |
||
^ в = |
■ |
= |
0,51 m/ж3. |
|
|
|
На складе в наличии <?г = |
150 т груза с объемным весом у, = 0,3 т/м3, 0 2 = |
180 т |
с объемным весом у2 = 0,45 т/м3, Q3 — 300 т c y s = 0,6 т/м3. Требуется найти такие Xj (j = 1, 2, 3), чтобы при совместной перевозке всех трех родов груза в одном вагоне максимизировать функционал (П.2). После подстановки числовых значений в формулы (II.2)—(II.4) получим
R = Хі^[-Х2-)гХз, |
(11.5) |
Хх-ф-лга-ф-Хз 62; |
(11.6) |
Ü2
* L + |
_ 5 L + |
_ 5 L < 1 2 0 или |
2хх 1,3х2ф-х3 < |
72. |
(ІІ.7) |
||
0 , 3 |
0 , 4 5 ^ 0 , 6 |
|
|
|
|
||
6 3 0 х і = |
1 5 0 |
(хх~ р х2 ■р х3) |
» |
3 , 2 л,'і — ,ѵ2 —]*з = |
0 ; |
|
|
630х2= |
1 8 0 |
(ххФ - *2+ * з ) |
» |
2 , 5 х , — * і — * з = |
0 ; |
(II .8) |
|
6 3 0 * з = |
3 0 0 |
( * і + * 2 + * з ) |
» |
1 , 1 х 3 — х2—* і = 0 ; |
|
||
|
|
|
* і , 2 ,3 |
^ |
0 . |
|
|
где хх, х2, х3 — соответственно количество грузов с объемным весом уі, у2, 7з. |
погру |
женных в один вагон.
Последнее равенство системы (II.8) излишне, так как оно является линейной ком
бинацией первых двух. Таким образом остаются следующие условия |
|
|||
2.ѵ'і -(-1, Зх2-ф-*3 |
С 72; |
|
||
3 ,2х3 |
х2 |
х3= |
[0, |
|
2 ,5X2 —хх—х3 — 0; |
(ІІ.9) |
|||
*і х2-\-х3 < 62; |
|
|||
|
* 1 .2 .3 |
^ 0 - |
|
|
Найти оптимальные значения |
хх, х2 |
и х3, максимизирующих линейную |
форму |
(II.5) с учетом ограничений (II.6)—(И .8), относительно просто. Можно дать и графи ческую интерпретацию процесса решения.
Из равенств (II.9) получим, что х2 = 1,2 хх. Воспользовавшись последним соотно шением, запишем:
R — 2 , 2 x x - j - x 3\ |
11 10 |
|||
( |
. ) |
|||
3 , 56л; L -[■-T;j '5 72; |
|
|
||
2 х х — х 3 = |
0; |
(11,11) |
||
2 , 2 х х ± х 3 < 62; |
||||
|
|
|||
* і . * з < |
0 . |
|
|
|
Третье условие системы (11.11) менее сильное, чем остальные два, и его можно |
||||
опустить. Теперь процесс поиска изобразим на фазовой плоскости хх, ох3 |
(рис. |
1), |
||
где показаны проекции горизонтальных сечений поверхности R = 2,2 хх + |
х3 и ли |
|||
ний ограничения |
|
|
|
|
3,56 хх-±-х3< 72 |
( 11. 12) |
|||
и |
|
|
|
|
2 *і—* 3 = 0; |
(11.13) |
|||
* і , з |
0 . |
|||
|
|
Так как по условию функция цели возрастает с увеличением хх и х3, одной из линий ограничения является прямая 3,56 хх + х3 = 72. Таким образом, точка, коор динаты которой представляют оптимальные значения хх и х3, принадлежит линиям
23
2xt — х3 = |
0 и 3,56 л*]-1- л'з = 72, |
т. |
е. находится на их |
пересечении. Решая совмест |
||
но два последних уравнения, получим: |
|
|
|
|||
X*! = |
12,8 т, х*3 = 25,6 m и х*2 = |
1,2 х*г = |
15,4 т, откуда R* = 53,8 т. |
|||
Потребное число вагонов: |
|
|
|
|
|
|
при совместной перевозке легковесных и тяжеловесных грузов |
||||||
|
д,С _ |
Q1 + Q2 + Q3 _ 630 |
^ |
|
||
|
1 |
|
R* |
53,8 |
— |
’ |
при раздельной перевозке |
|
|
|
|
|
|
|
Л'Р = |
Уі |
У |
Уз > V |
£е? |
13. |
|
|
|
|
Экономия вагонов
NP—N\ 13—12
£*8,3% .
12
Задача 2. Д анная задача от предыдущей отличается более общей по становкой: на грузовой пункт подается несколько і (і = 1, 2, ..., п) типов вагонов. Необходимо найти такие = 1, 2, ..., т), которые минимизи ровали бы количество вагонов для перевозки заданного количества груза.
Естественно, если объемный вес грузов равен или больше удельной грузоподъемности вагонов, т. е. грузоподъемность вагонов используется полностью в любом случае, выбор оптимальной схемы загрузки теряет вся кий смысл. Когда общее количество порожних вагонов вполне достаточно для перевозки имеющихся грузов, но накладываются ограничения на число вагонов каждого типа nlt поставленная задача математически формулирует ся следующим образом:
|
|
п |
т |
|
= |
ш ах |
2 2 х и, |
(11.14) |
|
если |
xij |
|
|
|
|
|
|
|
|
1, |
2. |
. л; |
/= 1, 2, .. . , m); |
(11.15) |
|
т |
|
|
|
|
/= I |
|
|
(11.16) |
|
|
|
|
|
|
т X- |
|
|
(11.17) |
|
|
|
|
|
|
п |
|
|
|
2 ІЦ х и > |
Q). |
(И -18) |
||
і= 1 |
|
|
|
24
Задача |
сформулирована в тер |
|
|
|
|
|
|
|
||||||||
минах |
линейного |
программирова |
|
|
|
|
|
|
|
|||||||
ния. Заклю чается она в поиске оп |
|
|
|
|
|
|
|
|||||||||
тимальных |
значений хң, |
максими |
|
|
|
|
|
|
|
|||||||
зирующих |
линейный |
функционал |
|
|
|
|
|
|
|
|||||||
(11.14) |
при |
соблюдении |
ограниче |
|
|
|
|
|
|
|
||||||
ний (11.15)— (11.18). |
|
|
|
|
|
|
|
|
|
|
|
|||||
Смысл |
|
ограничений |
(11.16), |
|
|
|
|
|
|
|
||||||
(11.17) указан ранее. У словие (11.18) |
|
|
|
|
|
|
|
|||||||||
означает что количество груза /, |
Рис. |
1. |
Графическая модель |
поиска |
опти |
|||||||||||
которое |
может |
быть |
погружено в |
мальной |
схемы загрузки вагона |
при доста |
||||||||||
вагоны |
всех |
і |
типов, больше |
или |
точном |
количестве порожних |
вагонов |
|||||||||
|
|
|
|
|
|
|
||||||||||
равно наличию этого груза на |
|
|
|
|
налагаемых |
|||||||||||
складе. |
Чтобы |
уточнить |
вид |
функционала |
и |
ограничений |
||||||||||
на Xjj, воспользуемся следующими исходными данными. |
|
|
|
|||||||||||||
Пусть |
имеется |
количество порожних вагонов |
грузоподъемностью |
Я, — 62 т |
||||||||||||
и вместимостью |
Ѵі = |
90 м3, пг = |
3 единицы; грузоподъемностью Р2 = |
62 т, вмести |
||||||||||||
мостью Ѵ2 = |
108 м3, п2 = |
8 единиц. Количество груза с объемным весом ^ |
= 0,3 |
т/м3 |
||||||||||||
Qi = 150 т, у 2 = |
0,75 т/м3 |
Q2 = |
300 т. Подставив числовые значения в выражения |
|||||||||||||
(II .14)—(11.18), |
после преобразований получим |
|
|
|
|
|
||||||||||
если |
|
|
|
|
|
|
R —Хц 4-XJ2 -ф"Х2і -\-х22, |
|
|
(11.19) |
||||||
|
|
|
|
|
* ,/ > 0; |
Qij > 0 (г = |
1,2; |
/= 1 ,2 ); |
|
(11.20) |
||||||
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
Хц |
|
62, |
х2і~\~х2п |
62; |
|
(11.21) |
||||
|
|
|
|
~ : - Ь |
|
< 90 |
или |
2 ,5 х и +Хіг < 67,5; |
|
|
|
|||||
|
|
|
|
0,3 |
0,7о |
|
|
|
|
|
|
|
|
(11.22) |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
—^ -4 -—— < 1 0 8 |
или |
2,5*21.+*оо < 81; |
|
|
|
|||||||
|
|
|
|
0,3 |
0,75 |
|
|
|
2 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
Ъхц 4-8.ѵ21 > |
150; |
|
|
(И.23) |
||||
|
|
|
|
|
|
|
|
3*12+8*,2 > |
300. |
|
|
(11.24) |
||||
Так как объемный вес груза (?2, равный у 2 = |
0,75 т/м3, больше удельной грузо |
|||||||||||||||
подъемности |
вагонов того и другого |
типа (он |
равен |
соответственно 0,68 |
и 0,58), то |
чтобы не перегрузить последние, в системе ограничений целесообразно сохранить усло вия (11.21) и (11.22). Функционал (11.19) и условие (II.24) линейны, поэтому задача решается методами линейного программирования. Если ограничений на количество вагонов каждого типа нет, из системы ограничений исключают условия (11.23) и (11.24). В этом случае, чтобы лучше использовать грузоподъемность и вместимость, подби рают такой тип вагона, удельная грузоподъемность Р которого приближается к сред невзвешенному объемному весу грузов уср, т. е. уср > Р.
25
. Содержание данной задачи сходно с задачей 1. Отличием ж е является фиксированное число вагонов, подаваемых на грузовой пункт, которое может быть недостаточно для погрузки. Поэтому вместо ограниче ний вида
тт
%і 2 |
Qi —Q} £ х] |
(11.25) |
|
/= 1 |
|
/= 1 |
|
вводится условие |
|
|
|
|
nxj |
Qj. |
(11.26) |
Это условие означает, что наличие на грузовом фронте груза Qj больше или равно количеству груза /, погруженного в поданные вагоны. Ограниче ние полностью соответствует реальным условиям работы грузовой станции. Чтобы решить числовой пример, воспользуемся исходной информацией задачи 1. Дополнительная информация — число поданных вагонов на гру зовой пункт п = 7. Функционал записывается следующим образом:
т |
|
R ^ n ' Z t X j . |
(11.27) |
/= 1 |
|
Т ак как в условии задачи нет дополнительных ограничений в отноше нии приоритета при отправлении какого-либо груза из трех родов, имею щ ихся на грузовом пункте, для увеличения R целесообразно вагоны исполь зовать под грузы с наибольшим объемным весом Qx и Q2. Однако при реали зации такой схемы загрузки и использовании вместимости возможна пере грузка вагона. Поэтому, кроме условия (11.7), необходимо сохранить огра ничения вида ( I I .6) и условие
nxj ^ |
Qj. |
(11.28) |
|
Подставив числовые значения в выражения (II.3), |
(11.27), (11.28), получим |
||
R = 7 (А-'і+^гД-Хз)' |
(11.29) |
||
если хЬі!із > 0 ; |
|
|
* |
|
|
^ 62; |
(11.30) |
2х± -f- 1, 33х2 |
£ 3 ^ 72; |
(11.31) |
|
х± < |
21,4; |
(11.32) |
|
х2 < |
26; |
(И .33) |
|
*з « |
43. |
(11.34) |
|
Найти оптимальные значения хі (/ = |
1, 2, 3), которые максимизируют линейную |
форму (11.29), можно методами линейного программирования. Графическая интерпре-
26