Курс лекци Русакова по методам оптимизации (1083216), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Если найденная точка не является искомой, то метод обеспечиваетпереход в другую точку с уменьшением (увеличением) значения целевойфункции z = z (x ) . Через конечное число подобных точек точкаx* либонаходится, либо признаётся несуществующей.Симплексный метод универсален, хотя и требует стандартнуюпостановку задачи:Табличный алгоритм симплекс методаДля изготовления различных изделий A , B и C система использует 3различных вида сырья. Нормы расхода сырья на производство одногоизделия приведены в следующей таблице.Нормы затрат ресурса (у.е.)Вид ресурса39ОбщееколичествоABCI181512360II648192III533180Стоимость91016ресурсовИзделия A , B и C могут производиться в любых соотношениях (сбытобеспечен), накладываются ограничения по количеству сырья каждого вида.Требуется составить такой план производства изделий, при которомобщая стоимость всей произведённой предприятием продукции являетсямаксимальной.

Составим математическую модель.Обозначим искомый выпуск изделий A через x1 , B через x2 , C черезx3 .Целевая функция имеет вид:F = 9 x1 + 10 x 2 + 16 x3 → max .(1)В общем виде целевая функция принимает вид:F = c1 x1 + c2 x2 + K + cn xn →maxmin(1’)Ограничения записываются так18 x1 + 15 x 2 + 12 x3 ≤ 360 6 x1 + 4 x2 + 8 x3 ≤ 192 . 5 x + 3x + 3x ≤ 180123(2)Или в общем виде, так a11 x11 + a12 x12a x + a x 21 2122 22a n1 x n1 + a n 2 x n 2+ K + a1n x1n ≤ b1+ K + a 2 n x 2 n ≤ b2M,(2’)+ K + a nn x nn ≤ bnгде x1 , x 2 ,K , x n ≥ 0 .Запишемэтузадачу(3)вформеосновнойзадачилинейногопрограммирования (ОЗЛП).

Для этого перейдём от ограничений неравенств кограничением равенствам:18 x1 + 15x2 + 12 x3 + x4 = 360 6 x1 + 4 x2 + 8 x3 + x5 = 192 5 x + 3x + 3x + x = 180123640(4)В общем виде ограничения виде равенств записываются так: a11 x1 + a12 x2 + K + a1n xn + xn +1 = b1a x + a x + K + a x + x = b 21 1 22 22n nn+22.M an1 x1 + an 2 x2 + K + ann xn + x2 n = bn(4’)Преобразуем систему (4) к векторной форме.x1 p1 + x2 p 2 + x3 p 3 + x4 p 4 + x5 p 5 + x6 p 6 = p 0 .(5)18 12 15 1    234p =  6  ; p =  4  ; p =  8  ; p =  0 ;3 053    1 0 p5 = 1 ; 0  0 p 6 =  0 ;1  360 p 0 =  192  . 180 Запишем опорный план (базисное решение).X = (0; 0; 0; 360 192 180 )Опорныйпланопределяетсясистемойтрёхмерныхединичныхвекторов p 4 , p 5 , p 6 , которые образуют базис трёхмерного векторногопространства.Составим симплексную таблицу для 1-ой итерации.

Для этого поприведённым ниже формулам найдём следующие значения и запишем ихв симплекс таблицу.Сначала положим, что предприятие вообще не выпускает изделий, ипоэтому целевая функция принимает нулевое значение, то есть()F0 C K , P 0 = 0 , где0 C K =  0  — начальные значения коэффициентов в целевой функции.0 Далее найдём начальные частичные суммы целевой функции zi − сi .41(= (C= (C)z1 = C K , p1 = 0z2z3KK(= (C= (C), p )= 0, p )= 0z4 = C K , p 4 = 0), p )= 0, p2 = 0z53z6KK56Табл. 1.Симплекс таблица для первой итерации.1016000( C1 )( C2 )( C3 )( C4 )( C5 )( C6 )p1p2p3p4p5p6100010001000Базис9CKp40360181512( C4 )( b1 )( a11 )( a12 )( a13 )0192648( C5 )( b2 )( a21 )( a22 )( a23 )0180533( C6 )( b3 )( a31 )( a32 )( a33 )0-9-10-16( f0 )( z1 − c1 )( z 2 − c2 )( z3 − c3 )p5p6p0( z 4 − c4 ) ( z5 − c5 )( z6 − c6 )Как видно из табл.

1, значения всех основных переменных x1 , x 2 , x 3равны нулю, а дополнительные переменные принимают свои значения всоответствии с ограничениями задачи.Эти значения переменных отвечают такому «плану», при которомничего не производится, сырьё не используется и значение целевой функцииравно нулю. (то есть стоимость произведённой продукции отсутствует).Естественно, такой план не является оптимальным.Это видно из 4-йстроки табл.

