Контрольная Методы оптимальных решений

Контрольная по "Методы оптимальных решений", сделана лично, для нархоза, группы Финансы и кредит, Вариант №3. Зачет 100%. ...

Содержит практические задания и тестовую часть.

Введения нет по заданию.

При дальнейшем увеличении лимита сырья ОДР будет представлять собой четырехугольник, сторонами которого являются оси координат и ограничения по сырью и оборудованию. При этом точка, соответствующая максимальному значению выручки будет находиться по-прежнему на оси абсцисс. Из этого делаем вывод, что прирост максимума выручки будет таким же.Такая ситуация будет качественно сохраняться до тех пор, пока оптимальная программа не совпадет с точкой В, имеющей координаты . В данной точке, наряду с ограничением по сырью и оборудованию, будет ограничение по труду. Поэтому расход сырья на программу В покажет правую границу диапазона устойчивости предельной эффективности . Каждый следующий за этой границей килограмм сырья будет расходоваться с меньшей предельной эффективностью.Для расчета расхода сырья на программу В подставим ее координаты в левую часть ограничения по сырью , а именно:.Результаты расчетов показали, что каждый дополнительный килограмм сырья в диапазоне от 1 до 122,5 будет давать прирост максимума выручки 162,33 руб.При дальнейшем увеличении лимита сырья ОДР будет представлять собой пятиугольник, сторонами которого являются оси координат и ограничения по всем трем видам ресурсов. При этом точка, соответствующая максимальному значению выручки будет находиться на прямой ВС, в точке пересечения прямых по сырью и труду. Характеризует эти программы тот очевидный факт, что по ним выпускается два продукта , . Ограничение по оборудованию проходит выше оптимальных программ, т. е. оборудование не является лимитирующим ресурсом для этих программ до того момента, пока пунктирная линия (3) не пройдет через точку С.Отсюда из первой группы условий (1.3) следует, что . Из группы условий (1.4) следует, что, если оба продукта выпускаются, должны выполняться равенства;.Из этих двух уравнений, с учетом , перейдем к решению следующей системы: Решая систему, находим, что . Для того, чтобы получить правую границу диапазона устойчивости вычисленной предельной эффективности , необходимо рассчитать расход сырья для программы С..Результаты расчетов показали, что каждый дополнительный килограмм сырья в диапазоне от 122,5 до 149 будет давать прирост выручки на 113,67 руб.Пусть, наконец, . Тогда оптимальная программа С окажется ниже уровня лимита по сырью. Эту ситуацию отражает положение пунктирной прямой (4). Сырье становится избыточным относительно оптимальной программы С, и его предельная эффективность становится нулевой, в диапазоне (149; ∞). На этом исследование функции предельной эффективности сырья для данного предприятия завершается.На основе результатов выполненного анализа получим табличную запись функции предельной эффективности поступающего сырья для данного предприятия (табл. 2.1) и табличное предоставление функции зависимости максимума выручки от увеличения производственного потребления сырья (табл. 2.2). Используя информацию из этих таблиц, построим графики этих функций (рис. 4 и рис. 5).Таблица 2.1Функция предельной эффективности сырьяПредельная эффективность, (руб./кг)162,33113,670Сырье, r (кг)(0; 122,5](122,5;149](149; ∞)Таблица 2.2 Зависимость максимума выручки от сырьяМаксимум выручки, (руб.)162,33r22898Сырье, r (кг)(0; 122,5](122,5;149](149; ∞)Рис. 4. График изменения предельной эффективностиРис. 5. График максимума выручки в зависимостиот поступления сырьяВид графика на рис. 4 еще раз демонстрирует известный закон убывания эффективности ресурса с ростом объемов его производственного потребления. Ступенчатость графика и наличие точек разрыва функции эффективности объясняется тем, что исследование проводилось на основе линейного моделирования, в общем-то, нелинейных экономических связей.1.5.Текст практической задачи №3Необходимо доставить однородный груз от трех филиалов фирмыпяти потребителям:Предложение филиалов (ед.):Филиал 1Филиал 2Филиал 3582193Спрос потребителей (ед.):потр.1потр.2потр.3потр.4потр.5384164652Известна матрица затрат на доставку единицы груза от каждого поставщика потребителю (руб.).потр.1потр.2потр.3потр.4потр.5Поставщик 189746Поставщик 21011869Поставщик 3754451. Составить ЭММ расчета оптимального плана перевозок.2. Определить исходный опорный план методом северо-западного угла.3. Найти оптимальный план перевозок методом потенциалов и указать соответствующие ему минимальные транспортные затраты.1.6.Решение практической задачи №3Находим ; .Так как , то мы имеем открытую задачу. Вводим фиктивного поставщика с предложением 210-172=38.Транспортная ЭММ имеет вид:;.(3.1)В данной задаче получаем:(3.1)Первоначальный план будем искать по методу северо-западного угла.Для этого первую перевозку помещаем в левый верхний угол, в клетку А1В1. ВАВ1В2В3В4В5 8 38 9 207 4 065810 11 218692175 4 64 4 29593А4000 0 36 0 2383841646521). , 1-й столбец исключаем; 2). , 1-ю строку исключаем;3). , 2-й стлб и 2-ю строку исключаем; 4). , 3-й столбец исключаем;5). , 3-ю строку исключаем; 6). , 4-й столбец исключаем;7). ; 8). .Нулевую перевозку ввели для того, чтобы количество заполненных клеток было равно .Здесь и далее в нижнем правом углу записываем значение перевозки.Стоимость 1-ого плана:.Будем улучшать этот план методом потенциалов: ui- потенциал Аi, vj- потенциал Bj. Тогда: Положим , тогда:.Составим таблицу: ВАВ1(v1=8)В2(v2=9)В3(v3=4)В4(v4=4)В5(v5=4)(u1=0)6083304191000 8 38 9 20-3 7 4 0-2 658(u2=2)0 10 11 21-2 80 6-3 921(u3=0)1 74 5 4 64 4 29-1 593(u4=-4)4 05 00 0 0 36 0 238384164652В верхнем левом углу здесь и далее записываем значение ui+vj-cij. Имеем , следовательно, по критерию оптимальности, первый план не оптимален. Далее поместим перевозку в клетку А4В1, сместив, 36=min(36,38) по циклу, указанному в таблице.Получим новую таблицу. ВАВ1(v1=8)В2(v2=9)В3(v3=4)В4(v4=4)В5(v5=8)(u1=0) 8 250546016573500 9 20-3 7 4 362 658(u2=2)0 10 11 21-2 80 61 921(u3=0)1 74 5 4 64 4 293 593(u4=-8) 0 36-1 0-4 0-4 0 0 238384164652Найдем потенциалы:Положим , тогда:.Стоимость 2-ого плана равна:.Имеем , следовательно, по критерию оптимальности, данный план не оптимален. Далее поместим перевозку в клетку А3В2, сместив, 20=min(20,29) по циклу, указанному в таблице.Получим новую таблицу. ВАВ1(v1=8)В2(v2=5)В3(v3=4)В4(v4=4)В5(v5=8)(u1=0) 8 2-4 9 -3 7 4 562 658(u2=6)4 1048641011811000 11 212 84 65 921(u3=0)1 7 5 20 4 64 4 93 593(u4=-8) 0 36-3 0-4 0-4 0 0 238384164652Найдем потенциалы:Положим , тогда:.Стоимость 3-ого плана равна:.Имеем , следовательно, по критерию оптимальности, данный план не оптимален. Далее поместим перевозку в клетку А2В4, сместив, 9=min(9,21) по циклу, указанному в таблице.Получим новую таблицу. ВАВ1(v1=8)В2(v2=9)В3(v3=8)В4(v4=4)В5(v5=8)(u1=0)51117521336000 8 20 9 1 7 4 562 658(u2=2)0 10 11 122 8 6 91 921(u3=-4)-3 7 5 29 4 64-4 4 -1 593(u4=-8) 0 361 00 0-4 0 0 238384164652Найдем потенциалы:Положим , тогда:.Стоимость 4-ого плана равна:.Имеем , следовательно, по критерию оптимальности, данный план не оптимален. Далее поместим перевозку в клетку А1В5, сместив, 2=min(2,2) по циклу, указанному в таблице.Получим новую таблицу. ВАВ1(v1=6)В2(v2=9)В3(v3=8)В4(v4=4)В5(v5=6)(u1=0)-2 8 0 9 1 7 4 56 6 258(u2=2)-2 1049593517526000 11 122 8 6 9-1 921(u3=-4)-5 7 5 29 4 64-4 4 -4 593(u4=-6) 0 383 02 0-2 0 0 038384164652Найдем потенциалы:Положим , тогда:.Стоимость 5-ого плана равна:.Имеем , следовательно, по критерию оптимальности, данный план не оптимален. Далее поместим перевозку в клетку А2В3, сместив, 12=min(12,64) по циклу, указанному в таблице.Получим новую таблицу. ВАВ1(v1=6)В2(v2=7)В3(v3=6)В4(v4=4)В5(v5=6)(u1=0)-2 8 -2 9 -1 74152902336800041529023368000 4 566477023368000 6 258(u2=2)-2 10-2 11 1365251885950013652518859500 8 12 6 9-1 921(u3=-2)-3 74013202012950040132020129500 5 41 4 52-2 4 -1 593(u4=-6) 0 38401320204470001 00 0-2 0 0 038384164652Найдем потенциалы:Положим , тогда:.Стоимость 6-ого плана равна:.Имеем , следовательно, по критерию оптимальности, данный план не оптимален. Далее поместим перевозку в клетку А4В2, сместив, 0=min(0,56,12,41) по циклу, указанному в таблице.Получим новую таблицу. ВАВ1(v1=7)В2(v2=7)В3(v3=6)В4(v4=4)В5(v5=6)(u1=0)-1 8 -2 9 -1 7 4 56 6 258(u2=2)-1 10-2 11 8 12 6 9-1 921(u3=-2)-2 7 5 41 4 52-2 4 -1 593(u4=-7) 0 38 0 0-1 0-3 0 -1 0 38384164652Найдем потенциалы:Положим , тогда:.Стоимость 7-ого плана не изменилась, так как сместили нулевую перевозку.Для всех клеток данной таблицы выполнены условия оптимальности:1)ui+vj-сij=0 для клеток, занятых перевозками;2)ui+vj-сij≤0 для свободных клеток.Следовательно, данный план является оптимальным.Итак, оптимальный план перевозок следующий: ВАВ1В2В3В4В5562581292141529304164652Стоимость данного плана . При данном плане, в виду наличия открытой задачи, первый потребитель недополучает весь объем (38 ед.) груза.1.7.Текст практической задачи №4Фирма может влиять дополнительным финансированием на скорость строительства своего торгового павильона. Очередность выполнения работ, их нормальная и срочная продолжительность их выполнения, а также стоимость приведены в следующей таблице:Имя работыABCDEОпирается на работуEGC,Q,BVНормальный срок (дни)121227612Ускоренный срок (дни)44824Норм. стоим. (тыс. руб.)5,26,479,220,46Срочная стоим. (тыс. руб.)15,619,2267,361,218Имя работыFGHQVОпирается на работуEVGVНормальный срок (дни)12618226Ускоренный срок (дни)42662Норм. стоим. (тыс. руб.)7,22,28,470,224Срочная стоим. (тыс. руб.)21,66,625,2257,472С учетом технологической последовательности работ построить сетевой график выполнения этих работ.Рассчитать временные характеристики сетевого графика при нормальном режиме выполнения работ. Найти критический путь, указать все возможные критические пути, определить стоимость всего комплекса работ.Указать стратегию минимального удорожания комплекса работ при сокращении сроков строительства на 2 дня. В какую итоговую сумму обойдется ускоренная стройка павильона?1.8.Решение практической задачи №4Упорядоченный сетевой график строительства торговой павильона изображен на рис. 6, где рядом с буквой, обозначающей работу, в скобках проставлено число, равное нормальному сроку ее выполнения.17659351308100Q(22)00Q(22)126492013665200043815001404620F(12)00F(12)4499610226060H(18)00H(18)263271044132500122682050165000349631014046200041376601377950002133601421765002842260920750B(12)00B(12)2919095117729000329311010160004004324231093027500151828511868150053517801177290004417060117729000537210118681500256713E(12)V(6)C(27)G(6)A(12)D(6)256713E(12)V(6)C(27)G(6)A(12)D(6)Рис. 6. Сетевой график.Обозначим Ткр – критическое время, т.е. наибольшее время выполнения всего комплекса работ; Трi – раннее время наступления i-го события.Рассчитаем Трi для всех событий сетевого графика, т.е. для i= 1,2,…,7. Время наступления 1-го события сетевого графика будем считать равным нулю, т.е. Тр1 = 0. Далее последовательно находим Тр2,…, Тр7дн; дн;дн; дн;дн; Мы получили 1 критический путь:.Критический срок Ткр = 34дн.Находим стоимость критического пути:Сокращение сроков строительства торгового павильонаПо условию задачи необходимо сократить период строительства на 2 дня, т.е. до 32 дней и добиться этого минимальными затратами. Сокращение этого строительства может быть выполнено только за счет работ, принадлежащих критическому пути. Сокращая время выполнения тех работ, которые требуют наименьших дополнительных затрат, можно добиться минимального удорожания.Предположим, что затраты на ускорение каждой работы пропорциональны периоду ускорения. Дополнительные затраты на один день ускорения рассчитываем по формуле:.Рассчитанные затраты на ускорение приведены в таблице:Имя работыVQDНормальный срок (дни)6226Ускоренный срок (дни)262Срок ускорения (дни)4164Норм. стоим. (тыс. руб.)2470,220,4Срочная стоим. (тыс. руб.)72257,461,2Плата за ускорение 48187,240,8Удельные затраты на ускорение 1211,710,2Очевидно, что наилучший способ ускорения - сокращение сроков выполнения работы D, так как она имеет наименьшее удорожание.Сократим критическое время на 1 день за счет работы D и проверим наличие новых критических путей (рис. 7).17659351308100Q(22)00Q(22)126492013665200043815001404620F(12)00F(12)4499610226060H(18)00H(18)263271044132500122682050165000349631014046200041376601377950002133601421765002842260920750B(12)00B(12)2919095117729000329311010160004004324231093027500151828511868150053517801177290004417060117729000537210118681500256713E(12)V(6)C(27)G(6)A(12)D(5)256713E(12)V(6)C(27)G(6)A(12)D(5)Рис. 7. Сетевой график после ускорения на 1 день.Тр1 = 0; дн; дн;дн; дн;дн; Итак, критический путь не изменился, новых путей не появилось.Нам необходимо сократить критический путь еще на 1 день.Рассуждая аналогично, сократим критическое время еще на 1 день за счет работы D и проверим наличие новых критических путей (рис. 8).17659351308100Q(22)00Q(22)126492013665200043815001404620F(12)00F(12)4499610226060H(18)00H(18)263271044132500122682050165000349631014046200041376601377950002133601421765002842260920750B(12)00B(12)2919095117729000329311010160004004324231093027500151828511868150053517801177290004417060117729000537210118681500256713E(12)V(6)C(27)G(6)A(12)D(4)256713E(12)V(6)C(27)G(6)A(12)D(4)Рис. 8. Сетевой график после ускорения на 2 дня.Тр1 = 0; дн; дн;дн; дн;дн; Видим, что критический путь не изменился, новых путей не появилось.Итак, для ускорения строительства на 2 дня с минимальными затратами нужно ускорить на 2 дня работу D. При этом минимальная доплата составит: 10,2+10,2=20,4 тыс. руб.Стоимость работ будет равной 114,6+20,4=135 тыс. руб. Задание 1.Информация по фирме о нормах затрат ресурсов на единицу выпускаемой продукции, лимитах на эти ресурсы и ценах реализации готовой продукции представлена в таблице.Наименование ресурсаНормы затрат наОбъем ресурсаПродукт АПродукт ВСырье (кг)31248Оборудование (ст./час)12138Труд (чел./час)61245Цена единицы (руб.)487138Задание 2.Учитывая данные задания 1, исследовать динамику предельной эффективности сырья при изменении его объема от нуля до бесконечности при сохранении других ресурсов в прежних объемах.Требуется:1. Рассмотреть модель расчета оптимальной производственной программы как задачу линейного программирования с параметром, выражающим объем сырья.2. Используя графический метод решения прямой задачи при увеличении параметра от нуля до бесконечности и условия "дополняющей нежесткости", вычислить убывающие значения предельной эффективности и определить диапазоны их устойчивости.3. Записать выявленную функцию предельной эффективности сырья в табличной форме и построить ее график.Решение.При решении задачи 1 была получена математическая модель:Для нее составили двойственную задачу:Относительно рассматриваемых в данной работе задач (1.1) и (1.2) соответствующие условия «дополняющей нежесткости» первой и второй группы выглядят следующим образом.При сохранении лимитов по другим ресурсам исследуем зависимость максимума выручки от изменения лимита сырья в диапазоне от нуля до бесконечности. Это значит, что при графическом анализе изменения области допустимых решений на рис. 1, прямая, связанная с оборудованием, и прямая, связанная с трудом, останутся на тех же местах, что и в задаче 1, в то время как прямая по сырью будет менять свое положение. Пунктирные прямые на рис. 1, рассмотренные в порядке (1), (2), (3), (4) отражают динамику роста лимитов потребления сырья для данного предприятия. Пунктирная прямая (4) соответствует первоначально заданному лимиту по сырью, равному 248 кг. Она соответствует избыточному объему сырья по отношению ко всем программам, допустимым по лимитам для оборудования и труда.3524885136271000363474023647400020821652190115002314575143764000352488513627100039782752440940003634740236474000Рис. 1. Графический анализ изменения предельной эффективностидополнительно привлекаемой единицы сырьяПри лимите сырья, представленном пунктирной прямой (1), область допустимых решений задачи будет представлена треугольником, образованным этой прямой и осями координат. Для определения оптимального решения на таком треугольнике можно либо использовать градиент целевой функции, либо сравнить значения целевой функции в угловых точках треугольника. Такими точками можно взять, например, точки (0;30) и (10;0), расход сырья для которых одинаков и равен 30 кг. Выручка, соответствующая этим точкам: и . Отсюда видно, что оптимальным решением в данной ситуации будет точка , . Решение двойственной задачи для данной ситуации найдем по составленным выше условиям «дополняющей нежесткости».Из группы условий (1.3), так как и , следует, что оборудование и труд не лимитируют оптимальную программу, а значит , . Из группы условий (1.4) следует, что, если первый продукт выпускается по оптимальной производственной программе, то есть , то должно выполняться равенство Из последнего уравнения, с учетом , , получим .При повышении лимита потребления сырья пунктирная прямая будет двигаться по направлению от начала координат, а треугольник, отражающий ОДР, будет увеличиваться.