Реферат: Транспортная задача и задача об использовании сырья
1<m:mathPr> <m:mathFont m:val=«Cambria Math»/> <m:brkBin m:val=«before»/> <m:brkBinSub m:val="--"/> <m:smallFrac m:val=«off»/> <m:dispDef/> <m:lMargin m:val=«0»/> <m:rMargin m:val=«0»/> <m:defJc m:val=«centerGroup»/> <m:wrapIndent m:val=«1440»/> <m:intLim m:val=«subSup»/> <m:naryLim m:val=«undOvr»/> </m:mathPr>1.Решить задачу об использованиисырья геометрическим способом и симплекс методом, дать экономическуюинтерпретацию.
<img src="/cache/referats/26147/image002.gif" v:shapes="_x0000_i1025">
<img src="/cache/referats/26147/image004.gif" v:shapes="_x0000_i1026">
<img src="/cache/referats/26147/image006.gif" v:shapes="_x0000_i1027">
75
5
3
83
4
7
50
1
5
<img src="/cache/referats/26147/image008.gif" v:shapes="_x0000_i1028">
4
5
Геометрическийспособ.
Пусть <img src="/cache/referats/26147/image010.gif" v:shapes="_x0000_i1029"> количество выпускаемойпродукции первого вида, тогда <img src="/cache/referats/26147/image012.gif" v:shapes="_x0000_i1030"> количество выпускаемойпродукции второго вида. Прибыль от реализации всей продукции составляет <img src="/cache/referats/26147/image014.gif" v:shapes="_x0000_i1031">
Цель задачи (максимализацияприбыли) запишется в виде
Расход ресурса
Запас ресурса
<img src="/cache/referats/26147/image015.gif" v:shapes="_x0000_s1042 _x0000_s1040 _x0000_s1041"><img src="/cache/referats/26147/image017.gif" v:shapes="_x0000_i1032">Структура всех трёх ограниченийодинакова <img src="/cache/referats/26147/image019.gif" v:shapes="_x0000_i1033">
<img src="/cache/referats/26147/image021.gif" v:shapes="_x0000_i1034">
<img src="/cache/referats/26147/image023.gif" v:shapes="_x0000_i1035">
Перейдём из неравенств куравнениям
<img src="/cache/referats/26147/image025.gif" v:shapes="_x0000_i1036">
Построим прямые на плоскости <img src="/cache/referats/26147/image027.gif" v:shapes="_x0000_i1037">
<img src="/cache/referats/26147/image029.gif" v:shapes="_x0000_i1038">
Многоугольник решений <img src="/cache/referats/26147/image031.gif" v:shapes="_x0000_i1039"><img src="/cache/referats/26147/image014.gif" v:shapes="_x0000_i1040"> построим начальнуюпрямую <img src="/cache/referats/26147/image033.gif" v:shapes="_x0000_i1041"> и вектор <img src="/cache/referats/26147/image035.gif" v:shapes="_x0000_i1042"><img src="/cache/referats/26147/image033.gif" v:shapes="_x0000_i1043"> вдоль вектора <img src="/cache/referats/26147/image038.gif" v:shapes="_x0000_i1044"> получим, чтомаксимальное значение наша прямая принимает в точке <img src="/cache/referats/26147/image040.gif" v:shapes="_x0000_i1045"> точке пересеченияпрямых <img src="/cache/referats/26147/image042.gif" v:shapes="_x0000_i1046"> и <img src="/cache/referats/26147/image044.gif" v:shapes="_x0000_i1047">
<img src="/cache/referats/26147/image046.gif" v:shapes="_x0000_i1048">
<img src="/cache/referats/26147/image048.gif" v:shapes="_x0000_i1049">
Симплексметод.
Приведём систему неравенств ксистеме уравнений
<img src="/cache/referats/26147/image050.gif" v:shapes="_x0000_i1050">
Целевая функция – функция прибыли
<img src="/cache/referats/26147/image052.gif" v:shapes="_x0000_i1051">
Составим симплекс таблицу:
- Первое ограничение запишем в первую строку
- Второе ограничение запишем во вторую строку
- Третье ограничение запишем в третью строку
Целевую функцию запишем в <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1052"> строку
Б
З
<img src="/cache/referats/26147/image056.gif" v:shapes="_x0000_i1053">
<img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1054">
<img src="/cache/referats/26147/image060.gif" v:shapes="_x0000_i1055">
<img src="/cache/referats/26147/image062.gif" v:shapes="_x0000_i1056">
<img src="/cache/referats/26147/image064.gif" v:shapes="_x0000_i1057">
<img src="/cache/referats/26147/image060.gif" v:shapes="_x0000_i1058">
75
5
3
1
<img src="/cache/referats/26147/image062.gif" v:shapes="_x0000_i1059">
83
4
7
1
<img src="/cache/referats/26147/image064.gif" v:shapes="_x0000_i1060">
50
1
5
1
<img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1061">
<img src="/cache/referats/26147/image070.gif" v:shapes="_x0000_i1062">
<img src="/cache/referats/26147/image072.gif" v:shapes="_x0000_i1063">
В строке <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1064"> есть отрицательные <img src="/cache/referats/26147/image075.gif" v:shapes="_x0000_i1065"> начальный план неоптимален. Найдём наименьший отрицательный элемент строки <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1066"><img src="/cache/referats/26147/image077.gif" v:shapes="_x0000_i1067"><img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1068"> будет включена в базис.Столбец переменной <img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1069"> – ведущий. Подсчитаем симплексные отношения и найдёмсреди них минимальное <img src="/cache/referats/26147/image081.gif" v:shapes="_x0000_i1070"> третья строка ведущая,а элемент <img src="/cache/referats/26147/image083.gif" v:shapes="_x0000_i1071"> разрешающий.Следовательно переменная <img src="/cache/referats/26147/image064.gif" v:shapes="_x0000_i1072"> выйдет из базиса.
Проведём одну интеракцию методазамещения Жордано-Гаусса. Столбцы. Разрешающий элемент
равен <img src="/cache/referats/26147/image086.gif" v:shapes="_x0000_i1073"> поделим третью строкуна 5, столбец <img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1074"> сделаем единичным дляэтого третью строку умножим на <img src="/cache/referats/26147/image089.gif" v:shapes="_x0000_i1075"> и прибавим к первойстроке, третью строку умножим на <img src="/cache/referats/26147/image091.gif" v:shapes="_x0000_i1076"> и сложим со второй строкой;третью строку сложим со строкой <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1077">
Б
З
<img src="/cache/referats/26147/image056.gif" v:shapes="_x0000_i1078">
<img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1079">
<img src="/cache/referats/26147/image060.gif" v:shapes="_x0000_i1080">
<img src="/cache/referats/26147/image062.gif" v:shapes="_x0000_i1081">
<img src="/cache/referats/26147/image064.gif" v:shapes="_x0000_i1082">
<img src="/cache/referats/26147/image060.gif" v:shapes="_x0000_i1083">
45
<img src="/cache/referats/26147/image095.gif" v:shapes="_x0000_i1084">
1
<img src="/cache/referats/26147/image097.gif" v:shapes="_x0000_i1085">
<img src="/cache/referats/26147/image062.gif" v:shapes="_x0000_i1086">
13
<img src="/cache/referats/26147/image099.gif" v:shapes="_x0000_i1087">
1
<img src="/cache/referats/26147/image101.gif" v:shapes="_x0000_i1088">
<img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1089">
10
<img src="/cache/referats/26147/image104.gif" v:shapes="_x0000_i1090">
1
<img src="/cache/referats/26147/image104.gif" v:shapes="_x0000_i1091">
<img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1092">
50
<img src="/cache/referats/26147/image107.gif" v:shapes="_x0000_i1093">
1
В строке <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1094"> есть отрицательные <img src="/cache/referats/26147/image075.gif" v:shapes="_x0000_i1095"> план не оптимальный.Рассчитаем симплексные отношения и найдём среди них минимальное <img src="/cache/referats/26147/image109.gif" v:shapes="_x0000_i1096"> вторая строка ведущая <img src="/cache/referats/26147/image075.gif" v:shapes="_x0000_i1097"> разрешающий <img src="/cache/referats/26147/image112.gif" v:shapes="_x0000_i1098">
Следовательно, переменная <img src="/cache/referats/26147/image062.gif" v:shapes="_x0000_i1099"> выйдёт из базиса. Таккак разрешающий элемент <img src="/cache/referats/26147/image112.gif" v:shapes="_x0000_i1100"><img src="/cache/referats/26147/image062.gif" v:shapes="_x0000_i1101"> на <img src="/cache/referats/26147/image117.gif" v:shapes="_x0000_i1102"><img src="/cache/referats/26147/image056.gif" v:shapes="_x0000_i1103"> отличны от элемента <img src="/cache/referats/26147/image120.gif" v:shapes="_x0000_i1104"> сделаем нулевыми, дляэтого вторую строку умножим на <img src="/cache/referats/26147/image122.gif" v:shapes="_x0000_i1105"> и прибавим к первой;вторую строку умножим на <img src="/cache/referats/26147/image124.gif" v:shapes="_x0000_i1106"> и прибавим к третьей;вторую строку умножим на <img src="/cache/referats/26147/image126.gif" v:shapes="_x0000_i1107"> и прибавим к строке <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1108">
Б
З
<img src="/cache/referats/26147/image056.gif" v:shapes="_x0000_i1109">
<img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1110">
<img src="/cache/referats/26147/image060.gif" v:shapes="_x0000_i1111">
<img src="/cache/referats/26147/image062.gif" v:shapes="_x0000_i1112">
<img src="/cache/referats/26147/image064.gif" v:shapes="_x0000_i1113">
<img src="/cache/referats/26147/image060.gif" v:shapes="_x0000_i1114">
23
1
<img src="/cache/referats/26147/image130.gif" v:shapes="_x0000_i1115">
<img src="/cache/referats/26147/image132.gif" v:shapes="_x0000_i1116">
<img src="/cache/referats/26147/image056.gif" v:shapes="_x0000_i1117">
5
1
<img src="/cache/referats/26147/image135.gif" v:shapes="_x0000_i1118">
<img src="/cache/referats/26147/image137.gif" v:shapes="_x0000_i1119">
<img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1120">
9
1
<img src="/cache/referats/26147/image140.gif" v:shapes="_x0000_i1121">
<img src="/cache/referats/26147/image142.gif" v:shapes="_x0000_i1122">
<img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1123">
65
<img src="/cache/referats/26147/image126.gif" v:shapes="_x0000_i1124">
<img src="/cache/referats/26147/image145.gif" v:shapes="_x0000_i1125">
В строке <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1126"> есть отрицательныйэлемент – пересчитываем таблицу. Рассчитываем симплексные отношения и найдёмсреди них минимальные <img src="/cache/referats/26147/image147.gif" v:shapes="_x0000_i1127"> первая строка ведущая <img src="/cache/referats/26147/image075.gif" v:shapes="_x0000_i1128"> разрешающий элемент <img src="/cache/referats/26147/image150.gif" v:shapes="_x0000_i1129"> переменная <img src="/cache/referats/26147/image060.gif" v:shapes="_x0000_i1130"> выйдет из базиса.Сделаем элемент <img src="/cache/referats/26147/image153.gif" v:shapes="_x0000_i1131"> единичным, для этогоподелим первую строку на <img src="/cache/referats/26147/image132.gif" v:shapes="_x0000_i1132"><img src="/cache/referats/26147/image064.gif" v:shapes="_x0000_i1133"> сделаем единичным дляэтого первую строку умножим на <img src="/cache/referats/26147/image157.gif" v:shapes="_x0000_i1134"> и прибавим ко второйстроке. Первую строку умножим на <img src="/cache/referats/26147/image159.gif" v:shapes="_x0000_i1135"> и прибавим к третьей.Первую строку умножим на <img src="/cache/referats/26147/image161.gif" v:shapes="_x0000_i1136"> и прибавим к строке <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1137">
Б
З
<img src="/cache/referats/26147/image056.gif" v:shapes="_x0000_i1138">
<img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1139">
<img src="/cache/referats/26147/image060.gif" v:shapes="_x0000_i1140">
<img src="/cache/referats/26147/image062.gif" v:shapes="_x0000_i1141">
<img src="/cache/referats/26147/image064.gif" v:shapes="_x0000_i1142">
<img src="/cache/referats/26147/image064.gif" v:shapes="_x0000_i1143">
13
<img src="/cache/referats/26147/image165.gif" v:shapes="_x0000_i1144">
<img src="/cache/referats/26147/image167.gif" v:shapes="_x0000_i1145">
1
<img src="/cache/referats/26147/image056.gif" v:shapes="_x0000_i1146">
12
1
<img src="/cache/referats/26147/image170.gif" v:shapes="_x0000_i1147">
<img src="/cache/referats/26147/image172.gif" v:shapes="_x0000_i1148">
<img src="/cache/referats/26147/image058.gif" v:shapes="_x0000_i1149">
5
1
<img src="/cache/referats/26147/image174.gif" v:shapes="_x0000_i1150">
<img src="/cache/referats/26147/image176.gif" v:shapes="_x0000_i1151">
<img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1152">
73
<img src="/cache/referats/26147/image161.gif" v:shapes="_x0000_i1153">
<img src="/cache/referats/26147/image165.gif" v:shapes="_x0000_i1154">
Так как в строке <img src="/cache/referats/26147/image054.gif" v:shapes="_x0000_i1155"> все элементы неотрицательны,то найден оптимальный план
<img src="/cache/referats/26147/image180.gif" v:shapes="_x0000_i1156">
<img src="/cache/referats/26147/image182.gif" v:shapes="_x0000_i1157">
Оптимальный план найденныйгеометрическим способом и симплексным методом совпадают. Предприятию необходимовыпускать 12 единиц продукции первого вида и 5 единиц продукции второго вида. Вэтом случае предприятие получит прибыль <img src="/cache/referats/26147/image184.gif" v:shapes="_x0000_i1158"> денежных единиц.
2.Решить транспортную задачураспределительным методом, оценивая свободные клетки по методу потенциалов.
<img src="/cache/referats/26147/image185.gif" v:shapes="_x0000_s1047"> <img src="/cache/referats/26147/image187.gif" v:shapes="_x0000_i1159">
<img src="/cache/referats/26147/image189.gif" v:shapes="_x0000_i1160">
60
50
85
75
65
8
10
6
5
65
80
4
30
3
50
5
9
35
11
25
4
4
8
10
90
5
5
5
3
85
6
Проверим необходимое идостаточное условие разрешимости задачи
<img src="/cache/referats/26147/image191.gif" v:shapes="_x0000_i1161">
<img src="/cache/referats/26147/image193.gif" v:shapes="_x0000_i1162">
Потребность в грузе равна запасамгруза <img src="/cache/referats/26147/image075.gif" v:shapes="_x0000_i1163"> задача закрытая,следовательно, имеет единственное решение.
Используя метод наименьшейстоимости заполним таблицу.
Среди тарифов наилучшим является <img src="/cache/referats/26147/image196.gif" v:shapes="_x0000_i1164"> и <img src="/cache/referats/26147/image198.gif" v:shapes="_x0000_i1165">
в клетку <img src="/cache/referats/26147/image200.gif" v:shapes="_x0000_i1166">
в клетку <img src="/cache/referats/26147/image202.gif" v:shapes="_x0000_i1167">
в клетку <img src="/cache/referats/26147/image204.gif" v:shapes="_x0000_i1168">
в клетку <img src="/cache/referats/26147/image206.gif" v:shapes="_x0000_i1169">
в клетку <img src="/cache/referats/26147/image208.gif" v:shapes="_x0000_i1170">
в клетку <img src="/cache/referats/26147/image210.gif" v:shapes="_x0000_i1171">
в клетку <img src="/cache/referats/26147/image212.gif" v:shapes="_x0000_i1172">
Запасы поставщиков исчерпаны,запросы потребителей удовлетворены полностью. В результате получили первыйопорный план. Подсчитаем число занятых клеток таблицы их 7, а должно быть <img src="/cache/referats/26147/image214.gif" v:shapes="_x0000_i1173"> опорный план невырожденный.
Определим значение целевойфункции первого опорного плана
<img src="/cache/referats/26147/image216.gif" v:shapes="_x0000_i1174">
Проверим оптимальность плана.
Найдём потенциалы <img src="/cache/referats/26147/image218.gif" v:shapes="_x0000_i1175"> и <img src="/cache/referats/26147/image220.gif" v:shapes="_x0000_i1176"> по занятым клеткамтаблицы
<img src="/cache/referats/26147/image222.gif" v:shapes="_x0000_i1177">
Пусть <img src="/cache/referats/26147/image224.gif" v:shapes="_x0000_i1178">
<img src="/cache/referats/26147/image226.gif" v:shapes="_x0000_i1179">
Подсчитаем оценки свободныхклеток <img src="/cache/referats/26147/image228.gif" v:shapes="_x0000_i1180">
<img src="/cache/referats/26147/image230.gif" v:shapes="_x0000_i1181">
<img src="/cache/referats/26147/image232.gif" v:shapes="_x0000_i1182">
<img src="/cache/referats/26147/image234.gif" v:shapes="_x0000_i1183">
<img src="/cache/referats/26147/image236.gif" v:shapes="_x0000_i1184">
<img src="/cache/referats/26147/image238.gif" v:shapes="_x0000_i1185">
Первый опорный план не являетсяоптимальным так как <img src="/cache/referats/26147/image240.gif" v:shapes="_x0000_i1186">
Переходим к его улучшению. Дляклетки <img src="/cache/referats/26147/image242.gif" v:shapes="_x0000_i1187"> строим циклперераспределения
<img src="/cache/referats/26147/image244.gif" v:shapes="_x0000_i1188">
В результате получили новыйопорный план
<img src="/cache/referats/26147/image187.gif" v:shapes="_x0000_i1189"><img src="/cache/referats/26147/image185.gif" v:shapes="_x0000_s1048">
<img src="/cache/referats/26147/image189.gif" v:shapes="_x0000_i1190">
60
50
85
75
65
8
10
6
5
65
80
4
55
3
25
5
9
35
11
4
25
4
8
10
90
5
5
5
3
85
6
Определим значение целевойфункции
<img src="/cache/referats/26147/image246.gif" v:shapes="_x0000_i1191">
Проверим оптимальность плана
<img src="/cache/referats/26147/image248.gif" v:shapes="_x0000_i1192"> <img src="/cache/referats/26147/image250.gif" v:shapes="_x0000_i1193"> <img src="/cache/referats/26147/image252.gif" v:shapes="_x0000_i1194">
Подсчитаем оценки свободныхклеток
<img src="/cache/referats/26147/image254.gif" v:shapes="_x0000_i1195">
<img src="/cache/referats/26147/image256.gif" v:shapes="_x0000_i1196">
<img src="/cache/referats/26147/image258.gif" v:shapes="_x0000_i1197">
<img src="/cache/referats/26147/image260.gif" v:shapes="_x0000_i1198">
<img src="/cache/referats/26147/image262.gif" v:shapes="_x0000_i1199">
План близок к оптимальному.
При дальнейшем перераспределениигруза, задача входит в циклическую фазу, план не улучшается. Таким образом,полученное решение является наиболее оптимальным для нашей задачи