1 так как в ней имеются триотрицательных числа (− 9;−10;−16). Напомним, что условие оптимальностиуказывает на то, что в последней строке не должно быть отрицательныхчисел. Эти отрицательные числа не только свидетельствуют о возможности42увеличения общей стоимости производимой продукции, но и показывают, насколько увеличится эта сумма при введении в план единицы того илидругого вида продукции. Так число − 9 означает, что при включении в планпроизводства одного изделияAобеспечивается увеличение выпускапродукции на 9 руб. Поэтому с экономической точек зрения наиболеецелесообразным является включение в план производства изделий C .

Это жеи необходимо сделать и на основании формального признака симплексногометода, поскольку максимальное по абсолютной величине отрицательноечисло ∆ i = (zi − ci ) стоит в 4-й строке столбца P 3 . Следовательно, в базисвведём вектор P 3 .Определяем вектор, подлежащий исключению из базиса. Для этогонаходимθ = min (bi ai 3 )дляai 3 > 0 ,тоестьθ = min (360 12; 192 8; 180 3;) = 192 8 . Найдя число 192 8 = 24 , мы темсамым с экономической точки зрения определили, какое количество изделийC предприятие может изготовлять с учётом норм расхода и имеющихсяобъёмов сырья каждого вида. Так как сырья данного вида соответственноимеется 360, 192 и 180 кг, а на одно изделие C требуется затратить сырьякаждого вида соответственно 12, 8 и 3 кг, то максимальное число изделий C ,котороеможетбытьизготовленопредприятием,равноmin (360 12; 192 8; 180 3;) = 192 8 = 24 , то есть ограничивающим факторомдля производства изделий C является имеющийся объём сырья II вида.

Сучётом его наличия предприятие может изготовить 24 изделия C . При этомсырьё II вида будет полностью использовано. Следовательно, вектор P 5подлежит исключению из базиса. Столбец вектора P 3 и вторая 2-я являютсянаправляющими. Составим таблицу для второй итерации.Сначала заполним строку вектора, вновь введённого в базис, т.е.строку, номер которой совпадает с номером направляющей строки. Здесь43направляющей строкой является вторая строка. Элементы этой строкиполучаются из соответствующих элементов табл. 1 делением их наразрешающий элемент (т.е.

на 8).Табл. 2.Симплекс таблица для второй итерации.БазисCKp40( C4 )p316000( C2 )( C3 )( C4 )( C5 )( C6 )p1p2p3p4p5p6729901−3 202434121018010811 43200−3 813843-20020p016( C3 )p61090( C6 )При этом в столбце C K записываем коэффициент C3 = 16 , стоящий встолбце вводимого в базис вектора P 3 . Затем заполняем элементы столбцовдля векторов, входящих в новый базис. В этих столбцах на пересечениистрок и столбцов одноименных векторов подставляем единицы, а всеостальные элементы полагаем равными нулю.Для определения остальных элементов табл. 2 применяем правилотреугольника. Вычислим элементы табл. 2, стоящие в столбце вектора P 0 .Первый из них находится в 1-й строке этого столбца. Для его вычислениянаходим три числа:Число, стоящее на месте этого элемента в предыдущей таблице.В нашем случае это число, стоящее в табл.

1 на пересечении столбца вектораP 0 и 1-й строки (360);44Число, стоящее в той же строке что и отыскиваемый элемент и встолбце вектора вводимого в базис из предыдущей симплекс таблицы. Внашем случае это число, стоящее в табл. 1 на пересечении столбца вектораP 3 и 1-й строки (12);Число в строке введённого в базис вектора и в столбце отыскиваемогоэлемента в текущей симплекс таблице. В нашем случае это число, стоящее втабл. 2 на пересечении столбца вектора P 0 и 2-й строки (24).Вычитая из первого числа произведение двух других, находимискомый элемент: 360 − 12 ⋅ 24 = 72 ; записываем его в 1-й строке столбцавектора P 0 табл.

2. Аналогичным образом находим и все остальныеэлементы:108 = 180 − 3 ⋅ 24 ;9 = 18 − 12 ⋅ 3 4 ;11 4 = 5 − 3 ⋅ 3 4 ;9 = 15 − 12 ⋅ 1 2 ;3 2 = 3 − 3 ⋅1 2 ;− 3 2 = 0 − 12 ⋅ 1 8 ;− 3 8 = 0 − 3 ⋅1 8 .По окончании расчёта всех элементов табл. 2 в ней получены новыйопорный план и коэффициенты разложения векторов P ( j = 1,6 ) черезбазисные векторы P 4 , P 3 , P 6 и значения ∆' j и f 0' . Как видно из этой таблицы,новымопорнымпланомX = [0; 0; 24; 72; 0; 108;] .Призадачиданномявляетсяпланепланпроизводстваизготовлены 24 изделия C и остаётся неиспользованным 72 кг сырья I вида и108 кг сырья III вида. Стоимость всей производимой при этом планепродукции равна 384 руб.

