Методы оптимизации и исследование операций

С помощи рассмотренных моделей можно строить прогнозы и планы для компании, а в случае изменений каких либо показателей и значений, в модель можно легко внести изменения. Использование этой методики, построенной на основе SWOT-таблицы и модели линейного программирования, позволяет решать задачу выбора оптимальной стратегии — набора мероприятий на прогнозный период, обеспечивающих получение максимального роста продаж при ограниченном бюджете. Решение математических моделей изучаемого объекта средства ExcelПринятые программы стратегических мероприятий по развитию предприятия.

В результате анализа в предыдущей главе выяснилось, что для повышения продаж необходимо провести ряд мероприятий. Теперь рассмотрим еще одну задачу по увеличению прибыли предприятия — оптимальное распределения ресурсов. Поставим следующую задачу. Пусть — программа производства самолетов МиГ-29СД, — программа производства самолетов МиГ-29СМ, — программа производства самолетов МиГ-31Э, Введем ограничения:

ограничения по производственным материалам:

ограничения по трудозатратам:

ограничения по государственной программе:

ограничение по зарубежным контрактам:

Целевая функция:

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F (X) = 3561/2×1 + 4131/2×2 + 5531/5×3 при следующихусловиях-ограничений. 196×1 + 182×2 + 1522/5x3≤10 000 1940×1 + 2820×2 + 1410x3≤250 000 x3≥5 x1≥10 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5.

В 3-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус. В 4-м неравенстве смысла (≥) вводим базисную переменную x7 со знаком минус. 196×1 + 182×2 + 1522/5×3 + 1×4 + 0×5 + 0×6 + 0×7 = 10 000 1940×1 + 2820×2 + 1410×3 + 0×4 + 1×5 + 0×6 + 0×7 = 250 000 0×1 + 0×2 + 1×3 + 0×4 + 0×5−1×6 + 0×7 = 5 1×1 + 0×2 + 0×3 + 0×4 + 0×5 + 0×6−1×7 = 10 Введем искусственные переменные x: в 3-м равенстве вводим переменную x8; в 4-м равенстве вводим переменную x9; 196×1 + 182×2 + 1522/5×3 + 1×4 + 0×5 + 0×6 + 0×7 + 0×8 + 0×9 = 10 000 1940×1 + 2820×2 + 1410×3 + 0×4 + 1×5 + 0×6 + 0×7 + 0×8 + 0×9 = 250 000 0×1 + 0×2 + 1×3 + 0×4 + 0×5−1×6 + 0×7 + 1×8 + 0×9 = 5 1×1 + 0×2 + 0×3 + 0×4 + 0×5 + 0×6−1×7 + 0×8 + 1×9 = 10 Для постановки задачи на максимум целевую функцию запишем так: F (X) = 3561/2×1+4131/2×2+5531/5×3 — Mx8 — Mx9 → maxЗа использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается. Из уравнений выражаем искусственные переменные: x8 = 5-x3+x6 x9 = 10-x1+x7которые подставим в целевую функцию: F (X) = 3561/2×1 + 4131/2×2 + 5531/5×3 — M (5-x3+x6) — M (10-x1+x7) → maxили F (X) = (3561/2+M)x1+(4131/2)x2+(5531/5+M)x3+(-M)x6+(-M)x7+(-15M) → maxРешим систему уравнений относительно базисных переменных: x4, x5, x8, x9Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,10 000,250000,0,0,5,10) Базисное решение называется допустимым, если оно неотрицательно.

БазисBx1x2x3x4x5x6x7x8x9x410000196182762/5 100 000×5 250 000 194 028 201 096 249 344×8 500 100−1010×910 100 000−101F (X0)-15M-3561/2-M-4131/2−5531/5-M00MM00Переходим к основному алгоритму симплекс-метода. Итерация № 0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai3и из них выберем наименьшее: min (10 000: 1522/5, 250 000: 1410, 5: 1 , —) = 5 Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

