ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.04.2024
Просмотров: 223
Скачиваний: 0
тация решения |
задачи |
показана на |
рис. 2. Из него |
следует, |
что оптималь |
ное решение следует искать в наиболее удаленной от начала координат точке— одной из вершин многогранника М. Эта
точка лежит |
на пересечении плоскостей |
||||||||
*і + * 2 |
+ |
*з = |
62, |
2*! + |
1,33 * 2 |
|
х3= |
||
— 72 |
и |
*з = |
43. |
|
Уменьшим |
размер |
|||
ность |
задачи, |
исключив |
из |
системы |
|||||
(11.29)—(11.31) |
переменную х х. |
|
|
||||||
Тогда |
|
7 (36 + 0,34х2 + |
0,5х3), |
(11.35) |
|||||
Р = |
|||||||||
если |
|
|
|
*2, |
*3 > 0; |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
* ,< 2 6 ; |
|
(11.36) |
|||
|
|
|
|
*з < |
43; |
|
(11.37) |
||
|
|
|
0,67*2+ |
*з = 52. |
(11.38) |
||||
Заметим, |
что |
условия *а + *з |
< |
62 и |
|||||
1,33 * 2 |
+ |
*з |
< |
72 |
менее |
сильные, |
чем |
||
остальные, |
и |
поэтому их можно опус |
|||||||
тить. |
|
|
|
|
|
|
|
|
|
На рис. 3 в координатах *2, *3 по строены проекции линий равных сечений
функционала |
(11.32) |
и ограничиваю |
щие прямые, |
определяемые условиями |
|
(11.36)—(11.38). Так |
как с увеличением |
|
* 2 и *з возрастает R, |
оптимальные зна |
|
чения х* 2 и х*з следует искать в грани
цах .многоугольника |
МгМ 2М 3 М4М6 в |
точке, расположенной |
на наиболее уда |
ленной от начала координат горизонта ли. Нетрудно заметить, что такой точкой является ЛД. Для решения задачи необ
ходимо совместно |
решить |
уравнения |
|||||
0,67 * 2 |
+ |
*з = |
52 |
и *з = 43. В резуль |
|||
тате чего получим х*2 = |
13,5, х*3 = |
43, |
|||||
**} = |
5,5. При |
этом легковесного груза |
|||||
будет |
перевезено |
7 - 5 , 5 = |
38,5 гп и |
||||
13,5-7 = |
94,5 т, тяжеловесного 7-43 = |
||||||
= 300 т. |
Остаток |
на |
складе составит |
||||
(150 — 38,5) + |
(180 — 94,5) = 196 |
т. |
|||||
При раздельной |
загрузке тяжеловесных |
||||||
и легковесных грузов для перевозки
394,5 |
т потребовалось |
бы 8 вагонов |
||
( 300 |
, |
94,5 , |
38,5) |
^ |
^-ß2 ~ |
+ |
“5 4 ~ "г |
"Зб/ - |
Экономия соста |
вит 14%,
Задача 4. Данная задача отли чается от задачи 2 фиксированным
Рис. 2. Графическая модель поиска опти мальной схемы загрузки вагона в трехмер ном пространстве
Рис. 3. Графическая модель поиска опти мальной схемы загрузки вагона
27
числом вагонов каждого типа, общее количество которых может быть недо статочно для перевозки всех грузов. Функционал — количество груза, погруженного в поданные вагоны, — записывается следующим образом:
п т
Я = |
2 «г |
2 |
х и . |
|
(11.39) |
Ограничения: х и ^ 0 ; |
і= і |
/=1 |
|
|
|
|
|
|
|
|
|
п |
щ х и < |
Qj. |
|
|
|
2 |
|
(11.40) |
|||
«■=1 |
|
|
|
|
|
|
|
|
|
|
(11.41) |
/' |
|
|
|
|
|
где п; представляет собой количество вагонов типа і |
(і = 1, 2, |
..., /г). Зада |
|||
ча состоит в том, чтобы найти такие х и , |
которые бы максимизировали ли |
||||
нейную форму (11.39) при соблюдении |
ограничений |
(11.40) и |
(11.41). Опти |
||
мальные решения находят методом линейного программирования. Допол нительное ограничение (11.40) имеет тот смысл, что количество груза, за груженное в поданные вагоны, не должно превосходить наличия гурза на
складе. |
|
|
|
|
|
|
|
|
|
|
Пример. На грузовой |
пункт поданы вагоны двух типов (і = |
1; 2): четырехосные |
||||||||
грузоподъемностью Рг = 62 т с объемом кузова |
Д = 90 м3 в количестве щ = |
4 еди |
||||||||
ниц и четырехосные грузоподъемностью Р2 — 62 т,Ѵ2= 108 |
м3 в количестве |
п2= 3 |
||||||||
единиц. На складе имеется Qj = 150 т груза с объемным весом Уі |
= |
0,3 т/м3 и Р2 = |
300 т |
|||||||
груза с объемным весом у2 = |
0,6 т/м3 (/ = |
1,2). Подставив числовые значения |
в вы |
|||||||
ражения |
(11.39)—(11.41), |
получим |
|
|
|
|
|
|
||
|
|
^ |
— 4 (хи -)- х 12) -р- 3 (х21 -|- X 22) . |
|
|
(11.42) |
||||
Ограничения: |
|
|
> 0; |
|
|
|
|
|
|
|
|
|
|
4хи -р З.ѵ21 < |
150; |
*| |
|
|
(11.43) |
||
|
|
|
4л'і2 -[- Зх22 < |
300: |
j |
|
|
|||
|
|
|
|
|
|
|||||
|
|
|
2х„ - j -Л'р2 < |
54; |
|
|
|
(11.44) |
||
|
|
|
^X2i~juX22 < |
64,8; |
|
|
|
|||
|
|
|
|
|
|
|
||||
|
|
|
|
Хп Д а'і2 < |
62; |
|
|
|
(11.45) |
|
|
|
|
|
x2j -j^ x22 < |
62. |
|
|
|
||
|
|
|
|
|
|
|
|
|||
Из двух |
ограничений Хц + |
|
х12 < |
62 и 2хп + х12 < 54 второе |
более сильное. По |
|||||
этому остается следующая |
система |
ограничений: |
|
|
|
|
||||
28
4'^ц~Ф" 3j^2i |
150; 1 |
|
(11.46) |
4x^2-ф-ЗлГчо ^ 300; )
(11.47)
< 64,8; J
^ 2 1 "Ф^"22 ^ 62; "I
(II .48)
хіі ^ 0. J
Для решения поставленной задачи воспользуемся симплекс-методом и для этого приведем ее к виду основной задачи линейного программирования, заменив неравен ства (11.46)—(11.48) равенствами:
Уі = — 4*ц — 3*2і + 150; |
|
|
у%— — |
“Н 300; |
(11.49) |
У з ~ — 2*п — *12 + 54,0; |
||
Уі = — 2*2і —*,2 + 64,8; |
|
|
|
|
Уъ— — *21— *22+ 62; |
|
|
|
||||||||
|
|
max R = |
4 (*ц + |
*і2) + |
3 (*2і + * 2 2 ), |
|
|
(11.50) |
|||||
где ух — у ъ — искусственно введенные в систему (11.49) переменные: |
|
|
|||||||||||
ух и у 2 — остаток |
груза |
на |
складе |
после |
загрузки |
вагонов; |
|
|
|||||
Уз и ft — недоиспользованные |
объемы вагонов; |
|
|
|
|||||||||
у ъ — недоиспользованная часть грузоподъемности вагона. |
|
|
|||||||||||
Число неизвестных |
системы т = |
9; ранг |
системы г = |
5. При т^> г совместная |
|||||||||
система имеет |
бесчисленное множество |
решений, среди |
которых требуется |
найти |
|||||||||
оптимальное, |
максимизирующее |
R. |
|
|
|
|
|
|
|
|
|
|
|
Выберем начальное базисное решение. В качестве его примем такое решение, |
|||||||||||||
базис которого состоит из единичных векторов. В |
матрице |
базисными |
неизвестными, |
||||||||||
отвечающими |
принятому |
условию, |
соответствуют |
переменные ух, у 2, |
.... Уз- |
Коэф |
|||||||
фициенты при этих неизвестных образуют отличный от нуля базисный минор |
|
||||||||||||
|
|
|
( |
1 |
0 |
0 |
0 |
0 |
4 |
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
0 |
0 |
1 |
|
|
|
|
|
|
|
0 |
0 |
1 |
|
0 |
0 |
= 1. |
|
|
|
|
|
|
|
0 |
0 |
0 |
|
1 |
0 |
/ |
|
|
|
|
|
|
|
0 |
0 |
0 |
|
0 |
1 / |
|
|
|
|
Перепишем систему (11.49) и функционал (11.50) в табл. 1, которая дает опорное |
|||||||||||||
решение. |
Чтобы |
отыскать оптимальное решение, следует преобразовывать таблицу до |
|
тех пор, |
пока все коэффициенты Д-строки будут неотрицательны. На первом |
шаге: |
|
в качестве |
разрешающего выбираем столбец, содержащий наибольший по |
абсо |
|
лютной величине отрицательный коэффициент Д-строки: [—*і2 — столбец]; отбираем все положительные коэффициенты этого столбца и делим на них соот
ветствующие свободные члены; строка у 3 с наименьшим по величине отношением будет разрешающей:
54 < 75;
29
Т а б л и ц а 1
Дополнитель |
|
Коэффициенты при переменных |
|
Свободные |
|
ные перемен |
|
|
|
|
члены урав |
ные |
Г ц |
— А '1 В |
— А 'а і |
----- * 2 Я |
нений (11.49) |
— |
|
||||
1 |
4 |
0 |
3 |
0 |
150 |
У |
|
|
|
|
|
Уг |
0 |
4 |
0 |
3 |
300 |
Уз |
2 |
ш |
0 |
0 |
54 |
Уі |
0 |
0 |
2 |
1 |
64,8 |
Уъ |
0 |
0 |
1 |
1 |
62 |
R |
—4 |
—4 |
—3 |
—3 |
0 |
элемент, находящийся одновременно в разрешающих столбце и строке, является разрешающим. В табл. 1 он обозначен так Ш. После первого шага знак коэффициента /^-строки разрешающего столбца станет положительным, так как при преобразовании
таблицы по правилам |
модифицированного Жорданова исключения: |
|
|
|
|||||
разрешающий элемент |
заменяется единицей; |
|
|
|
|
|
|||
остальные элементы разрешающей строки остаются без изменения; |
|
|
|||||||
остальные элементы разрешающего столбца меняют знаки. |
|
принадлежащие |
|||||||
Все эти преобразования отражены в табл. 2. Элементы öj;-, не |
|||||||||
к разрешающей строке г и |
столбцу s в |
табл. 1, вычисляют, |
используя |
данные |
|||||
табл. 2, |
по формуле |
a-tj ars — a.isarj. Пример расчета показан |
в табл. 3 |
и 4. |
|||||
В результате таких расчетов |
получаем табл. 5. Все элементы ее делим на разре |
||||||||
шающий элемент ars и после первого |
шага получаем табл. 6. Описанным |
выше |
|||||||
способом |
выполняем |
второй |
шаг (табл. |
7.) После второго |
шага |
получим |
таблицу |
||
8. Процедура третьего шага расчетов показана в табл. 9. |
|
|
|
|
|
||||
Т а б л и ц а 2 |
|
|
|
|
|
|
|
|
|
П ер е м е н н ы е |
— А'і ! |
— А3 |
— А'зі |
— Л*22 |
С во б о д н ы е |
||||
|
член ы |
||||||||
Уі |
— |
0 |
— |
— |
|
|
— |
|
|
У г |
— |
—4 |
— |
— |
|
|
— |
|
|
х и |
2 |
1 |
0 |
0 |
|
|
54 |
|
|
Уі |
— |
0 |
— |
— |
|
|
— |
|
|
Уъ |
— |
0 |
— |
— |
|
|
— |
|
|
R |
|
— |
4 |
— |
|
|
|
|
|
.30