Указанные числа записаны в столбце вектора P 0табл. 2. Как видно, данные этого столбца по-прежнему представляют собойпараметры рассматриваемой задачи, хотя они значительные изменения.Изменились данные и других столбцов, а их экономическое содержаниестало более сложным.

Так, например, возьмём два столбца вектора P 2 . Число451 2 во 2-й строке этого столбца показывает, на сколько следует уменьшитьизготовление изделий C , если запланировать выпуск одного изделия B .Числа 9 и 3 2 в 1-й и 3-й строках вектора P 2 показывают соответственно,сколько потребуется сырья I и II вида при включении в план производстваодного изделия B , то это обеспечит увеличение выпуска продукции ввыражении стоимости на 2 руб.

Другими словами, если включить в планпроизводства продукции одно изделие B , то это потребует уменьшениявыпуска изделия C на 1 2 ед. и потребует дополнительных затрат 9 кг сырьяI вида и 3 2 кг сырья III вида, а общая стоимость изготовляемой продукции всоответствии с новым оптимальным планом возрастёт на 2 руб. Такимобразом, числа 9 и 3 2 выступают как бы новыми «нормами» затрат сырья Iи III вида на изготовление одного изделия B (как видно из табл. 1, ранее онибыли равны 15 и 3), что объясняется уменьшением выпуска изделий C .Такой же экономический смысл имеют и данные столбца вектора P1табл.

2. Несколько иное экономическое содержание имеют, числа записанныев столбце вектора P 5 . Число 1 8 во 2-й строке этого столбца, показывает, чтоувеличении объёмов сырья II вида на 1 кг позволило бы увеличить выпускизделий C на 1 8 ед. Одновременно потребовалось бы дополнительно 3 2 кгсырья I вида и 3 8 кг сырья III вида. Увеличение выпуска изделий C на1 8 ед. приведет к росту выпуска продукции на 2 руб.Из изложенного выше экономического содержания данных табл.

2следует, что найденный на II итерации план задачи не являетсяоптимальным. Это видно и из 4-й строки табл. 2, поскольку в столбцевектора P 2 этой строки стоит отрицательное число − 2 . Значит, в базисследует ввести вектор P 2 , то есть в новом плане следует предусмотретьвыпуск изделий B . При определении возможного числа изготовленияизделий B следует учитывать имеющиеся количество сырья каждого вида, а46именно: возможный выпуск изделий B определяется min(bi′ ai′2 ) для ai′2 > 0 ,то есть находим 72 24 ⋅ 2 108 ⋅ 2  72Θ = min ;;= 8.=13  9 9Следовательно, исключению из базиса подлежит вектор P 4 , инымисловами, выпуск изделий B ограничен имеющимися в распоряжениипредприятия сырьём I вида.

С учётом имеющихся объёмов этого сырьяB . Число 9 являетсяпредприятию следует изготовить 8 изделийразрешающим элементом, а столбец вектора P 2 и 1-я строка табл. 2 являютсянаправляющими.Составляем таблицу для III итерации.Табл. 3.Симплекс таблица для третей итерации.1016000pp1p2p3p4p5p610811019−1 60p316201401− 1 185 240p60965400−1 6−1 8140050029530Базис9Kp2C0В табл. 3 сначала заполняем элементы 1-й строки, котораяпредставляет собой строку вновь вводимого в базис вектораp 2 . Элементыэтой строки получаем из элементов 1-й строки табл. 2 делением последних наразрешающий элемент (то есть на 9).

При этом в столбце C K данной строкизаписываем C2 = 10 .47Затем заполняем элементы столбцов векторов базиса и по правилутреугольника вычисляем элементы остальных столбцов.Врезультатевтабл.3получаемновыйопорныйпланX = (0; 8; 20; 0; 0; 96 ) и коэффициенты разложения векторов(i = 1,6) через базисные векторыp2 , p3 , p6Piи соответствующие значения∆′′j и f 0′′ .Проверяем является ли данный опорный план оптимальным или нет.Для этого рассмотрим 4-ю строку табл. 3. В этой строке среди чисел ∆′′j нетотрицательных. Это означает, что найденный опорный план являетсяоптимальным иf max = 400 .

Характеристики

Список файлов лекций