БазисBx1x2x3x4x5x6x7x8x9minx4100001961821522/510 000 065 235/381×525 000 019 402 820 138 143 517 245 440/141×8 500 100−10 105×910 100 000−101-F (X1)-15M-3561/2-M-4131/2−5531/5-M00MM0004.

Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x8 в план 1 войдет переменная x3. Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=1 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x3 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ — (А*В)/РЭ СТЭ — элемент старого плана, РЭ — разрешающий элемент (1), А и В — элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Получаем новую симплекс-таблицу: БазисBx1x2x3x4x5x6x7x8x9x49238196182010762/50−762/50×52 429 501 940 281 997 524 992−14 100×3 500 100−1010×910 100 000−101F (X1)2766−10M-3561/2-M-4131/2000;5531/5M5531/5+M0Итерация № 1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 3.

Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1и из них выберем наименьшее: min (9238: 196, 242 950: 1940 , —, 10: 1) = 10 Следовательно, 4-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки. БазисBx1x2x3x4x5x6x7x8x9minx492381961820101522/50−1522/504 713/98×52 429 501 940 281 997 524 992−1 410 012 545/194×3 500 100−1010-x910100000−10110F (X2)2766−10M-3561/2-M-4131/2000;5531/5M5531/5+M004. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x9 плана 1 на разрешающий элемент РЭ=1 На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x1 плана 2 записываем нули. Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Получаем новую симплекс-таблицу: БазисBx1x2x3x4x5x6x7x8x9x472780182010762/5196−762/5−196×52 235 500 282 000 112 091 136;1410−1940×3 500 100−1010×110 100 000−101F (X2)63310−4131/2000;5531/5−3561/25 531/5+M3561/2+MИтерация № 2. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai6и из них выберем наименьшее: min (7278: 1522/5, 223 550: 1410 , — , —) = 4796/127Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1522/5) и находится на пересечении ведущего столбца и ведущей строки. БазисBx1x2x3x4x5x6x7x8x9minx4727801820101522/5196−1522/5−1 964 796/127×52 235 500 282 000 112 091 136;1410−194 015 877/141×3 500 100−1010-x110100000−101-F (X3)63310−4131/2000;5531/5−3561/25 531/5+M3561/2+M04. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 3 войдет переменная x6. Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x4 плана 2 на разрешающий элемент РЭ=1522/5На месте разрешающего элемента в плане 3 получаем 1. В остальных клетках столбца x6 плана 3 записываем нули. Таким образом, в новом плане 3 заполнены строка x6 и столбец x6. Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.

Получаем новую симплекс-таблицу: БазисBx1x2x3x4x5x6x7x8x9x66065/1 270 455/38105/76 201 490/381−1-490/381×519 839 200/1270144290/1270−1175/1 271 016 080/1270−16 080/127×36 700/1270455/38 115/76200490/3810−490/381×110 100 000−101F (X3)3274972/127 024 737/2540380/12 700 354 245/254M-354 245/254+M1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы: БазисBx1x2x3x4x5x6x7x8x9x66065/1 270 455/38105/76 201 490/381−1-490/381×519 839 200/1270144290/1270−1175/1 271 016 080/1270−16 080/127×36 700/1270455/38 115/76200490/3810−490/381×110 100 000−101F (X4)3274972/127 024 737/2540380/12 700 354 245/254M-354 245/254+M Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Оптимальный план можно записать так: x3 = 5296/127×1 = 10 F (X) = 5531/5•5296/127 + 3561/2•10 = 3 274 972/127Метод Гомори. В полученном оптимальном плане присутствуют дробные числа.

По 1-у уравнению с переменной x6, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 96/127, составляем дополнительное ограничение: q1 — q11•x1 — q12•x2 — q13•x3 — q14•x4 — q15•x5 — q16•x6 — q17•x7≤0 q1 = b1 — [b1] = 4796/127 — 47 = 96/127q11 = a11 — [a11] = 0 — 0 = 0 q12 = a12 — [a12] = 174/381 — 1 = 74/381q13 = a13 — [a13] = 0 — 0 = 0 q14 = a14 — [a14] = 5/762 — 0 = 5/762q15 = a15 — [a15] = 0 — 0 = 0 q16 = a16 — [a16] = 1 — 1 = 0 q17 = a17 — [a17] = 1109/381 — 1 = 109/381Дополнительное ограничение имеет вид: 96/127−74/381×2−5/762×4−109/381×7 ≤ 0 Преобразуем полученное неравенство в уравнение: 96/127−74/381×2−5/762×4−109/381×7 + x8 = 0 коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу. Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F (x) = -F (X). БазисBx1x2x3x4x5x6x7x8x66065/1 270 455/38105/76 201 490/3810×519 839 200/1270144290/1270−1175/1 271 016 080/1270×36 700/1270455/38 115/76200490/3810×110 100 000−10×8−96/1270−74/3810−5/76 200−109/3811F (X0)-4 159 195/1270−62 775/2540−461/12 700−90 161/25401.

