Модели линейного программирования, теория игр и их применение в экономике.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 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