Разработка занятия на тему: «Двойственность в линейном программировании» по дисциплине "Моделирование производственных и экономических процессов", 3 курс специальность "ВТ и ПО"

ГККП «Политехнический колледж» Разработка занятия по дисциплине «Моделирование производственных и экономических процессов» Тема: «Двойственность в линейном программировании» Тема: Лабораторная работа №3 «Двойственность в линейном программировании» Цель: актуализация знаний о двойственности в линейном программировании, и принципе его решения с помощью программы Microsoft Excel, умение применять полученные знания на практике, при выполнении заданий Задачи: 1.   Закрепить   знания   обучающихся   по   составлению   и   решению   прямой   и   двойственной задачи линейного программирования с использованием симплекс­метода»;  2. Развивать наблюдательность, самостоятельность в решении учебных проблем, умения пользоваться   приемами   сравнения,   обобщения,   делать   выводы,   навыки   работы   с компьютерными программами, Развивать межпредметные связи 3.   Воспитательная:   Воспитывать   у   обучающихся   последовательность   и   поэтапность действия, логику мышлений, деловой и творческий подход к работе, требовательность и самокритичность к себе, компьютерную грамотность, бережное отношение к оборудованию Тип урока: комбинированный Вид урока: закрепление и контроль знаний, умений, навыков Средства обучения: программа Microsoft Excel, интерактивная доска Технология   обучения:   интегрированный   урок   с   применением   интерактивных   методов обучения. Планируемые результаты: В   процессе   освоения   темы   предлагается   формирование   следующих   компетентностей   у обучающихся:        получение и обработка информации; составление прямой и двойственной задач линейного программирования; использование различных критериев принятия решений (работа с итерациями); принимать на себя ответственность за получаемое решение; закреплять и применять межпредметные знания; пользоваться приемами сравнения, обобщения, делать выводы; самостоятельно пополнять и систематизировать свои знания. Ход занятия 1. Орг. момент   – приветствие, проверка присутствующих, указание темы, целей и задач занятия, ознакомить с ходом проведения занятия (3 минуты) 2.   Опрос   ранее   пройденного   материала   (фронтальный   опрос   с   использованием интерактивной доски) (10 минут) Вопросы: 1. Дайте определение линейному программированию? Линейное программирование (планирование) – метод отыскания максимума или минимума линейной функции при наличии ограничений в виде линейных неравенств или уравнений. 2. Что такое целевая функция? Максимизируемая   (минимизируемая)   функции   представляют   собой   принятый   критерий эффективности решения задачи, соответствующей поставленной цели.  3. Перечислите правила построения двойственных задач 1. Если в исходной задаче целевая функция исследуется на min, то в двойственной задаче она будет  исследоваться на max  и наоборот.  2. Если в исходной задаче n переменных и m уравнений, то в двойственной задаче будет m переменных и n уравнений. 3.   Коэффициенты   целевой   функции   исходной   задачи   становятся   правыми   частями ограничений двойственной задачи, а правые части системы ограничений исходной задачи становятся коэффициентами целевой функции исходной задачи.  4.   Матрица   ограничений   двойственной   задачи   получается     из   матрицы   ограничений исходной задачи транспонированием. 5.   Если   в   исходной   задаче   xk≥0,   то   в   двойственной   задаче   k­ое   ограничение   будет неравенством,   если   же   в   исходной   задаче   xk  не   имело   ограничений   на   знак,   то   k­ое ограничение в двойственной задаче будет равенством. 6. Если в исходной задаче l­ое ограничение ­ неравенство, то в двойственной задаче у1≥0; если же в исходной задаче  l­ое ограничение ­ равенство, то в двойственной задаче нет ограничений на знак yi 4. Дана прямая экономико­математическая модель линейной задачи. Составить к ней двойственную задачу.  x 2 3 x x 2 4 1  x 54412 x  3223 10 x x   7432514 x x x  03,2,1 xxx     3 x 3 min             5   max Ответ:   7 y y y 10 5 2 3 1   12 334 y y     23523 y y      22 y    14 y   3    533 y 5. В чем заключается экономический смысл двойственных задач об использовании   ресурсов   2,* * yy 1 * my     * X ,...., * Y     * 2,* xx 1 ,..., * nx     План производства  и набор цен ресурсов  оказываются  оптимальными  тогда   и   только   тогда,   когда   прибыль   (выручка)   от продукции,   найденная   при   «внешних»   (известных   заранее)   ценах   оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при “внешних”(известных заранее) ценах у1, у2, …, уm Для всех других планов X и Y обеих задач прибыль (выручка) от продукции всегда меньше (или равна) затратам на ресурсы. 6. Что такое исследование на устойчивость? Исследование на устойчивость – исследование диапазона изменения правых частей системы ограничений, при котором найденное оптимальное решение не изменяется.  7. Что такое исследование на чувствительность? При   исследовании   на   чувствительность   исследуется   зависимость   решения   ЗЛП   от небольших изменений коэффициентов в условии задачи. При этом предыдущее решение может стать либо недопустимым, либо неоптимальным.  • К недопустимости пред. решения могут привести изменения запасов ресурсов и/или добавление новых ограничений. • К   неоптимальности   пред.   решения   могут   привести   изменение   целевой   функции и/или изменение технологических коэффициентов и/или  включение в модель нового вида производственной деятельности. 8. Объясните технологию расчета задач линейного программирования с помощью симплекс метода 1. Поставленная описательная задача переводится в математическую форму (целевая функция и ограничения). 2. Полученное математическое описание приводят к канонической форме. 3. Каноническую форму приводят к матричному виду. 4. Ищут первое допустимое решение. Для этого  матрица  должна быть правильной. Матрица  в   ЗЛП   называется   правильной,   если   она   содержит   минимум   m   правильных (базисных)   столбцов,   где   m   –   число   строк   в   матрице.   Столбец   в   канонической   ЗЛП называется   правильным   (базисным),   если   все   его   элементы   равны   нулю,   кроме единственного равного единице. 5. Если матрица не является правильной, то ее нужно сделать таковой с помощью искусственного базиса. Для этого в  матрицу нужно дописать столько базисных столбцов, чтобы их общее количество вместе с уже имеющимися базисными столбцами составляло m. После этого переходят к пункту 6. Если искусственный столбец выходит из базиса, то его удаляют   из  матрицы.   Если   удалены   все   искусственные   столбцы,   то   получено   первое допустимое   решение.   Если   искусственные   элементы   не   удается   вывести   из   базиса,   то система не имеет решений. 6. Строят последовательность матриц. Нужно определить ведущий столбец, ведущую строку   и   ведущий   элемент.   Элемент,   соответствующий   ведущей   строке,   удаляется   из базиса, а на его место ставят элемент, соответствующий ведущему столбцу. Составляют уравнение пересчета матрицы, выполняют пересчет, а затем проверяют его результаты на оптимальность. Если решение не оптимально, то заново ограничивают ведущий элемент, ведущую строку и ведущий столбец. 3.   Выполнение   задания   лабораторной   работы   –   контроль   и   оказание   помощи   (35 минут) 3.1 Решение задач Лабораторная работа №3 Цель: составление и расчет прямой и двойственной задачи линейного программирования Содержание работы 1. Ознакомиться   условием   заданием   для   решения   прямой   и   двойственной   задачей линейного программирования. 2. Воспроизвести задачу в электронном виде, используя программу Microsoft Excel. 3. Работа с тестирующей программой MyTest. 4. Составить отчет по работе. Задание. Для изготовления обуви четырех моделей на фабрике используются два сорта кожи. Ресурсы рабочей силы и материала, затраты труда и материала для изготовления каждой   пары   обуви,   а   также   прибыль   от   реализации   единицы   продукции   приведены   в таблице. Составить план выпуска обуви по ассортименту, максимизирующий прибыль. Запас ресурсаЗатраты ресурсов на одну пару обуви по моделям Ресурсы Рабочее время, чел.­ч Кожа 1­го сорта Кожа 2­го сорта Прибыль, ден. ед. 1000 500 1200 № 1 1 2 0 2 № 2 2 1 1 40 № 3 2 0 4 10 № 4 1 0 1 15 Решение задачи: Х1 – количество обуви модели №1, выпускаемое фабрикой; Х2 – количество обуви модели №2, выпускаемое фабрикой; Х3 – количество обуви модели №3, выпускаемое фабрикой; Х4 – количество обуви модели №4, выпускаемое фабрикой. F = 2*X1 + 40*X2 + 10*X3 + 15*X4 => max ­целевая функция Ограничения на ресурсы: Х1 + 2*Х2 + 2*Х3 + Х4≤ 1000 2*Х1 + Х2 ≤ 500 Х2 + 4*Х3 + Х4 ≤ 1200 Х1, Х2 ≥ 0 Таблица 1.1. Изделия x2 x1 0 500   объем x3 0 x4 0 ЦФ F(X) 20000 Оптимальный производства Ресурс Наличие Расход   ресурсов   на Общий расход Остато к Статус ресурса Теневая цена Рабочее   время, чел. Кожа 1 Кожа 2 1000 500 1200 производство изделий x1 0 x2 1000 x3 0 0 0 500 500 0 0 x4 0 0 0 1000 500 500 0 0 700 Дефицит15 Дефицит0 Излишек 0 Итоговая симплекс­таблица: 1. Основные вопросы анализа оптимального решения ЗЛП на чувствительность линейное программирование задача Основные задачи анализа на чувствительность: 1. Анализ изменений запасов ресурсов позволяет ответить на два вопроса: а) На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции? б)   На   сколько   можно   снизить   запас   некоторого   ресурса   при   сохранении   полученного оптимального значения целевой функции? 2.   Определение   наиболее   выгодного   ресурса,   т.е.   ресурса,которому   следует   отдавать предпочтение при инвестировании дополнительных средств. 3. Определение пределов изменения коэффициентов целевой функции делает возможным исследование следующих вопросов: а) Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения? б)   На   сколько   следует   изменить   тот   или   иной   коэффициент   целевой   функции,   чтобы сделать   некоторый   недефицитный   ресурс   дефицитным,   и,наоборот,   дефицитный   ресурс сделать недефицитным? 2. Анализ оптимального решения ЗЛП на чувствительность с помощью итоговой симплекс­ таблицы ­ статус ресурсов: Ресурс относят к разряду дефицитных, если он израсходован полностью. Недефицитный ресурс, наоборот, имеется в избытке. ­ теневая цена: Для определения наиболее выгодного ресурса вводится характеристика ценности каждой дополнительной единицы дефицитного ресурса Решение   двойственной   задачи   yi  определяет   теневую   цену   i­го   ресурса.   Теневая   цена ресурса   показывает,  на  сколько  увеличится  значение   целевой  функции  при   увеличении запаса этого ресурса на единицу. ­ изменение запасов ресурсов и цены на продукцию: Объем   дефицитного   ресурса   не   следует   увеличивать   сверх   того   предела,   когда соответствующее ему ограничение становится избыточным. Объем недефицитного ресурса можно уменьшить на величину избытка. ­ целесообразность выпуска (приобретения) нового вида продукции Теневая   цена   предоставляет   возможность   оценить   целесообразность   введения   в оптимальный план продукцию нового вида. Если выполняется условие то введение в план j­ го вида продукции выгодно. Содержание отчета. 1. Сохранить решение задачи в своей папке. 2. Объясните технологию записи критерия оптимальности. 3. Указать формулы, по которым производится расчет. 4. Анализ изменений запасов ресурсов. 5. Анализ   оптимального   решения   ЗЛП   на   чувствительность   с   помощью   итоговой симплекс­таблицы Задание 3.2. Работа с тестирующей программой MyTest (25 мин) Вопросы. 1. Исследование операций – это: а)   математическая   дисциплина,   особенностью   которого   является   геометрический подход к изучению объектов.  б) математическая дисциплина, занимающаяся построением, анализом и применением математических моделей принятия оптимальных решений. в) математическая дисциплина, занимающаяся применением математических методов для исследования бухгалтерских операций. 2. Оптимальным решением задачи исследования операций называется: а)  решение, доставляющее целевой функции искомое экстремальное значение б)  решение, удовлетворяющее хотя бы одному ограничению в)  решение, удовлетворяющее системе ограничений  г)  решение,   удовлетворяющее   системе   ограничений   и   доставляющее   целевой         функции искомое экстремальное значение 3. Вектор  x  (1,0, 1)   является допустимым решением задачи:  а)   в)      z  5 x 1  12 x 1  x 1 2 x x 2 x 2  1  10  min б)      z    9 2 5 3 x x 3 x 3 2  3 x x 1  x x 3 1  x 1 2 x 3  2 x  x 2 3  5 x 2  5  18  3 min    z  2 x x 1  x x 1  x 1 2 3 x   6 2  3  x x 3 x 3  5 3 2  г)   min 2   10 x x 1   13 x x  1 2  z x x 1 2  12   0   x 3 2 x 3 5 x 3 min 4. Симплекс­таблица содержит оптимальное решение, если она: а)  допустима либо по строкам, либо по столбцам б)  допустима по столбцам, но недопустима по строкам в)  допустима по строкам, но недопустима по столбцам г)  допустима по строкам и по столбцам 5. Для задачи       z 2 2   5 20 x x 1  x 4 x 1  xx 0 , 1 2  5 x 4 x 1  2 2  точка (0;3) является: max а) планом; б) оптимальным планом; в) точкой вне области допустимых решений задачи. 6. Какая из следующих задач не является задачей линейного программирования: а)     z x 1  5 x 2  x 0 1  x 3 1 x 2 б)     z  min 2  0 x 1 x 1 5 x 1 x 2  0 x  2 min в)     z 2  5 x x 1  xx 0 , 1  3 x x 1 2 2 г)     z max  2 4 x x 1 2  xx , 0 1  x x 1 2 2 max 7. Дана задача линейного программирования: Цех выпускает два  вида  продукции, используя два вида полуфабрикатов.  Продукция используется   при   комплектовании   изделий,   при   этом   на   каждую   единицу   продукции первого вида требуется не более двух единиц продукции второго вида. Нормы расхода полуфабрикатов   каждого   вида   на   единицу   выпускаемой   продукции,   общие   объемы полуфабрикатов и прибыль от единицы каждой продукции предоставлены в таблице. Полуфабрикаты Объем полуфабриката Нормы затрат на единицу продукции П1 1 6 10 1 2 Прибыль Определить план производства, доставляющий максимум прибыли. Математическая модель задачи примет вид: а)  П2 2 2 35 800 2400 x 1 x 1 2        z x 1 x 1 6 б)  в)         z        z 800 2400 2 x x  6  2 2 x 1 , xx 2 1  x 1   2  x 2  0 x 35  10  max 2 800 2400 2 x x  2  2 x 2 1 , xx 1 2  x 1   2  x 2  0 x 35  10  min 2 x 1 x 1 6 800 2400 2  2 x x  2  2 2 x 1 , xx 1 2  x 1   x 2  0 35 x  10  max 2 x 1 x 1 2 г)         z 800 2400 2 x x  6  2 x 2 1 , xx 1 2  x 1   2  x 2  0 x 35  10  min 2 8. Если прямая задача является задачей на максимум и имеет ограничения со знаком «≤», то двойственная задача будет являться: а) задачей на минимум и иметь ограничения со знаком «≤»; б) задачей на максимум и иметь ограничения со знаком «≥»; в) задачей на минимум и иметь ограничения со знаком «≥»; г) задачей на максимум и иметь ограничения со знаком «≤». 9. Двойственной к задаче линейного программирования 9 5 4 2 6  x 5 x 1 2    x x 1 2  x 3 x 2 1  , , x x x 3 1   2 x 2 2 x 1 z    x 3 x 3 x 3    0   7 x 3 max является задача:  а)          z 3  x 2 6 x x  5 x 1   x 1  3 x 1 2 , xxx , 1  2 x x 1  9 2 x 3  x 5 2  x 4 3  0 3  7 x 3 2 2  в)         z 2 3    5 3 2 y y y 1   y y y 6 1 1 2    y 7 y 2 1 2 , yy , y 1 2  9 y 5 y 1 3 y 3  0  4 y 3 2 3  б)         z min max  3    3 9 y y 5 y 1 2   6 y 5 y y 3 2 1   y 4 y y 2 3 2 1  yy , 0 y , 3 1   7 y y 2 y 1 3 2 2  max г)         z 2 3 y    5 3 2 y y 1   y y 6 1 y 1 2    y 7 y 2 1 2 , yy , y 1 2  9 y 5 y 1 3 y 3  0  4 y 3 2 3  min 9. Если одна из взаимно двойственных задач имеет оптимальное решение, то другая задача: а) имеет решение, причем линейная функция этой задачи не ограничена; б) имеет решение, причем оптимальные значения линейных функций задач равны; в) не имеет решения, так как условия задачи противоречивы. г) все ответы верны       10. Укажите неверное утверждение: 1) если обе сопряженные задачи имеют хотя бы по одному   допустимому   решению,   то   они   имеют   и   оптимальное   решение;   2)   если   в сопряженных   задачах   имеются   допустимые   решения,   при   которых   целевые   функции совпадают, то решение оптимальное; 3) если прямая задача на максимум, то ее допустимое решение не больше допустимого решения сопряженной. а) 1 б) 2 в) 3 г) все верные. 4. Подведение итогов занятия (5 минут). Выставление полученных оценок за урок в журнал. 5. Домашнее задание (2 минуты)_ В.Яворский, А.Амиров «ЭИ и ИС» стр180­190.  Решить задачу  Для производства четырех видов изделий А1, А2, А3 и А4 завод должен использовать три вида сырья I, II и III. Запасы сырья на планируемый период составляют, соответственно, 1000, 600 и 150 единиц.  Технологические коэффициенты (расход каждого вида сырья на производство единицы каждого изделия) и прибыль от реализации единицы каждого изделия приведены в таблице. Таблица 1 ­ Исходные данные задачи о четырех видах изделий Технологические коэффициенты Запасы сырья Виды сырья I II III Прибыль от реализации А1 5 4 1 6 А2 1 2 0 2 А3 0 2 2 2,5 А4 2 1 1 4 1000 600 150 Требуется, зная решение данной задачи, решить задачу, двойственную ей.