Проверка критерия оптимальности. План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 5-ая строка, а переменную x8 следует вывести из базиса.

3. Определение новой базисной переменной. Минимальное значение θ соответствует 4-му столбцу, т. е. переменную x4 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-5/762). БазисBx1x2x3x4x5x6x7x8x64796/1 270 174/38105/762 011 109/3810×515 621 422/1270113618/1270−932/1 271 012 678/1270×35 296/1270174/38 115/762001109/3810×110 100 000−10×8−96/1270−74/3810−5/76 200−109/3811F (X0)-3 274 972/1270−24 737/2540−380/12 700−354 245/2540θ - -24 737/254: (-74/381) = 127 269/148 — -380/127: (-5/762) = 5531/5 — - -354 245/254: (-109/381) = 1 240 163/218 — 4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

БазисBx1x2x3x4x5x6x7x8x64701000111×5 157 280 014 100 011 008−1410×35 201 100 011×110 100 000−10×4576/50 148/50100218/5−762/5F (X0)-2 607 365 753/806450−1397/100 000−1967/10−2766/5 В полученном оптимальном плане присутствуют дробные числа. По 5-у уравнению с переменной x4, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 1/5, составляем дополнительное ограничение: q5 — q51•x1 — q52•x2 — q53•x3 — q54•x4 — q55•x5 — q56•x6 — q57•x7 — q58•x8≤0 q5 = b5 — [b5] = 1151/5 — 115 = 1/5q51 = a51 — [a51] = 0 — 0 = 0 q52 = a52 — [a52] = 293/5 — 29 = 3/5q53 = a53 — [a53] = 0 — 0 = 0 q54 = a54 — [a54] = 1 — 1 = 0 q55 = a55 — [a55] = 0 — 0 = 0 q56 = a56 — [a56] = 0 — 0 = 0 q57 = a57 — [a57] = 433/5 — 43 = 3/5q58 = a58 — [a58] = -1522/5 + 153 = 3/5Дополнительное ограничение имеет вид: 1/5−3/5×2−3/5×7−3/5×8 ≤ 0 Преобразуем полученное неравенство в уравнение: 1/5−3/5×2−3/5×7−3/5×8 + x9 = 0 коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу. БазисBx1x2x3x4x5x6x7x8x9x647010001110×5 157 280 014 100 011 008−14 100×352 011 000 110×110 100 000−100×4576/50 148/50100218/5−762/50×9−1/50−3/50 000−3/5−3/51F (X0)-2 607 365 753/806450−1397/100 000−1967/10−2766/501. Проверка критерия оптимальности. План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 6-ая строка, а переменную x9 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т. е. переменную x2 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3/5). БазисBx1x2x3x4x5x6x7x8x9x647010001110×5 157 280 014 100 011 008−14 100×352 011 000 110×110 100 000−100×41 151/50293/50 100 433/5−1522/50×9−1/50−3/50 000−3/5−3/51F (X0)-3 233 132 258/806450−1397/100 000−1967/10−5531/50θ - -1397/10: (-3/5) = 2325/6 — - - - -1967/10: (-3/5) = 3275/6−5531/5: (-3/5) = 922 — 4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

