Реферат: Статические модели задачи размещения
РЕФЕРАТ
Статические модели задачи размещения.
Самара, 2006
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;letter-spacing:.05pt;mso-ansi-language:RU; mso-fareast-language:RU;mso-bidi-language:AR-SA;mso-bidi-font-weight:bold">Производственно-транспортные задачиоптимального размещения предприятий и применимость метода последовательныхрасчетов
1.<span Times New Roman"">
Задача размещения предприятий с ограниченными объемами производства.Имеется ппунктов потребления с заданными объемами потребления <img src="/cache/referats/23638/image002.gif" v:shapes="_x0000_i1025"> и mпунктов производства (предприятий) с неизвестными, ограниченнымисверху объемами производства <img src="/cache/referats/23638/image004.gif" v:shapes="_x0000_i1026">.Для каждого <img src="/cache/referats/23638/image006.gif" v:shapes="_x0000_i1027"> заданы величины <img src="/cache/referats/23638/image008.gif" v:shapes="_x0000_i1028"> — постоянные затраты(капиталовложения), не пропорциональные объему производства <img src="/cache/referats/23638/image010.gif" v:shapes="_x0000_i1029"> необходимые, например,для строительствапредприятий <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1030"><img src="/cache/referats/23638/image014.gif" v:shapes="_x0000_i1031">, где <img src="/cache/referats/23638/image016.gif" v:shapes="_x0000_i1032"> — стоимость перевозкиединицы продукции из пункта производства iв пункт потребления j.
Необходимоопределить такие объемы перевозок<img src="/cache/referats/23638/image018.gif" v:shapes="_x0000_i1033">затраты были минимальными, т.е. требуетсянайти наименьшее значение функционала
<img src="/cache/referats/23638/image020.gif" v:shapes="_x0000_i1034">
где
<img src="/cache/referats/23638/image022.gif" v:shapes="_x0000_i1035"> <img src="/cache/referats/23638/image024.gif" v:shapes="_x0000_i1036"> (1)
при условиях
<img src="/cache/referats/23638/image026.gif" v:shapes="_x0000_i1037"> <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1038"> <img src="/cache/referats/23638/image029.gif" v:shapes="_x0000_i1039">, (2)
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1040"><img src="/cache/referats/23638/image033.gif" v:shapes="_x0000_i1041"> <img src="/cache/referats/23638/image035.gif" v:shapes="_x0000_i1042"> (3)
<img src="/cache/referats/23638/image037.gif" v:shapes="_x0000_i1043"> <img src="/cache/referats/23638/image039.gif" v:shapes="_x0000_i1044"> (4)
Если все<img src="/cache/referats/23638/image041.gif" v:shapes="_x0000_i1045">, то задача становится обычной транспортной задачей линейногопрограммирования. В рассматриваемой задаче предполагается, что не все <img src="/cache/referats/23638/image041.gif" v:shapes="_x0000_i1046">. В этом случае функционал (1) представляет собой разрывную функцию, обладающую,вообще говоря, большим числом точек минимума над областью (2) — (4).
Предполагается также, что либо <img src="/cache/referats/23638/image044.gif" v:shapes="_x0000_i1047"> для всех <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1048">, либо <img src="/cache/referats/23638/image047.gif" v:shapes="_x0000_i1049"> недля всех <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1050">, так как в случае <img src="/cache/referats/23638/image047.gif" v:shapes="_x0000_i1051"> длявсех <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1052">получаем задачу размещения с неограниченными объемамипроизводства.Однако необходимо, чтобы суммарныйобъем потребления <img src="/cache/referats/23638/image051.gif" v:shapes="_x0000_i1053"> — не превышал суммуверхних/границобъемов производств, т.е.
<img src="/cache/referats/23638/image053.gif" v:shapes="_x0000_i1054"> (5)
так как в противном случае никакие значения <img src="/cache/referats/23638/image018.gif" v:shapes="_x0000_i1055"> не удовлетворяют условиям (2) -(4).
Обозначим через <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1056"> минимальные суммарныезатраты при фиксировании некоторого варианта размещения <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1057">
<img src="/cache/referats/23638/image060.gif" v:shapes="_x0000_i1058"> (6)
при условиях
<img src="/cache/referats/23638/image026.gif" v:shapes="_x0000_i1059"> <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1060"> <img src="/cache/referats/23638/image029.gif" v:shapes="_x0000_i1061">, (7)
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1062"><img src="/cache/referats/23638/image033.gif" v:shapes="_x0000_i1063"> <img src="/cache/referats/23638/image035.gif" v:shapes="_x0000_i1064"> (8)
<img src="/cache/referats/23638/image037.gif" v:shapes="_x0000_i1065"> <img src="/cache/referats/23638/image039.gif" v:shapes="_x0000_i1066"> (9)
Фиксированиенекоторого варианта размещения <img src="/cache/referats/23638/image062.gif" v:shapes="_x0000_i1067"> производится тем, что для всех <img src="/cache/referats/23638/image064.gif" v:shapes="_x0000_i1068"> считается <img src="/cache/referats/23638/image066.gif" v:shapes="_x0000_i1069">Дляфиксированного со предполагается выполнение условия
<img src="/cache/referats/23638/image068.gif" v:shapes="_x0000_i1070"> (10)
аналогичное условию (5).
Значение<img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1071"> для каждого <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1072">определяется решением обычной транспортной задачи линейногопрограммирования. Таким образом, можно говорить об однозначной функции <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1073">заданной на множестве всех <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1074">, для которых выполняются условия (10).
Задача,собственно, состоит в отыскании среди всех возможных подмножеств (вариантов размещения) <img src="/cache/referats/23638/image062.gif" v:shapes="_x0000_i1075"> пунктовпроизводства <img src="/cache/referats/23638/image070.gif" v:shapes="_x0000_i1076"> такогоподмножества (варианта) <img src="/cache/referats/23638/image072.gif" v:shapes="_x0000_i1077">, при котором обеспечиваютсяс учетом условий (7) — (10) наименьшие суммарные затраты<img src="/cache/referats/23638/image074.gif" v:shapes="_x0000_i1078">. Другими словами, требуется определить такоеподмножество <img src="/cache/referats/23638/image072.gif" v:shapes="_x0000_i1079">, для которого <img src="/cache/referats/23638/image077.gif" v:shapes="_x0000_i1080"> по всем <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1081">, удовлетворяющимусловию (10).
Функция <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1082"> не определена намножестве всех подмножеств <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1083">, не удовлетворяющих условию (10).Для определения функции <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1084"> на множестве всех <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1085">поступим следующим образом. Соотнесем пустому подмножеству <img src="/cache/referats/23638/image079.gif" v:shapes="_x0000_i1086"> условный пунктпроизводства <img src="/cache/referats/23638/image081.gif" v:shapes="_x0000_i1087">cколь угодно большими постоянными транспортными расходами<img src="/cache/referats/23638/image083.gif" v:shapes="_x0000_i1088">(<img src="/cache/referats/23638/image085.gif" v:shapes="_x0000_i1089"><img src="/cache/referats/23638/image087.gif" v:shapes="_x0000_i1090">). Так как пустое множество <img src="/cache/referats/23638/image079.gif" v:shapes="_x0000_i1091">содержится в любом <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1092">, то это означает, что условный пункт производства будет содержаться влюбом подмножестве (варианте размещения) <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1093"> пунктов производства.Поэтому в дальнейшем (чтобы не усложнять записи) под выражением <img src="/cache/referats/23638/image064.gif" v:shapes="_x0000_i1094"><img src="/cache/referats/23638/image006.gif" v:shapes="_x0000_i1095">все отличные от нуля значения элементовподмножества <img src="/cache/referats/23638/image062.gif" v:shapes="_x0000_i1096">, но и само значение 0, соответствующее условному пункту производства. В частности, <img src="/cache/referats/23638/image092.gif" v:shapes="_x0000_i1097"><img src="/cache/referats/23638/image094.gif" v:shapes="_x0000_i1098">.
Послетакого введения условного пункта производства условие (4.10) будет выполняться для любого <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1099">, так как величина <img src="/cache/referats/23638/image096.gif" v:shapes="_x0000_i1100"> и поэтому значение <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1101"> теперь может быть определено для всех <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1102">. Здесь необходимо отметить, что в силу выбора величин <img src="/cache/referats/23638/image098.gif" v:shapes="_x0000_i1103"><img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1104"> для тех <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1105">, для которыхусловие (10) выполняется лишь с учетом <img src="/cache/referats/23638/image100.gif" v:shapes="_x0000_i1106">, будут сколь угодно большими, а для тех <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1107">, для которых это условие выполняется и без учета <img src="/cache/referats/23638/image100.gif" v:shapes="_x0000_i1108">, наличие условного пункта производства не влияет на величину <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1109">, т.е. <img src="/cache/referats/23638/image103.gif" v:shapes="_x0000_i1110">. Отсюда, вчастности, следует, что искомоеподмножество <img src="/cache/referats/23638/image105.gif" v:shapes="_x0000_i1111"><img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1112">, для которых
<img src="/cache/referats/23638/image107.gif" v:shapes="_x0000_i1113"> (11)
Таким образом, на множествевсех подмножеств <img src="/cache/referats/23638/image062.gif" v:shapes="_x0000_i1114"> множества/определяется однозначная функция <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1115"> и исходная задача сводится к отысканиютакого подмножества <img src="/cache/referats/23638/image110.gif" v:shapes="_x0000_i1116"><img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1117"> достигаетсвоего наименьшего значения <img src="/cache/referats/23638/image074.gif" v:shapes="_x0000_i1118">, т.е<img src="/cache/referats/23638/image114.gif" v:shapes="_x0000_i1119">по всем <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1120">.
Покажем,что к решению этой задачи применим метод последовательных расчетов. Для этогодостаточно установить, что функция <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1121"> удовлетворяет условию
<img src="/cache/referats/23638/image117.gif" v:shapes="_x0000_i1122">
где <img src="/cache/referats/23638/image119.gif" v:shapes="_x0000_i1123"> и<img src="/cache/referats/23638/image121.gif" v:shapes="_x0000_i1124"> -произвольные подмножества <img src="/cache/referats/23638/image123.gif" v:shapes="_x0000_i1125">
Для доказательства рассмотрим вспомогательную функцию <img src="/cache/referats/23638/image125.gif" v:shapes="_x0000_i1126"> для всех <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1127">Можно записать
<img src="/cache/referats/23638/image127.gif" v:shapes="_x0000_i1128">
<img src="/cache/referats/23638/image129.gif" v:shapes="_x0000_i1129">
Таким образом, длякаждого <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1130">
<img src="/cache/referats/23638/image131.gif" v:shapes="_x0000_i1131">
при условиях (7)-(10).
2. Задачаразмещения с фиксированными минимальными объемами производства.
Эта задача отличается от задачи 1 тем, что некоторые предприятия <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1132">являются уже действующими с мощностями <img src="/cache/referats/23638/image133.gif" v:shapes="_x0000_i1133">, закрытиеих запрещено и возможно лишь увеличение их мощностей до некоторой величины <img src="/cache/referats/23638/image135.gif" v:shapes="_x0000_i1134">(<img src="/cache/referats/23638/image137.gif" v:shapes="_x0000_i1135">, что влечет дополнительные затраты <img src="/cache/referats/23638/image139.gif" v:shapes="_x0000_i1136">.Таким образом, ставится следующая задача: определить совокупность значений <img src="/cache/referats/23638/image018.gif" v:shapes="_x0000_i1137">, при которыхдостигается минимум функционала
<img src="/cache/referats/23638/image142.gif" v:shapes="_x0000_i1138"> (12)
при условиях
<img src="/cache/referats/23638/image026.gif" v:shapes="_x0000_i1139"> <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1140"> <img src="/cache/referats/23638/image029.gif" v:shapes="_x0000_i1141">, (13)
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1142"><img src="/cache/referats/23638/image037.gif" v:shapes="_x0000_i1143"> <img src="/cache/referats/23638/image145.gif" v:shapes="_x0000_i1144"> (14)
<img src="/cache/referats/23638/image147.gif" v:shapes="_x0000_i1145"> <img src="/cache/referats/23638/image149.gif" v:shapes="_x0000_i1146"> (15)
<img src="/cache/referats/23638/image151.gif" v:shapes="_x0000_i1147">
где <img src="/cache/referats/23638/image153.gif" v:shapes="_x0000_i1148"> — возможный объемпроизводства предприятия <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1149">.
Предполагается, что
<img src="/cache/referats/23638/image155.gif" v:shapes="_x0000_i1150">
так как в противномслучае задача не имеет решения. Задача чрезвычайно упрощается, когда
<img src="/cache/referats/23638/image157.gif" v:shapes="_x0000_i1151"> или <img src="/cache/referats/23638/image159.gif" v:shapes="_x0000_i1152">
в обоих случаях еерешение сводится к решению одной транспортной задачи. Поэтому будем в общем случаесчитать
<img src="/cache/referats/23638/image161.gif" v:shapes="_x0000_i1153"> (16)
Обозначим через <img src="/cache/referats/23638/image163.gif" v:shapes="_x0000_i1154"> множество тех <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1155">, длякоторых <img src="/cache/referats/23638/image165.gif" v:shapes="_x0000_i1156">. Определимфункцию <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1157"> на множестве всех подмножеств <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1158"> (считаем для <img src="/cache/referats/23638/image167.gif" v:shapes="_x0000_i1159">, как и прежде, <img src="/cache/referats/23638/image169.gif" v:shapes="_x0000_i1160"><img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1161"> полагать,что <img src="/cache/referats/23638/image171.gif" v:shapes="_x0000_i1162">для всех <img src="/cache/referats/23638/image064.gif" v:shapes="_x0000_i1163"> (это означает, что для всех предприятий <img src="/cache/referats/23638/image064.gif" v:shapes="_x0000_i1164">возможно расширение мощности до <img src="/cache/referats/23638/image175.gif" v:shapes="_x0000_i1165">), то минимальное значение функционала (12) для этого <img src="/cache/referats/23638/image062.gif" v:shapes="_x0000_i1166">
<img src="/cache/referats/23638/image178.gif" v:shapes="_x0000_i1167"> (17)
при условиях
<img src="/cache/referats/23638/image026.gif" v:shapes="_x0000_i1168"> <img src="/cache/referats/23638/image180.gif" v:shapes="_x0000_i1169"> <img src="/cache/referats/23638/image029.gif" v:shapes="_x0000_i1170">, (18)
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1171"><img src="/cache/referats/23638/image182.gif" v:shapes="_x0000_i1172"> <img src="/cache/referats/23638/image145.gif" v:shapes="_x0000_i1173"> (19)
<img src="/cache/referats/23638/image147.gif" v:shapes="_x0000_i1174"> для <img src="/cache/referats/23638/image064.gif" v:shapes="_x0000_i1175"> (20)
<img src="/cache/referats/23638/image185.gif" v:shapes="_x0000_i1176"> для <img src="/cache/referats/23638/image187.gif" v:shapes="_x0000_i1177">
Так как с учетомпустого множества для любого <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1178"> выполняется неравенство
<img src="/cache/referats/23638/image189.gif" v:shapes="_x0000_i1179"> (22)
тометодами линейного программирования определяется значение <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1180"> для любого <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1181">ва Iопределяется однозначная функция <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1182">. Следовательно, задача 2 сводится к определению такого подмножества<img src="/cache/referats/23638/image110.gif" v:shapes="_x0000_i1183">функция <img src="/cache/referats/23638/image056.gif" v:shapes="_x0000_i1184"> принимает своенаименьшее значение<img src="/cache/referats/23638/image074.gif" v:shapes="_x0000_i1185">, т.е. <img src="/cache/referats/23638/image193.gif" v:shapes="_x0000_i1186">по всем <img src="/cache/referats/23638/image058.gif" v:shapes="_x0000_i1187">при условиях (18) — (21). Возможны два случая:
1) <img src="/cache/referats/23638/image195.gif" v:shapes="_x0000_i1188">, т.е. <img src="/cache/referats/23638/image197.gif" v:shapes="_x0000_i1189"> <img src="/cache/referats/23638/image199.gif" v:shapes="_x0000_i1190"> и в этом случаеполучаем задачу 1;
2) <img src="/cache/referats/23638/image201.gif" v:shapes="_x0000_i1191"> можно записать <img src="/cache/referats/23638/image203.gif" v:shapes="_x0000_i1192"> где <img src="/cache/referats/23638/image205.gif" v:shapes="_x0000_i1193"> — элементы <img src="/cache/referats/23638/image207.gif" v:shapes="_x0000_i1194">, расположенные в порядке возрастания
индексовi, т.е. <img src="/cache/referats/23638/image209.gif" v:shapes="_x0000_i1195"><img src="/cache/referats/23638/image211.gif" v:shapes="_x0000_i1196">
Вслучае 2) рассмотрим задачу отыскания наименьшего значения функционала
<img src="/cache/referats/23638/image213.gif" v:shapes="_x0000_i1197"> (23)
приусловиях
<img src="/cache/referats/23638/image215.gif" v:shapes="_x0000_i1198"> <img src="/cache/referats/23638/image217.gif" v:shapes="_x0000_i1199"> <img src="/cache/referats/23638/image029.gif" v:shapes="_x0000_i1200">, (24)
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1201"><img src="/cache/referats/23638/image219.gif" v:shapes="_x0000_i1202"> <img src="/cache/referats/23638/image145.gif" v:shapes="_x0000_i1203"> (25)
<img src="/cache/referats/23638/image221.gif" v:shapes="_x0000_i1204"> <img src="/cache/referats/23638/image223.gif" v:shapes="_x0000_i1205"> (26)
где
<img src="/cache/referats/23638/image225.gif" v:shapes="_x0000_i1206">
<img src="/cache/referats/23638/image227.gif" v:shapes="_x0000_i1207"> <img src="/cache/referats/23638/image229.gif" v:shapes="_x0000_i1208">
<img src="/cache/referats/23638/image231.gif" v:shapes="_x0000_i1209">
Значения<img src="/cache/referats/23638/image233.gif" v:shapes="_x0000_i1210"><img src="/cache/referats/23638/image235.gif" v:shapes="_x0000_i1211"><img src="/cache/referats/23638/image237.gif" v:shapes="_x0000_i1212"> определяются следующимобразом.
Длявсех <img src="/cache/referats/23638/image239.gif" v:shapes="_x0000_i1213">
тельноечисло, но в то же время <img src="/cache/referats/23638/image241.gif" v:shapes="_x0000_i1214">
<img src="/cache/referats/23638/image243.gif" v:shapes="_x0000_i1215">
Длявсех <img src="/cache/referats/23638/image245.gif" v:shapes="_x0000_i1216"> при любых <img src="/cache/referats/23638/image247.gif" v:shapes="_x0000_i1217">
Условиеэтой задачи полностью совпадает с условием задачи 1, и поэтому решение еесводится к отысканию такого подмножества <img src="/cache/referats/23638/image249.gif" v:shapes="_x0000_i1218"><img src="/cache/referats/23638/image251.gif" v:shapes="_x0000_i1219"><img src="/cache/referats/23638/image253.gif" v:shapes="_x0000_i1220">
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">3. Задачаразмещения со ступенчатой функцией стоимости производства.
Постановка этой задачи отличается отпостановки задачи 1 другимзаданием функций стоимости производства предприятий. В данном случае эта функциязадается некоторой ступенчатой разрывной функцией<img src="/cache/referats/23638/image255.gif" v:shapes="_x0000_i1221"> именно:
<img src="/cache/referats/23638/image257.gif" v:shapes="_x0000_i1222"> (27)
где <img src="/cache/referats/23638/image259.gif" v:shapes="_x0000_i1223"> для всех <img src="/cache/referats/23638/image261.gif" v:shapes="_x0000_i1224"> (при<img src="/cache/referats/23638/image263.gif" v:shapes="_x0000_i1225"><img src="/cache/referats/23638/image265.gif" v:shapes="_x0000_i1226"> длявсех <img src="/cache/referats/23638/image267.gif" v:shapes="_x0000_i1227"> следует,что <img src="/cache/referats/23638/image269.gif" v:shapes="_x0000_i1228"> при<img src="/cache/referats/23638/image271.gif" v:shapes="_x0000_i1229"> для всех <img src="/cache/referats/23638/image273.gif" v:shapes="_x0000_i1230">
Таким образом, задача состоит в следующем: определитьсовокупность значений <img src="/cache/referats/23638/image275.gif" v:shapes="_x0000_i1231"> при которыхдостигается минимум функционала
<img src="/cache/referats/23638/image277.gif" v:shapes="_x0000_i1232"> (28)
где<img src="/cache/referats/23638/image279.gif" v:shapes="_x0000_i1233"> — ступенчатаяразрывная функция (27) при условиях
<img src="/cache/referats/23638/image026.gif" v:shapes="_x0000_i1234"> <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1235"> <img src="/cache/referats/23638/image029.gif" v:shapes="_x0000_i1236">, (29)
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1237"><img src="/cache/referats/23638/image281.gif" v:shapes="_x0000_i1238"> <img src="/cache/referats/23638/image035.gif" v:shapes="_x0000_i1239"> (30)
<img src="/cache/referats/23638/image037.gif" v:shapes="_x0000_i1240"> <img src="/cache/referats/23638/image039.gif" v:shapes="_x0000_i1241"> (31)
При<img src="/cache/referats/23638/image283.gif" v:shapes="_x0000_i1242"> получаемзадачу 1.
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;letter-spacing:.45pt;mso-font-width:93%; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">4. Задачиразмещения с ограничениями на суммарную продукцию.
В этой задаче предполагается, что суммарныйобъем продукции, выпускаемой всеми предприятиями, задан и равен <img src="/cache/referats/23638/image285.gif" v:shapes="_x0000_i1243">, объемы перевозок от предприятий до потребителей ограниченысверху величинами <img src="/cache/referats/23638/image287.gif" v:shapes="_x0000_i1244">каждый потребитель должен получить продукцию в объеме,не меньшем <img src="/cache/referats/23638/image289.gif" v:shapes="_x0000_i1245"> Остальные условия задачи 1 сохраняются.
Тогдарассматриваемая задача принимает следующий вид: определить совокупностьзначений <img src="/cache/referats/23638/image275.gif" v:shapes="_x0000_i1246">, при которых достигается минимум функционала
<img src="/cache/referats/23638/image292.gif" v:shapes="_x0000_i1247"> (32)
при условиях
<img src="/cache/referats/23638/image026.gif" v:shapes="_x0000_i1248"> <img src="/cache/referats/23638/image012.gif" v:shapes="_x0000_i1249"> <img src="/cache/referats/23638/image029.gif" v:shapes="_x0000_i1250">, (33)
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1251"><img src="/cache/referats/23638/image294.gif" v:shapes="_x0000_i1252"> <img src="/cache/referats/23638/image145.gif" v:shapes="_x0000_i1253"> (34)
<img src="/cache/referats/23638/image296.gif" v:shapes="_x0000_i1254"> <img src="/cache/referats/23638/image149.gif" v:shapes="_x0000_i1255"> (35)
<img src="/cache/referats/23638/image298.gif" v:shapes="_x0000_i1256"> (36)
<img src="/cache/referats/23638/image300.gif" v:shapes="_x0000_i1257">
Будем считать, что
<img src="/cache/referats/23638/image302.gif" v:shapes="_x0000_i1258">,<img src="/cache/referats/23638/image304.gif" v:shapes="_x0000_i1259">
Рассмотрим вначалезадачу (32) -(36). Наиболее интересен случай,
когда
<img src="/cache/referats/23638/image306.gif" v:shapes="_x0000_i1260">
Всеостальные предположения о расположениивеличины dотносительно интервала <img src="/cache/referats/23638/image308.gif" v:shapes="_x0000_i1261"> либо делают задачунесовместной, либо позволяют освободиться от условия (4.53).
Действительно,если
<img src="/cache/referats/23638/image310.gif" v:shapes="_x0000_i1262">, то <img src="/cache/referats/23638/image312.gif" v:shapes="_x0000_i1263">;
при <img src="/cache/referats/23638/image310.gif" v:shapes="_x0000_i1264"> условия (33), (34), (36) несовместны; при <img src="/cache/referats/23638/image314.gif" v:shapes="_x0000_i1265"> условие (36) можно исключить, заменив условия (34) на <img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1266"><img src="/cache/referats/23638/image316.gif" v:shapes="_x0000_i1267"> <img src="/cache/referats/23638/image145.gif" v:shapes="_x0000_i1268">
при <img src="/cache/referats/23638/image318.gif" v:shapes="_x0000_i1269"> условия (33), (34), (36)несовместны;<img src="/cache/referats/23638/image320.gif" v:shapes="_x0000_i1270"> при условие (36) можно исключить,заменив условия (35) на <img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1271"><img src="/cache/referats/23638/image322.gif" v:shapes="_x0000_i1272"> <img src="/cache/referats/23638/image324.gif" v:shapes="_x0000_i1273">
Длялюбого <img src="/cache/referats/23638/image326.gif" v:shapes="_x0000_i1274"> определение <img src="/cache/referats/23638/image328.gif" v:shapes="_x0000_i1275"> сводится к решениюзадачи (32)-(36),где везде вместо Iпишется <img src="/cache/referats/23638/image062.gif" v:shapes="_x0000_i1276">dдля какого-либо <img src="/cache/referats/23638/image326.gif" v:shapes="_x0000_i1277"> выйдет из интервала <img src="/cache/referats/23638/image308.gif" v:shapes="_x0000_i1278">, то, как показано выше,либо условия (33)-(36) становятся несовместными (в этом случае полагаем <img src="/cache/referats/23638/image331.gif" v:shapes="_x0000_i1279">), либоосвобождаемся от условия (4.53) иопределение <img src="/cache/referats/23638/image328.gif" v:shapes="_x0000_i1280"> сводится к решению транспортной задачи типа 1.
Производственно-распределительныезадачи оптимального размещенияпредприятий и применимость метода последовательных расчетов.
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;mso-ansi-language:RU;mso-fareast-language:RU; mso-bidi-language:AR-SA">5. Производственно-распределительнаязадача размещения предприятий с ограниченными объемами производства и пропускными способностямикоммуникаций.
Рассматриваетсязадача нахождения наименьшего значения функционала
<img src="/cache/referats/23638/image292.gif" v:shapes="_x0000_i1281"> (37)
при условиях
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1282"><img src="/cache/referats/23638/image316.gif" v:shapes="_x0000_i1283"> <img src="/cache/referats/23638/image145.gif" v:shapes="_x0000_i1284"> (38)
<img src="/cache/referats/23638/image334.gif" v:shapes="_x0000_i1285"> <img src="/cache/referats/23638/image149.gif" v:shapes="_x0000_i1286"> (39)
<img src="/cache/referats/23638/image336.gif" v:shapes="_x0000_i1287"> (40)
Вотличие от задач оптимального размещения предприятий иприменимость метода последовательных расчетов,здесь имеются коэффициенты <img src="/cache/referats/23638/image338.gif" v:shapes="_x0000_i1288">, называемые коэффициентами переработки. Комбинаторная постановка задачи (37)- (40) состоит в определении подмножества <img src="/cache/referats/23638/image340.gif" v:shapes="_x0000_i1289"> такого, что
<img src="/cache/referats/23638/image342.gif" v:shapes="_x0000_i1290"> где <img src="/cache/referats/23638/image344.gif" v:shapes="_x0000_i1291">
<img src="/cache/referats/23638/image346.gif" v:shapes="_x0000_i1292"><img src="/cache/referats/23638/image348.gif" v:shapes="_x0000_i1293">
при условиях (38)-(40), в которых Iзаменено на <img src="/cache/referats/23638/image062.gif" v:shapes="_x0000_i1294">.
В случаеотсутствия верхних ограничений на переменные <img src="/cache/referats/23638/image275.gif" v:shapes="_x0000_i1295"> в работе показывалось,что функция <img src="/cache/referats/23638/image328.gif" v:shapes="_x0000_i1296"> удовлетворяет условию <img src="/cache/referats/23638/image353.gif" v:shapes="_x0000_i1297">.
Длярешения сформулированной задачи также применим метод последовательных расчетов.
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;color:black;letter-spacing:-.05pt;mso-ansi-language:RU; mso-fareast-language:RU;mso-bidi-language:AR-SA">6. Производствснно-распределительнаязадача размещения предприятий с ограничениями на суммарную продукцию.
Рассматривается задача нахождениянаименьшего значения функционала
<img src="/cache/referats/23638/image292.gif" v:shapes="_x0000_i1298"> (41)
при условиях
<img src="/cache/referats/23638/image031.gif" v:shapes="_x0000_i1299"><img src="/cache/referats/23638/image355.gif" v:shapes="_x0000_i1300"> <img src="/cache/referats/23638/image145.gif" v:shapes="_x0000_i1301"> (42)
<img src="/cache/referats/23638/image334.gif" v:shapes="_x0000_i1302"> <img src="/cache/referats/23638/image149.gif" v:shapes="_x0000_i1303"> (43)
<img src="/cache/referats/23638/image357.gif" v:shapes="_x0000_i1304"> (44)
<img src="/cache/referats/23638/image359.gif" v:shapes="_x0000_i1305"> (45)
Комбинаторнаяпостановка задачи заключается в определении подмножества <img src="/cache/referats/23638/image340.gif" v:shapes="_x0000_i1306"> такого, что
<img src="/cache/referats/23638/image342.gif" v:shapes="_x0000_i1307"> где <img src="/cache/referats/23638/image344.gif" v:shapes="_x0000_i1308">
здесь <img src="/cache/referats/23638/image346.gif" v:shapes="_x0000_i1309"><img src="/cache/referats/23638/image348.gif" v:shapes="_x0000_i1310">.
при условиях (41) -(45),в которых Iзаменено на <img src="/cache/referats/23638/image062.gif" v:shapes="_x0000_i1311">
Длярешения этой задачи также применим метод последовательных расчетов.