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

С помощи рассмотренных моделей можно строить прогнозы и планы для компании, а в случае изменений каких либо показателей и значений, в модель можно легко внести изменения. Использование этой методики, построенной на основе SWOT-таблицы и модели линейного программирования, позволяет решать задачу выбора оптимальной стратегии – набора мероприятий на прогнозный период, обеспечивающих получение максимального роста продаж при ограниченном бюджете.Решение математических моделей изучаемого объекта средства ExcelПринятые программы стратегических мероприятий по развитию предприятияВ результате анализа в предыдущей главе выяснилось, что для повышения продаж необходимо провести ряд мероприятий. Теперь рассмотрим еще одну задачу по увеличению прибыли предприятия – оптимальное распределения ресурсов. Поставим следующую задачу. Пусть - программа производства самолетов МиГ-29СД, - программа производства самолетов МиГ-29СМ, - программа производства самолетов МиГ-31Э, Введем ограничения:ограничения по производственным материалам:ограничения по трудозатратам:ограничения по государственной программе:ограничение по зарубежным контрактам:Целевая функция:Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 3561/2x1 + 4131/2x2 + 5531/5x3 при следующихусловиях-ограничений. 196x1 + 182x2 + 1522/5x3≤10000 1940x1 + 2820x2 + 1410x3≤250000 x3≥5 x1≥10 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус. В 4-м неравенстве смысла (≥) вводим базисную переменную x7 со знаком минус. 196x1 + 182x2 + 1522/5x3 + 1x4 + 0x5 + 0x6 + 0x7 = 10000 1940x1 + 2820x2 + 1410x3 + 0x4 + 1x5 + 0x6 + 0x7 = 250000 0x1 + 0x2 + 1x3 + 0x4 + 0x5-1x6 + 0x7 = 5 1x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 = 10 Введем искусственные переменные x: в 3-м равенстве вводим переменную x8; в 4-м равенстве вводим переменную x9; 196x1 + 182x2 + 1522/5x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 = 10000 1940x1 + 2820x2 + 1410x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 = 250000 0x1 + 0x2 + 1x3 + 0x4 + 0x5-1x6 + 0x7 + 1x8 + 0x9 = 5 1x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 + 1x9 = 10 Для постановки задачи на максимум целевую функцию запишем так: F(X) = 3561/2x1+4131/2x2+5531/5x3 - Mx8 - Mx9 → maxЗа использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается. Из уравнений выражаем искусственные переменные: x8 = 5-x3+x6 x9 = 10-x1+x7которые подставим в целевую функцию: F(X) = 3561/2x1 + 4131/2x2 + 5531/5x3 - 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,10000,250000,0,0,5,10) Базисное решение называется допустимым, если оно неотрицательно. БазисBx1x2x3x4x5x6x7x8x9x410000196182762/5100000x5250000194028201410010000x8500100-1010x910100000-101F(X0)-15M-3561/2-M-4131/2-5531/5-M00MM00Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai3и из них выберем наименьшее: min (10000 : 1522/5 , 250000 : 1410 , 5 : 1 , - ) = 5 Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки. БазисBx1x2x3x4x5x6x7x8x9minx4100001961821522/510000065235/381x525000019402820141001000017743/141x8500100-10105x910100000-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/50x52429501940282000114100-14100x3500100-1010x910100000-101F(X1)2766-10M-3561/2-M-4131/2000-5531/5M5531/5+M0Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1и из них выберем наименьшее: min (9238 : 196 , 242950 : 1940 , - , 10 : 1 ) = 10 Следовательно, 4-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки. БазисBx1x2x3x4x5x6x7x8x9minx492381961820101522/50-1522/504713/98x52429501940282000114100-1410012545/194x3500100-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-196x52235500282000114101940-1410-1940x3500100-1010x110100000-101F(X2)63310-4131/2000-5531/5-3561/25531/5+M3561/2+MИтерация №2. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai6и из них выберем наименьшее: min (7278 : 1522/5 , 223550 : 1410 , - , - ) = 4796/127Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1522/5) и находится на пересечении ведущего столбца и ведущей строки. БазисBx1x2x3x4x5x6x7x8x9minx4727801820101522/5196-1522/5-1964796/127x52235500282000114101940-1410-194015877/141x3500100-1010-x110100000-101-F(X3)63310-4131/2000-5531/5-3561/25531/5+M3561/2+M04. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 3 войдет переменная x6. Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x4 плана 2 на разрешающий элемент РЭ=1522/5На месте разрешающего элемента в плане 3 получаем 1. В остальных клетках столбца x6 плана 3 записываем нули. Таким образом, в новом плане 3 заполнены строка x6 и столбец x6. Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника. Получаем новую симплекс-таблицу: БазисBx1x2x3x4x5x6x7x8x9x66065/1270455/38105/76201490/381-1-490/381x519839200/1270144290/1270-1175/1271016080/1270-16080/127x36700/1270455/38115/76200490/3810-490/381x110100000-101F(X3)3274972/127024737/2540380/12700354245/254M-354245/254+M1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы: БазисBx1x2x3x4x5x6x7x8x9x66065/1270455/38105/76201490/381-1-490/381x519839200/1270144290/1270-1175/1271016080/1270-16080/127x36700/1270455/38115/76200490/3810-490/381x110100000-101F(X4)3274972/127024737/2540380/12700354245/254M-354245/254+M Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Оптимальный план можно записать так: x3 = 5296/127x1 = 10 F(X) = 5531/5•5296/127 + 3561/2•10 = 3274972/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/381x2-5/762x4-109/381x7 ≤ 0 Преобразуем полученное неравенство в уравнение: 96/127-74/381x2-5/762x4-109/381x7 + x8 = 0 коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу. Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F(x) = -F(X). БазисBx1x2x3x4x5x6x7x8x66065/1270455/38105/76201490/3810x519839200/1270144290/1270-1175/1271016080/1270x36700/1270455/38115/76200490/3810x110100000-10x8-96/1270-74/3810-5/76200-109/3811F(X0)-4159195/1270-62775/2540-461/12700-90161/25401. Проверка критерия оптимальности. План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 5-ая строка, а переменную x8 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-5/762). БазисBx1x2x3x4x5x6x7x8x64796/1270174/38105/762011109/3810x515621422/1270113618/1270-932/1271012678/1270x35296/1270174/38115/762001109/3810x110100000-10x8-96/1270-74/3810-5/76200-109/3811F(X0)-3274972/1270-24737/2540-380/12700-354245/2540θ - -24737/254 : (-74/381) = 127269/148 - -380/127 : (-5/762) = 5531/5 - - -354245/254 : (-109/381) = 1240163/218 - 4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. БазисBx1x2x3x4x5x6x7x8x64701000111x5157280014100010530-1410x35201100011x110100000-10x4576/50148/50100218/5-762/5F(X0)-2607365753/806450-1397/100000-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/5x2-3/5x7-3/5x8 ≤ 0 Преобразуем полученное неравенство в уравнение: 1/5-3/5x2-3/5x7-3/5x8 + x9 = 0 коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу. БазисBx1x2x3x4x5x6x7x8x9x647010001110x5157280014100010530-14100x352011000110x110100000-100x4576/50148/50100218/5-762/50x9-1/50-3/50000-3/5-3/51F(X0)-2607365753/806450-1397/100000-1967/10-2766/501. Проверка критерия оптимальности. План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 6-ая строка, а переменную x9 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3/5). БазисBx1x2x3x4x5x6x7x8x9x647010001110x5157280014100010530-14100x352011000110x110100000-100x41151/50293/50100433/5-1522/50x9-1/50-3/50000-3/5-3/51F(X0)-3233132258/806450-1397/100000-1967/10-5531/50θ - -1397/10 : (-3/5) = 2325/6 - - - - -1967/10 : (-3/5) = 3275/6-5531/5 : (-3/5) = 922 - 4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. БазисBx1x2x3x4x5x6x7x8x9x6140/3000001005/3x5156810000010-880-28202350x3155/3001000005/3x110100000-100x4316/300010014-182148/3x21/301000011-5/3F(X0)-193709/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/3x9 ≤ 0 Преобразуем полученное неравенство в уравнение: 2/3-2/3x9 + x10 = 0 коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу. БазисBx1x2x3x4x5x6x7x8x9x10x6140/3000001005/30x5156810000010-880-282023500x3155/3001000005/30x110100000-1000x4316/300010014-182148/30x21/301000011-5/30x10-2/300000000-2/31F(X0)-193709/6000000-57-827/2-1397/601. Проверка критерия оптимальности. План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 7-ая строка, а переменную x10 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует 9-му столбцу, т.е. переменную x9 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2/3). БазисBx1x2x3x4x5x6x7x8x9x10x6462/30000010012/30x5156810000010-880-282023500x3512/30010000012/30x110100000-1000x41051/300010014-182491/30x21/301000011-12/30x10-2/300000000-2/31F(X0)-322845/6000000-57-4131/2-2325/60θ - - - - - - - - -2325/6 : (-2/3) = 3491/4 - 4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. БазисBx1x2x3x4x5x6x7x8x9x10x6450000010005/2x5154460000010-880-282003525x3500010000005/2x110100000-1000x45600010014-182074x22010000110-5/2x91000000001-3/2F(X0)-32052000000-57-827/20-1397/4Решение получилось целочисленным. Нет необходимости применять метод Гомори. Оптимальный целочисленный план можно записать так: x6 = 45 x5 = 154460 x3 = 50 x1 = 10 x4 = 56 x2 = 2 x9 = 1 F(X) = 0•45 + 0•154460 + 5531/5•50 + 3561/2•10 + 0•56 + 4131/2•2 = 32052Результаты проведения расчетов по решению модели №2 и принятие оптимальных тактических решенийРешим задачу в Excel.Пользуемся «Данные-Поиск решения».Вносим параметры в модель:Получаем решение:Таким образом, получили оптимальную производственную программу. Оценка эффективности внедрения предлагаемых решений в управлении авиационным предприятиемТак как в результате расчета получена оптимальная производственная программа, то решение является эффективным. ЗаключениеВо время выполнения курсовой работы были выполнены все поставленные задача и достигнута поставленная основная цель. С помощью различных экономико-математических моделей была разработана концепция для оптимизации производства предприятия РСК «Миг».С помощью средства «поиск решений» были решены стратегические и тактические задачи, которые позволили нам повысить конкурентоспособность предприятия на рынке.Расчеты, произведённые по разным методам, позволили выбрать наиболее подходящий вариант дальнейшего управления авиационным предприятием и максимизации роста продаж.Список использованной литературы1) Комарова Н.В. «Методические указания по выполнению курсовой работы по дисциплине «Методы оптимизации и исследования операций» М.: Доброе слово, 2013»2) Есипов Б.А. . «Методы оптимизации и исследования операций. Конспект лекций» Самара.: Изд-во Самарского государственного аэрокосмического университета, 2007