БазисBx1x2x3x4x5x6x7x8x9x6140/3 000 001 005/3×5 156 810 000 010−880−28 202 350×3155/3 001 000 005/3×110 100 000−100×4316/300 010 014−182 148/3×21/301 000 011−5/3F (X0)-193 709/6000000−57−827/2−1397/6 В полученном оптимальном плане присутствуют дробные числа. По 1-у уравнению с переменной x6, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение: q1 — q11•x1 — q12•x2 — q13•x3 — q14•x4 — q15•x5 — q16•x6 — q17•x7 — q18•x8 — q19•x9≤0 q1 = b1 — [b1] = 462/3 — 46 = 2/3q11 = a11 — [a11] = 0 — 0 = 0 q12 = a12 — [a12] = 0 — 0 = 0 q13 = a13 — [a13] = 0 — 0 = 0 q14 = a14 — [a14] = 0 — 0 = 0 q15 = a15 — [a15] = 0 — 0 = 0 q16 = a16 — [a16] = 1 — 1 = 0 q17 = a17 — [a17] = 0 — 0 = 0 q18 = a18 — [a18] = 0 — 0 = 0 q19 = a19 — [a19] = 12/3 — 1 = 2/3Дополнительное ограничение имеет вид: 2/3−2/3×9 ≤ 0 Преобразуем полученное неравенство в уравнение: 2/3−2/3×9 + x10 = 0 коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу. БазисBx1x2x3x4x5x6x7x8x9x10×6140/3 000 001 005/30×5 156 810 000 010−880−282 023 500×3155/3 001 000 005/30×110 100 000−1000×4316/300 010 014−182 148/30×21/301 000 011−5/30×10−2/300 000 000−2/31F (X0)-193 709/6000000−57−827/2−1397/601. Проверка критерия оптимальности. План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 7-ая строка, а переменную x10 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует 9-му столбцу, т. е. переменную x9 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2/3). БазисBx1x2x3x4x5x6x7x8x9x10×6462/30 000 010 012/30×5 156 810 000 010−880−282 023 500×3512/30 010 000 012/30×110 100 000−1000×41 051/300010014−182 491/30×21/301 000 011−12/30×10−2/300 000 000−2/31F (X0)-322 845/6000000−57−4131/2−2325/60θ - - - - - - - - -2325/6: (-2/3) = 3491/4 — 4. Пересчет симплекс-таблицы.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. БазисBx1x2x3x4x5x6x7x8x9x10×6 450 000 010 005/2×5 154 460 000 010−880−282 003 525×3 500 010 000 005/2×110 100 000−1000×45 600 010 014−182 074×22 010 000 110−5/2×91 000 000 001−3/2F (X0)-32 052 000 000−57−827/20−1397/4Решение получилось целочисленным. Нет необходимости применять метод Гомори. Оптимальный целочисленный план можно записать так: x6 = 45×5 = 154 460×3 = 50×1 = 10×4 = 56×2 = 2×9 = 1 F (X) = 0•45 + 0•154 460 + 5531/5•50 + 3561/2•10 + 0•56 + 4131/2•2 = 32 052.

Результаты проведения расчетов по решению модели № 2 и принятие оптимальных тактических решений.

Решим задачу в Excel. Пользуемся «Данные-Поиск решения».Вносим параметры в модель:

Получаем решение:

Таким образом, получили оптимальную производственную программу. Оценка эффективности внедрения предлагаемых решений в управлении авиационным предприятием.

Так как в результате расчета получена оптимальная производственная программа, то решение является эффективным.

Заключение

.

Во время выполнения курсовой работы были выполнены все поставленные задача и достигнута поставленная основная цель. С помощью различных экономико-математических моделей была разработана концепция для оптимизации производства предприятия РСК «Миг».С помощью средства «поиск решений» были решены стратегические и тактические задачи, которые позволили нам повысить конкурентоспособность предприятия на рынке. Расчеты, произведённые по разным методам, позволили выбрать наиболее подходящий вариант дальнейшего управления авиационным предприятием и максимизации роста продаж. Список использованной литературы1) Комарова Н. В. «Методические указания по выполнению курсовой работы по дисциплине «Методы оптимизации и исследования операций» М.: Доброе слово, 2013"2) Есипов Б. А.. «Методы оптимизации и исследования операций. Конспект лекций» Самара.: Изд-во Самарского государственного аэрокосмического университета, 2007.