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

1.Сущность симплекс - метода.
4.Решить по алгоритму Литтла задачу коммивояжера с матрицей ...

1.Сущность симплекс - метода.
4.Решить по алгоритму Литтла задачу коммивояжера с матрицей

Симплекс - метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

7.Выбор разрешающей строки (переменной, выводимой из базиса) по условию: Ds=minbiaii, i=1,2,…,m, для air > 0, где s - номер разрешающей строки.Таким образом, для тех строк, где элементы разрешающего столбца положительны, необходимо найти частное от деления элемента bi (последний столбец таблицы) на элемент, находящийся в разрешающем столбце. В качестве разрешающей выбирается та строка, для которой результат такого деления будет наименьшим. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. 8.Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Для элементов разрешающей строки используются следующие формулы: asj'=asjasr,  bs'=bsasr,  где s - номер разрешающей строки, r - номер разрешающего столбца, bs', asj'-новые значения пересчитываемых элементов, asj, bs - старые значения пересчитываемых элементов, asr - старое значение разрешающего элемента. При пересчете элементов разрешающей строки каждый ее элемент делится на разрешающий элемент. Элементы разрешающего столбца кроме разрешающего элемента, который равен 1, становятся равными нулю: air' =0, cr'=0.Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету, и разрешающий элемент образуют одну из диагоналей. Формулы будут иметь следующий вид: aij'=aij-air∙asjasr,  bi'=bi-air∙bsasr,  cj'=cj-asj∙crasr,  L'=L-cr∙bsasr, где , , , - новые значения пересчитываемых элементов, aij, bi, cj, L - старые значения пересчитываемых элементов. 3.Решение задачиИсходные данные:Запас груза в i-м пункте отправления ai: a1=28, a2=50, a3=39.Потребность j-го пункта назначения в грузе bj: b1=21, b2=36, b3=60.Матрица тарифов (транспортных расходов) Ci,j:(Ci,j)m×n=123123323383352Составим математическую модель задачи транспортного типа. Общие суммарные затраты, связанные с реализацией плана перевозок, можно представить целевой функциейПеременные Xk должны удовлетворять ограничениям по запасам (1), по потребностям (2), и условиям неотрицательности. В математической записи это можно представить так:Целевая функция:2X1+3X2+3X3+3X4+3X5+8X6+3X7+5X8+2X9→minУсловия:1X1+1X2+1X3+0X4+0X5+0X6+0X7+0X8+0X9=280X1+0X2+0X3+1X4+1X5+1X6+0X7+0X8+0X9=500X1+0X2+0X3+0X4+0X5+0X6+1X7+1X8+1X9=391X1+0X2+0X3+1X4+0X5+0X6+1X7+0X8+0X9=210X1+1X2+0X3+0X4+1X5+0X6+0X7+1X8+0X9=360X1+0X2+1X3+0X4+0X5+1X6+0X7+0X8+1X9=60Транспортная задача разрешима только в случае, если соблюдается условие баланса Σai=Σbi. В нашем случае оно выполняется, так как:Σai=28+50+39=117Σbi=21+36+60=117Следовательно задача является закрытой (сбалансированой). Приведем систему ограничений к каноническому виду, для этого введем в каждое условие искусственную переменную R. Тогда система запишется в виде:1X1+1X2+1X3+0X4+0X5+0X6+0X7+0X8+0X9+R1=280X1+0X2+0X3+1X4+1X5+1X6+0X7+0X8+0X9+R2=500X1+0X2+0X3+0X4+0X5+0X6+1X7+1X8+1X9+R3=391X1+0X2+0X3+1X4+0X5+0X6+1X7+0X8+0X9+R4=210X1+1X2+0X3+0X4+1X5+0X6+0X7+1X8+0X9+R5=360X1+0X2+1X3+0X4+0X5+1X6+0X7+0X8+1X9+R6=60Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции.Так как среди исходного набора условий были равенства, мы ввели искуственные переменные R. Это значит, что в симплекс таблицу нам необходимо добавить дополнительную строку M, элементы которой расчитываются как сумма соответствующих элементов условий-равенств (тех которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.Из данных задачи составляем исходную симплекс таблицу.X1X2X3X4X5X6X7X8X9Своб членF2333383520R111100000028R200011100050R300000011139R410010010021R501001001036R600100100160M-2-2-2-2-2-2-2-2-2-234Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 (столбец X1). Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R4, а ведущий элемент: 1.X2X3X4X5X6X7X8X9Своб членF33138152-42R111-100-1007R20011100050R30000011139X10010010021R51001001036R60100100160M-2-20-2-20-2-2-192В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 (столбец X2). Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 1.X3X4X5X6X7X8X9Своб членF0438452-63X21-100-1007R2011100050R3000011139X1010010021R5-111011029R6100100160M0-2-2-2-2-2-2-178В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 (столбец X4). Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X1, а ведущий элемент: 1.X3X1X5X6X7X8X9Своб членF0-438052-147X2110000028R20-111-10029R3000011139X4010010021R5-1-1100108R6100100160M02-2-20-2-2-136В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 (столбец X5). Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R5, а ведущий элемент: 1.X3X1X6X7X8X9Своб членF3-18022-171X211000028R2101-1-1021R300011139X401010021X5-1-100108R610100160M-20-200-2-120В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 (столбец X3). Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R2, а ведущий элемент: 1.X1X6X7X8X9Своб членF-15352-234X21-11107X301-1-1021R30011139X41010021X5-11-10029R60011139M00-2-2-2-78В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 (столбец X7). Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X2, а ведущий элемент: 1.X1X6X2X8X9Своб членF-48-322-255X71-11107X31010028R3-11-10132X401-1-1014X50011036R6-11-10132M2-220-2-64В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 (столбец X6). Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X4, а ведущий элемент: 1.X1X4X2X8X9Своб членF-4-85102-367X71100021X31010028R3-1-101118X601-1-1014X50011036R6-1-101118M220-2-2-36В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -2 (столбец X8). Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R3, а ведущий элемент: 1.X1X4X2X9Своб членF625-8-547X7110021X3101028X8-1-10118X6-10-1132X5111-118R600000M00000В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -8 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X8, а ведущий элемент: 1.X1X4X2X8Своб членF-2-658-403X7110021X3101028X9-1-10118X601-1-114X5001136R600000M00000В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -6 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X6, а ведущий элемент: 1.X1X6X2X8Своб членF-26-12-319X71-1117X3101028X9-11-1032X401-1-114X5001136R600000M00000В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -2 Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X7, а ведущий элемент: 1.X7X6X2X8Своб членF2414-305X11-1117X3-110-121X9100139X401-1-114X5001136R600000M00000Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки F, взятый с противоположным знаком. Найдено оптимальное решение (минимальные транспортные расходы) F=305 при значениях переменных равных:X1=7 (количество продукции, доставленое от поставщика №1 к потребителю №1),X3=21 (количество продукции, доставленое от поставщика №1 к потребителю №3),X9=39 (количество продукции, доставленое от поставщика №3 к потребителю №3),X4=14 (количество продукции, доставленое от поставщика №2 к потребителю №1),X5=36 (количество продукции, доставленое от поставщика №2 к потребителю №2),Ответ:4.Решить по алгоритму Литтла задачу коммивояжера с матрицей ∞9879∞6886∞147814∞Все элементы по диагонали матрицы приравняем к бесконечности.