УНИВЕРСИТЕТРОССИЙСКОЙ АКАДЕМИИ ОБРАЗОВАНИЯФакультет Бизнес, Маркетинг, КоммерцияДисциплина Теория принятия решенийТема контрольной работы Задачи по четв ртому варианту Ф.И.О. студента СпрыжковИгорь МаксимовичКурс 4. Семестр 7. Номер зачетнойкнижки 1818.Дата сдачи Ф.И.О. преподавателя Асташкин С.В.Оценка Подпись Дата проверки
Задача1УсловиеРешить симплекс-методом задачу, предварительно приведя е кканоническому виду x1 x2 x3 7×4 8594 max-x1 2×2 x3 x4 8804 22×1 x2 x3 2×4 8804 122×1 3×2 4×3 2×4 8804 6xj 8805 0, j 1, 2, 3, 4РешениеОбщий вид задачи линейного программирования в каноническойформе 8721 aij bi, i 1, 2, , nxj 8805 0, j 1, 2, , n, n 1, n m 8721 pjxj 8594 maxЭкономико-математическая модель рассматриваемой задачи вканонической форме будет иметь вид -1×1 2×2 1×3 1×4 1×5 0x6 0x7 2 2×1 1×2 1×3 –
2×4 0x5 1×6 0x7 12 2×1 3×2 4×3 2×4 0x5 0x6 1×7 6 xj 8805 0, j 1, 2, , 7×1 x2 x3 7×4 0x5 0x6 0x7 8594 maxТ.е. в ней линейная форма максимизируется, все ограниченияявляются равенствами, все переменные удовлетворяют условию неотрицательности.Система уравнений имеет предпочитаемый вид базиснымипеременными являются переменные Х5, Х6, Х7,правые части неотрицательны. Исходноеопорное решение, дающее координаты исходной угловой
точки, имеет вид Х 0, 0,0, 0, 2, 12, 6 т.Все остальные вычисления и действия удобно производит втабличной форме табл. 1 3 .Решение задачи потребовало три итерации, каждой из которыхсоответствует симплекс-таблица.В первую строку первой симплекс-таблицы занесены все данныепервого уравнения, во вторую второго и т.д.В каждой из таблиц во втором столбце Бx указаны базисныенеизвестные. Неизвестные, не входящие в базис, равны нулю. Значения базисныхнеизвестных записаны в третьем столбце
X0 . Нижний элемент этого столбца является значениемкритерия оптимальности на данном шаге. В первом столбце Pj представлены коэффициентыпри базисных неизвестных, взятые из критерия оптимальности. Каждый из столбцов X1 X4 соответствуетосновным переменным задачи, а столбцов X5 X7 дополнительным переменным задачи. Последние элементы этих столбцов образуютнижнюю строку, содержащую элементы 8710 J. С их помощью определяется,достигнут ли оптимум, а если не достигнут, то какое небазисное
неизвестноеследует ввести в базис, чтобы улучшить план. Элементы последнего столбца 952 позволяют найти то из прежних базисных неизвестных, которое следуетвывести из базиса, чтобы улучшить план. Разрешающий элемент, расположенный напересечении столбца, вводимого в базис неизвестного, и строки неизвестного,выводимого из базиса, выделен в каждой таблице.Рассмотрим первую симплексную таблицу решения задачи.
План задачи находится в столбцах Бх и Х0.Элементы столбцов Х1 Х7 являютсякоэффициентами замещения неизвестных. Они показывают, в каком соотношении любыеиз неизвестных могут заменить базисные переменные в плане данного шага.Элементы нижней строки столбцов Х1 Х7показывают размер уменьшения значения критерия оптимальности от замены базисныхнеизвестных Хj.Показатель 916 j рассчитывается перемножением элемента первого столбцатаблицы
Pj на элемент столбца Хjс последующим вычитанием соответствующего элемента Pj.После нахождения L0 и 916 j, проверяется условий оптимальности все 916 j gt 0 инеразрешимости если найдется хотя бы один 916 j lt 0 такой, что все элементысоответствующего столбца отрицательны .Наличие отрицательных 916 j свидетельствуето том, что найденный план производства не является оптимальным, так как имеютсявозможности увеличения прибыли. В качестве разрешающего столбца неизвестной может бытьвзят
y3 – ?Свед м задачу к каноническому виду 2y1 y2 y3 y4 1 -y1 2y2 – y3 y5 -1 y1 2y2 3y3 y6 -6 y1 3y2 y3 y7 2 2y1 y2 3y3 y8 12max 3y1 2y2 y3 – ?Все остальные вычисления и действия удобно производит втабличной форме табл. 4 6 .Таблица 4Симплексная таблица первого плана задачи Pi Бy y0 3 2 1 0 0 0 0 0 952 y1 y2 y3 y4 y5 y6 y7 y8 0 y4 1 2 -1 1 1 0 0 0 0 0.5 0 y5 -1 -1 2 -1 0 1 0 0 0 1 0 y6 -6 1 -2 3 0 0 1 0 0 – 0 y7 2 1 3 1 0 0 0 1 0 2 0 y8 12 2 1 3 0 0 0 0 1 6 8710 j 0 -3 -2 -1 0 0 0 0 0
Таблица 5Симплексная таблица второго плана задачи Pi Бy y0 3 2 1 0 0 0 0 0 952 y1 y2 y3 y4 y5 y6 y7 y8 3 y1 0.5 1 -0.5 0.5 0.5 0 0 0 0 – 0 y5 -7 0 0 2 0 1 1 0 0 8734 0 y6 -8 0 -5 2 0 0 1 -1 0 1.6 0 y7 1 0 5 0 0 1 0 1 0 0.2 0 y8 11 0 2 2 -1 0 0 0 1 5.5 8710 j 1.5 0 -3.5 0.5 1.5 0 0 0 0 Таблица 6Симплексная таблица третьего плана задачи Pi Бy y0 3 2 1 0 0 0 0 0 y1 y2 y3 y4 y5 y6 y7 y8 3 y1 0.6 1 0 0.5 0.5 0.1 0 0.1 0 0 y5 -7 0 0 2 0 1 1 0 0 0
y6 -7 0 0 2 0 1 1 0 0 2 y2 0.2 0 1 0 0 0.2 0 0.2 0 0 y8 10.6 0 0 2 -1 -0.4 0 -0.4 1 8710 j 2.2 0 0 0.5 1.5 0.3 0 0.3 0 y4 8596 x1 x1 1y5 8596 x2 x2 0y6 8596 x3 x3 0y7 8596 x4 x4 1y8 8596 x5 x5 0Ответ оптимальное решение х 1 0 0 10 , т.е. х1 1, х2 0, х3 0, х4 1, х5 0.Задача3Для рытья котлована объ мом 1440 м3 строителиполучили три экскаватора. Мощный экскаватор производительностью 22.5 м3 часрасходует в час 10 литров бензина. Аналогичные характеристики среднегоэкскаватора 10 м3 час и 10 3 л час, малого 5 м3 и 2 л час.
Экскаваторы могут работать одновременно, не мешаядруг другу. Запас бензина у строителей ограничен и равен 580 литров. Если рытькотлован только малым экскаватором, то бензина заведомо хватит, но это будеточень долго. Каким образом следует использовать имеющуюся технику, чтобы выполнитьработу как можно скорее?РешениеПусть экскаваторы работали x1, x2, x3 час соответственно,тогда22.5×1 10×2 5×3 1440 объемработ10×1 10 3
x2 2×3 8804 580 ограничения по расходу бензинаx1,x2, x3 8805 0 945 max x1, x2, x3 8594 minЗначение 945 равно наибольшему из значений x1,x2, x3 и это значениенужно взять наименьшим.Решим задачу графически.Множество допустимых значений фигура ABCD.Определим координаты точки A 22.5×1 10×2 5 0 1440 10×1 10 3×2 2 0 580 30×1 10×2 17407.5×1 300×1 40 час x2 1440 22.5 40 10 54 час Определим координаты точки
B 22.5×1 10 0 5×3 144010×1 10 3 0 2×3 580 45×1 10×3 288050×1 10×3 29005×1 20×1 4×3 1440 22.5 4 5 270Итак, определены координаты всех точек A 40 54 0 B 4 0 270 C 64 0 0 D 58 0 0 Искомое решение задачи точка A.Ответ оптимальный режим работы экскаваторов Мощный экскаватор 40часов, Средний экскаватор 54 часа, Малый экскаватор не используется.Задача4В пекарне для выпечки четырех видов хлеба используется мукадвух
сортов, маргарин и яйца. Имеющееся оборудование, производственные площадии поставки продуктов таковы, что в сутки можно переработать не более 290 кгмуки первого сорта, 150 кг муки второго сорта, 50 кг маргарина, 1280 шт. яиц. Втаблице приведены нормы расхода продуктов, а также прибыль от продажи 1 кгхлеба каждого вида Таблица 7 Наименование продукта Нормы расхода на 1 кг хлеба по видам 1 2 3 4 мука 1 сорта, кг 0.5 0.5 0 0
мука 2 сорта, кг 0 0 0.5 0.5 маргарин, кг 0.125 0 0 0.125 яйцо, шт. 2 1 1 1 прибыль, за 1 кг 14 12 5 6 Требуется определить суточный план выпечки хлеба,максимизирующий прибыль.Решение 0.5×1 0.5×2 0 x3 0 x4 8804 290 0 x1 0 x2 0.5×3 0.5×4 8804 1500.125×1 0 x2 0 x3 0.125×4 8804 50 2×1 1×1 1×3 1×4 8804 1280 14×1 12×2 5×3 6×4 8594 maxВсе остальные вычисления и действия удобно производит втабличной форме табл. 8 11 .Таблица 8Симплексная таблица первого плана задачи
Pi Бx X0 14 12 5 6 0 0 0 0 952 x1 x2 x3 x4 x5 x6 x7 x8 0 x5 290 0.5 0.5 0 0 1 0 0 0 580 0 x6 150 0 0 0.5 0.5 0 1 0 0 8734 0 x7 50 0.125 0 0 0.125 0 0 1 0 400 0 x8 1280 2 1 1 1 0 0 0 1 640 8710 j 0 -14 -12 -5 -6 0 0 0 0 Таблица 9Симплексная таблица второго плана задачи Pi Бx X0 14 12 5 6 0 0 0 0 952 x1 x2 x3 x4 x5 x6 x7 x8 0 x5 90 0 0.5 0 -0.5 1 0 -4 0 180 0 x6 150 0 0 0.5 0.5 0 1 0 0 8734 14 x1 400 1 0 0 1 0 0 8 0 8734 0 x8 120 0 -1 1 1 -4 0 0 1 –
8710 j 5600 0 -12 -5 -8 0 0 112 0 Таблица 10Симплексная таблица третьего плана задачи Pi Бx X0 14 12 5 6 0 0 0 0 952 x1 x2 x3 x4 x5 x6 x7 x8 12 x2 180 0 1 0 -1 2 0 -8 0 8734 0 x6 150 0 0 0.5 0.5 0 1 0 0 300 14 x1 400 1 0 0 1 0 0 8 0 8734 0 x8 300 0 0 1 0 -2 0 -8 1 300 8710 j 7760 0 0 -5 -4 24 0 16 0 Таблица 11Симплексная таблица четвертого плана задачи Pi Бx X0 14 12 5 6 0 0 0 0 x1 x2 x3 x4 x5 x6 x7 x8 12 x2 180 0 1 0 -1 2 0 -8 0 5 x3 300 0 0 1 1 0 2 0 0 14
x1 400 1 0 0 1 0 0 8 0 0 x8 300 0 0 0 -1 -2 -2 -8 1 8710 j 9260 0 0 0 1 12 10 16 0 Ответ суточный план выпуска продукции хлеб 1-говида 400 кг, 2-го вида 180 кг 3-го вида 300 кг, 4-го вида 0 кг. Списокиспользованных источников Зубков М.Я. Математические структуры иматематическое моделирование экономики Учебное пособие. Вып. 3в.Математическое программирование.
М. Изд-во УРАО, 1996. 68 с. Алешина И.Ф. Анализ и оценка хозяйственныхрешений Методические указания к изучению курса. М. Изд-во РОУ, 1996. 28с.