Указания методические по курсовой работе для студентов специальности 22. 02 Автоматизированные системы МИНИСТЕРСТВО ОБРАЗОВАНИЯ PОССИЙСКОЙ ФЕДЕPАЦИИ ИPКУТСКИЙ ГОСУДАPСТВЕHHЫЙ ТЕХHИЧЕСКИЙ УHИВЕPСИТЕТ Факультет кибернетики МАТЕМАТИЧЕСКИЕ МЕТОДЫ СИСТЕМНОГО АНАЛИЗА И ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ Методические указания по курсовой работе для студентов специальности 22.02 "Автоматизированные системы обработки информации и управления " Иркутск, 2001г. Куцый Н.Н. Математические методы системного анализа и теория принятия решений: Пособие по курсовой работе. – Иркутск, изд-во Иркутск. гос. технич. ун-та, 2001. – 39с. Определены цель и задачи, тематика, содержание курсовой работы по учебной дисциплине "Математические методы системного анализа и теория принятия решений". Пособие предназначено для студентов специальностей 220100 – "Вычислительные машины, системы, сети и комплексы", 220200 – "Автоматизированные системы обработки информации и управления", 071900 – "Информационные системы в наукоемких технологиях". Библиогр. 21 назв. Рецензент: профессор, д.т.н. Массель Л. В. Подготовила к печати: Брянская А.Г. План 2001. 2,4 печ. л., 2,5 уч.-изд. л. Тираж 100 экз. Зак. 366 . ЛР № 020263 от 30.12.96 Иркутский государственный технический университет 664074, Иркутск, ул. Лермонтова, 83 1.ЦЕЛЬ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ имеет целью закрепить и расширить знания, полученные студентами по дисциплине "Математические методы системного анализа и теория принятия решений", приобретение навыков самостоятельной работы при решении конкретных задач, выдвигаемых практикой. В результате выполнения курсовой работы студент должен: - освоить принципы формализации на примере реальной задачи организационного управления; - показать знакомство с методами решения, принятыми в математическом программировании, в рамках которого решается описываемая задача; - усовершенствовать навыки в переходе от метода решения формализованной задачи к конкретному алгоритму, на основе которого будет составлена программа для компьютера; продемонстрировать навыки программиста, т.е. необходимо: составить программу с последующей её отладкой; проверить полученные результаты на достоверность; оформить программу для передачи другим пользователям; - уметь анализировать полученные результаты с выдачей рекомендаций организации, для которой решается данная задача; - показать способность работать с литературой. 2.ТЕМАТИКА И ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ может разрабатываться на базе тем, освещенных в учебных занятиях по дисциплине "Математические методы системного анализа и теория принятия решений" для специальности "Авто­мати­зиро­ванные системы обработки информации и управления". Однако с учетом специфики дисциплины "Математические методы системного анализа и теория принятия решений", заключающейся в её многообразии разделов, может быть основана на материале, который должен быть освоен самим студентом. В качестве задания на курсовую работу может выступать содержательно сформулированная задача, имеющая некоторый аналог в практике. При этом одна и та же задача может быть поручена нескольким студентам, но каждому из них задается индивидуальный метод решения поставленной задачи. При выдаче задания на курсовую работу руководителем указывается тема работы, её содержание, сведения о рекомендуемой литературе, исходные данные для работы, метод решения задачи. 3. СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ должна состоять из пояснительной записки и программы, оформленной в виде продукта, предназначенного для передачи пользователю (заказчику). Пояснительная записка должна содержать следующие разделы: - постановка задачи; - обоснование разработанной математической модели; - краткие сведения о методе решения поставленной задачи; - алгоритм решения задачи, на основании которого составлена программа; - фрагмент листинга программы, относящийся к реализации алгоритма решения задачи; - проверка достоверности полученных результатов; - руководство пользователя; - результаты решения задачи курсовой работы на ПЭВМ по исходным данным индивидуального варианта; - список использованной литературы. ВАРИАНТЫ ТЕМ КУРСОВОЙ РАБОТЫ ТЕМА 1. ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СУДОВ ПО РЕГУЛЯРНЫМ ЛИНИЯМ Имеется n различных типов судов, которые могут осуществлять перевозки народнохозяйственных грузов по регулярным линиям. Суда различных типов при эксплуатации на той или иной линии имеют различные характеристики. В частности, различные суда имеют различное число заходов в промежуточные порты для пополнения запасов топлива и пресной воды, на некоторых линиях используется не полностью коммерческая грузоподъемность судов, а суда некоторых типов вообще не могут быть использованы на отдельных линиях и т.п. Все эти причины приводят к тому, что эксплуатационные расходы, приходящиеся на каждый тип судна, используемый на линии, оказываются разными. Исходя из данных о себестоимости грузокилометра и коммерческой загрузки каждого типа судна на каждой линии устанавливается: а) величина месячный объем перевозок одним судном j -го типа i -ой регулярной линии; б) величина месячный эксплуатационный расход средств на одно судно j -го типа, используемое на i -ой линии. Предполагается также известным требуемый минимальный объем перевозок по каждой линии, а также число судов j -го типа, при этом где N - общее число судов, которое необходимо распределить по m линиям. Требуется составить такой план распределения парка N судов по регулярным линиям, который обеспечивает минимум суммарных эксплуатационных расходов при выполнении заданного объема перевозок. Все условия данной задачи сведены в таблицу 1. Таблица 1 № типа судна Þ № линии ß 1 · · · j · · · n Минималь­­ный объем пе­ревозок 1 · · · · · · · · · · · · · · · · · · · · · · · · · · · i · · · · · · · · · · · · · · · · · · · · · · · · · · · m · · · · · · Число судов · · · · · · Конкретные числовые значения представлены в таблице 2, при этом необходимо отметить следующее. 1.В верхних отделениях клеток таблицы указаны числа в тыс. тонн, а в нижних в тыс. рублей, объем перевозок в тыс. тоннах. 2.Отсутствие чисел и в i -ой строке и в j- ом столбце означает невозможность использования судна j -го типа на i -ой регулярной линии. Таблица 2 № типа судна Þ № линии ß 1 2 3 4 Минималь­ный объем перевозок 1 2 3 4 Число судов 55 95 30 45 Вариант 1.1. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод искусственных переменных [9]. Вариант 1.2. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод Данцига [9]. Вариант 1.3. Решить поставленную задачу симплекс-методом, основанном на модифицированных жордановых исключениях [11]. Вариант 1.4. Решить поставленную задачу двойственным симплекс-методом [9]. Вариант 1.5. Решить поставленную задачу следующим образом. Вначале записать прямую задачу линейного программирования; затем, осуществив переход к двойственной задаче линейного программирования, решить ее методом симплекс-таблиц, основанном на методе полного исключения Гаусса. От полученного решения перейти к решению прямой задачи [9]. Вариант 1.6. Решить поставленную задачу, применяя метод Гомори [9]. ТЕМА 2. ЗАДАЧА СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО ГРАФИКА РЕМОНТА ИНСТРУМЕНТА Пусть для выполнения некоторой производственной программы, рассчитанной на n последовательных дней, требуется к началу j -го дня единиц специального инструмента, который к концу дня весь изнашивается. Поэтому часть (или весь) этого инструмента в конце j -го дня сдается в обычный ремонт, часть (или весь) в срочный ремонт, а часть (или весь) изношенного инструмента может не сдаваться в ремонт, оставаясь, например, на складе использованного инструмента. Обычный ремонт инструмента длится p дней и стоит b рублей за единицу инструмента, а срочный ремонт инструмента длится дней и стоит рублей за единицу инструмента. Новый инструмент стоит рублей. Требуется так составить график ремонта и покупки инструмента, чтобы при минимальных издержках обеспечить предприятие инструментом в течение n последовательных дней. Конкретные числовые условия задачи сведены в таблицу. n сутки кол-во еди­ниц p сутки b рублей q сутки с рублей a рублей 7 40 (j= 1(1)4); 0 j =5; 20 (j= 6,7) 3 2 2 4 6 Вариант 2.1. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод Данцига [9]. Вариант 2.2. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применив для нахождения начального допустимого базисного решения метод искусственных переменных [9]. Вариант 2.3. Решить поставленную задачу симплекс-методом, основанном на модифицированных жордановых исключениях [11]. Вариант 2.4. Решить поставленную задачу следующим образом. Свести эту задачу к эквивалентной ей транспортной задаче. Последнюю решить методом потенциалов, использовав для нахождения начального опорного плана метод северо-западного угла [9,11]. Вариант 2.5. Решить поставленную задачу следующим образом. Свести эту задачу к эквивалентной ей транспортной задаче. Последнюю решить методом потенциалов, использовав для нахождения начального опорного плана метод минимального элемента [9,11]. Вариант 2.6. Решить поставленную задачу следующим образом. Свести эту задачу к эквивалентной ей транспортной задаче. Последнюю решить венгерским методом [9,11]. ТЕМА 3. ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЯМ СТОИМОСТИ И ВРЕМЕНИ Имеется m пунктов отправления, в каждом из которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте имеется единиц этого продукта, во втором - единиц, в i -ом - единиц, и, наконец, в m -ом пункте - единиц продукта. Этот продукт следует доставить в n пунктов назначения (потребления), причем в первый пункт назначения следует доставить единиц продукта, во второй - единиц, в j -й - единиц, и, наконец, в n -й пункт - единиц продукта. Каждый пункт отправления соединен с каждым пунктом назначения некоторым маршрутом (число таких маршрутов ), причем известна удельная стоимость перевозки одной единицы продукта из i -го пункта отправления в j -й пункт назначения. Общая стоимость перевозки по любому маршруту пропорциональна количеству перевозимого продукта. Известно также время перевозки продукта из i -го пункта отправления в j -й пункт назначения, причем это время не зависит от количества перевозимого груза. Удельные стоимости и время перевозок приведены в таблице, при этом: 1) на пропускные способности коммуникаций ограничения не накладываются; 2) и - количество условных единиц продукта; 3) в верхних отделениях клеток таблицы помещены удельные стоимости в рублях, а в нижних - время перевозок в часах. B j Þ A i ß B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 a i A 1 180 A 2 140 A 3 50 A 4 150 A 5 80 A 6 80 A 7 70 bj 50 80 10 40 140 110 130 150 Вариант 3.1. Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод северо-западного угла [9]. Вариант 3.2. Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод минимального элемента [9]. Вариант 3.3. Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить венгерским методом [9]. Вариант 3.4. Составить план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок; определить для этого плана стоимость перевозок; произвести, если это возможно, дооптимизацию по критерию стоимости. Поставленную задачу решить, применяя метод, в основе которого лежит построение "разгрузочного" цикла [13]. Вариант 3.5. Составить план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок; определить для этого плана стоимость перевозок; произвести, если это возможно, дооптимизацию по критерию стоимости. Первую часть задачи решить, применяя вариант метода потенциалов, при дополнительных условиях, вводимых последовательно в процесс решения [13]. ТЕМА 4. ЗАДАЧА О НАИЛУЧШЕМ РАСПРЕДЕЛЕНИИ ПРОГРАММЫ МЕЖДУ НЕСКОЛЬКИМИ ПРЕДПРИЯТИЯМИ (ОБ ОПТИМАЛЬНОМ ИСПОЛЬЗОВАНИИ ОБОРУДОВАНИЯ) Имеется s видов изделий, из которых комплектуется окончательная продукция. Каждый вид изделий может быть поставлен на производство на каждом из n типов предприятий (станков), причем имеется предприятий j -го типа каждое из которых может изготовить в месяц изделий k -го вида, и в каждый комплект готовой продукции должно входить изделий k -го вида Каждое предприятие должно по плану выпускать продукцию лишь одного вида. Требуется оптимальным образом распределить производственную программу между всеми предприятиями, т.е. определить число предприятий j -го типа, которое необходимо специализировать на изготовлении изделий k -го вида, чтобы обеспечить максимальный выпуск комплектной продукции. Конкретные числовые условия представлены в таблице, причем значения величин даны в тыс. штук. № типа пред­прия­тия Þ № изделия ß 1 2 3 4 5 Число изделий в комплекте 1 100 400 20 200 600 2 2 15 200 25 50 250 1 3 100 150 200 25 350 3 Число предприятий 5 3 40 9 2 Вариант 4.1. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса. Так как этот метод не обеспечивает целочисленности оптимального решения, то полученный результат необходимо округлить с последующей оценкой величины изменения целевой функции из-за такого округления. Вариант 4.2. Решить поставленную задачу симплекс-методом, основанном на модифицированных жордановых исключениях. Так как этот метод не обеспечивает целочисленности оптимального решения, то полученный результат необходимо округлить с последующей оценкой величины изменения целевой функции из-за такого округления. Вариант 4.3. Решить поставленную задачу, применяя метод Гомори. ТЕМА 5. ИССЛЕДОВАНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО НАЗНАЧЕНИЯ НА АВИАРЕЙСЫ Авиалиния, работающая в течение всей недели, имеет расписание рейсов, приведенное в таблице. Между полетами, экипажи должны иметь отдых не менее 5 часов. Вместе с тем экипаж не должен ждать рейса более чем 24 часа. Задача заключается в следующем. Где должны базироваться экипажи и какие рейсы они должны обслуживать, чтобы суммарное время, которое все экипажи имеют на ожидание обратного рейса, было минимальным. Москва - Санкт-Петербург Санкт-Петербург – Москва № рейса Отправление Прибытие № рейса Отправление Прибытие 1 7 час. 8 час. 101 8 час. 9 час. 15 мин. 2 8 час. 9 час. 102 8 час. 30 мин. 9 час. 45 мин. 3 13 час. 30 мин. 14 час. 30 мин. 103 12 час. 13 час. 15 мин. 4 18 час. 30 мин. 19 час. 30 мин. 104 17 час 30 мин. 18 час. 45 мин. 5 20 час. 21 час. 105 19 час. 20 час. 15 мин. 6 23 час. 30 мин. 0 час. 30 мин. 106 22 час. 23 час. 15 мин. ТЕМА 6. ИССЛЕДОВАНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ ОБЪЕМОВ ВЫПУСКАЕМЫХ ИЗДЕЛИЙ На рис.1 показаны технологические маршруты изготовления трех изделий на предприятии. Исходя из данных, приведенных ниже, сформулируйте и решите задачу выбора объема выпуска каждого изделия. Продажные цены изделий первого, второго и третьего соответственно равны 5,0; 4,5; 3,5 единиц стоимости, исследуйте загрузку оборудования при полученном оптимальном плане и определите расходы сырья. Рис. 1. Изделия СТАНКИ А B C Д 1.Выпуск в час 500 1000 1850 - 2.Выпуск в час 12000 1500 2300 1400 3.Выпуск в час - - 1600 800 Эксплуатационные затраты в час 500 450 800 600 Время простоя % 10 5 5 10 Сырье P O K Расход единиц сырья на изделие 1 1 1,25 2,0 Расход единиц сырья на изделие 2 - 2,0 2,5 Расход единиц сырья на изделие 3 1,5 - 1,75 Стоимость единиц сырья 0,25 0,35 0,3 Вариант 6.1. Исходя из данных, приведенных в таблице, сфор­мулируйте и решите задачу выбора объема выпуска каждого изделия. Исследуйте загрузку обо­рудования при полученном оп­ти­мальном решении и определите расходы сырья. При решении примените вариант симплексного метода, изложенного в [1]. Вариант 6.2. Исходя из данных, приведенных в таблице, сфор­мулируйте и решите задачу выбора объема выпуска каждого изделия. Исследуйте загрузку оборудования при полученном оп­ти­мальном решении и определите расходы сырья. При решении примените метод симплекс-таблиц. ТЕМА 7. ДВУХЭТАПНАЯ ТРАНСПОРТНАЯ ЗАДАЧА В различных отраслях народного хозяйства (территориально-техническое снабжение, торговля) грузы могут доставляться через промежуточные пункты. Допустим, имеются пункты производства , пункты потребления и промежуточные базы Объемы поставок и потребления обоз­на­че­ны через соответственно, через обозначены мощности промежуточных баз. Через обозначены стоимость перевозки едини­цы продукции от поставщиков на базы и с баз к потребителям соответственно. В Ивановском районе имеется два маслодельных завода. Сливочное масло поступает вначале на холодильники, которые расположены в Николаевке, Павловске, Александровке. Из этих холодильников сливочное масло поступает в торговлю в следующие пункты: Гончарово, Гришево, Гмелино, Седаново. Возможности маслодельных заводов, мощности холодильников, запросы потребителей и соответствующие тарифы представлены в таблицах 1 и 2. Таблица 1 Холодильники Þ Маслодельные заводы ß Николаевка Павловск Александровка 1-ый масло­дель­ный завод 20 23 16 2-ый масло­дель­ный завод 15 10 24 Таблица 2 Пункты торговлиÞ Холодильники ß Гончарово Гришево Гмелино Седаново Николаевка 17 22 20 23 Павловск 20 25 24 22 Александ­ровка 16 21 25 11 Вариант 7.1. Данную двухэтапную транспортную задачу свести к классической транспортной задаче, при решении которой использовать метод минимального элемента для нахождения начального опорного плана с последующим применением метода потенциалов. Вариант 7.2. Данную двухэтапную транспортную задачу свести к классической транспортной задаче, при решении которой использовать метод "северо-западного угла" с последующим применением метода потенциалов. Вариант 7.3. Данную двухэтапную транспортную задачу свести к классической транспортной задаче, при решении которой использовать венгерский метод. Вариант 7.4. Данную задачу решить в два этапа, т.е. сначала найти оптимальный план прикрепления поставщиков к холодильникам, а затем решить задачу оптимального прикрепления холодильников к потребителям. ТЕМА 8. ДИНАМИЧЕСКАЯ ЗАДАЧА ВЫБОРА ОБЪЕМА ПАРТИЙ Предприятие должно разработать календарную программу выпуска некоторого вида изделий на плановый период, состоящий из N отрезков. Предполагается, что для каждого из отрезков известен точный прогноз спроса на выпускаемую продукцию; для разных отрезков времени спрос не одинаков. Временем изготовления партий изделий пренебрегаем. Стоимость выпуска партии зависит от ее объема. Предприятию часто бывает выгодно изготавливать в течение некоторого отрезка продукцию в объеме превышающем спрос в пределах этого отрезка, и хранить излишки, используя их для удовлетворения спроса в последующие периоды. Вместе с тем, хранение запасов связано с определенными затратами, в состав которых входят, в частности, расходы по содержанию запасов, арендная плата за складские помещения и т.д. Обозна­чим через затраты по хранению избыточного запаса на i -ом отрезке. Требуется определить такую программу выпуска в каждом из отрезков, при которой минимизируется общая сумма затрат на производство и содержание запасов, при условии полного и своевременного удовлетворения спроса на продукцию в каждом из отрезков. Вариант 8.1. Число отрезков N = 6, где Спрос по периодам равен соответственно Вариант 8.2. Число отрезков N = 8, где Спрос по периодам равен соответственно Выяснить, при каком соотношении между фиксированной стоимостью заказа партии А и удельными затратами на хранение S оптимальная программа изготовления деталей будет совпадать со спросом, т.е. Вариант 8.3. Число отрезков N = 7, где Спрос по периодам равен соответственно Найти оптимальные программы выпуска партий и сравнить их для S = 1,2,4. ТЕМА 9. ЗАДАЧА УПРАВЛЕНИЯ ЗАПАСАМИ ПРИ СЛУЧАЙНОМ СПРОСЕ Пусть для некоторого оборудования целесообразно иметь запасные части (для простоты одного наименования). Известно, что вероятность поломки n штук этих деталей равна стоимость одной детали равна убытки в случае поломки и отсутствия запчастей равны . Требуется определить оптимальное количество запасных деталей , т.е. такое, чтобы суммарные затраты на приобретение и средние затраты из-за нехватки запчастей при поломке были минимальны. Вариант 9.1. Решить поставленную задачу при стоимости одного изделия 200 руб., затраты в случае выхода изделия из строя 500 руб. при максимальном количестве исследуемых деталей равном семи. Вероятности выхода из строя n изделий задана в виде: P (1)=0,35; P (2)=0,22; P (3)=0,16; P (4)=0,1; P (5)=0,08; P (6)=0,06; P (7)=0,03. Исследовать зависимость величины минимума целевой функции от соотношения Вариант 9.2. Решить поставленную задачу при стоимости одного изделия 200 руб., затраты в случае выхода одного изделия из строя 500 руб. При определении вероятности выхода из строя n изделий следует руководствоваться следующими выражениями Исследовать изменение минимума целевой функции от параметра а = 0(1)10. Ответить на вопрос о физическом смысле параметра a в данной задаче. ТЕМА 10. ЗАДАЧА ОБ ОПТИМАЛЬНОМ РАСКРОЕ МАТЕРИАЛОВ (О МИНИМИЗАЦИИ ОТХОДОВ) Пусть некоторый полуфабрикат (например, листы фанеры) поступил на предприятие в виде m различных партий, содержащих соответственно единиц полуфабрикатов одинакового для каждой партии размера. Из поступивших полуфабрикатов требуется изготовить возможно большее число комплектов деталей, в каждый из которых входит деталей первого вида, деталей второго вида, ..., деталей l -го вида. Пусть каждую единицу полуфабриката можно раскроить на детали n различными способами, причем при раскрое единицы i -й партии j -м способом получается деталей s- го вида. Конкретные данные задачи приведены ниже. В обработку поступили три партии досок для изготовления комплектов из четырех деталей, причем первая содержит 50 досок длиной по 6,5 м каждая, вторая содержит 200 досок длиной по 4 м каждая, третья содержит 100 досок длиной по 3 м каждая. Каждый комплект состоит из двух деталей по 2 м каждая и двух деталей длиной в 1,25 м каждая. Как распилить все доски, чтобы получить возможно большое число комплектов? Доска длиной 6,5 м может быть распилена на детали требуемых размеров следующими способами: 1) 3 детали по 2 м ; 2) 2 детали по 2 м и 2 детали по 1,25 м ; 3) 1 деталь в 2 м и 3 детали по 1,25 м ; 4) 5 деталей по 1,25 м. Доска длиной в 4 м может быть распилена на детали следующими способами: 1) 2 детали по 2 м ; 2) 1 деталь в 2 м и 1 деталь в 1,25 м ; 3) 3 детали по 1,25 м . Доска длиной в 3 м может быть распилена на детали следующими способами: 1) 1 деталь в 2 м ; 2) 2 детали по 1,25 м . Вариант 10.1. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод искусственных переменных. Вариант 10.2. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод Данцига. Вариант 10.3. Решить поставленную задачу симплекс-методом, основанном на модифицированных жордановых исключениях. Вариант 10.4. Решить поставленную задачу двойственным симплекс-методом. Вариант 10.5. Решить поставленную задачу следующим образом. Вначале записать прямую задачу линейного программирования; затем осуществив переход к двойственной задаче линейного программирования решить ее методом симплекс-таблиц, основанном на методе полного исключения Гаусса. От полученного решения перейти к решению прямой задачи. Вариант 10.6. Решить поставленную задачу, применяя метод Гомори. ТЕМА 11. УПРАВЛЕНИЕ СИСТЕМОЙ МАРКОВСКОГО ТИПА С ДОХОДАМИ Имеется предприятие, выпускающее галстуки, которое планирует свою работу на 12 месяцев вперед. Предприятие может находиться в одном из двух состояний: а) модель предыдущего месяца удачна; б) модель предыдущего месяца неудачна. Переходы за месяц из одного состояния в другое описываются матрицей вероятностей . С каждым переходом из состояния i в состояние j матрица доходов R. Предположим, что можно целенаправленно изменять элементы матрицы , увеличивая например, вероятность пребывания в удачном состоянии. Для этой цели предприятие применяет одну из следующих трех стратегий: а) k = 1 - не проводить никаких дополнительных исследований; б) k = 2 - провести дополнительные исследования конъюнктуры спроса; в) k = 3 - затратить дополнительные средства на рекламу своей продукции. Вариант 11.1. Применив рекуррентный метод динамического программирования найти оптимальную стратегию управления, обеспечивающую максимальный доход предприятия. Вариант 11.2. Применив метод итераций по стратегиям Ховарда найти оптимальную стратегию управления, обеспечивающую максимальный доход предприятия. Конкретные данные заданы следующим образом. Стратегия k = 1 j Þ i - 1 2 j Þ i - 1 2 P= 1 0,5 0,5 R= 1 7 3 2 0,3 0,7 2 5 1 Стратегия k = 2 Провести дополнительные исследования коньюктуры рынка j Þ i - 1 2 j Þ i - 1 2 P= 1 0,6 0,4 R= 1 3 -5 2 0,7 0,3 2 1 -18 Стратегия k = 3 Затратить дополнительные средства на рекламу своей продукции j Þ i - 1 2 j Þ i - 1 2 P= 1 0,7 0,3 R= 1 2 -8 2 0,8 0,2 2 0 -20 ТЕМА 12. ЗАДАЧА О ДОБЫЧЕ ПЕСКА В КАРЬЕРАХ И ЕГО ДОСТАВКЕ Строительный песок добывается в трех карьерах и доставляется на четыре строительных площадки. Данные о производительности карьеров за сутки ( в тоннах), потребностях в песке строительных площадках ( в тоннах), затратах на добычу песка ( руб/тонна) и транспортных расходах приведены в следующей таблице ai ¯ bj ® 40 35 30 45 di 46 4 3 2 5 2 34 1 1 6 4 3 40 3 5 9 4 1 Недостающее количество песка – 30 т за сутки можно обеспечить следующими тремя путями: 1)увеличение производительности 1-го карьера, что повлечет за собой дополнительные затраты на добычу 1 т в 3 руб. 2)увеличение производительности 2-го карьера в дополнительными затратами в 2 руб. на добычу 1 т. 3)эксплуатация нового карьера с затратами на добычу 1 т – 5 руб., и на транспортировку к указанным строительным площадкам - Определить план закрепления строительных площадок за карьерами и вариант расширения поставок песка, при которых затраты на доставку песка и на расширение его поставок будут минимальны. Вариант 12.1. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод минимального элемента. Вариант 12.2. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод "северо-западного угла". Вариант 12.3. Поставленную задачу решить венгерским методом. Тема 13. Задача о пополнении запасов Акционерное общество "Меркурий" имеет сорок автоцистерн для перевозки нефтепродуктов. Каждая машина обута в десять шин, запас которых хотя, поэтому желательно иметь в своем распоряжении не слишком больший запас; но при отсутствии шин в запасе акционерное общество терпит убытки из-за невозможности выполнить отдельные заказы на перевозки. За шинами следит осмотрщик, который по виду шин выносит заключение о ее состоянии. Он подметил, что шина, изношенная на 20% прошла 6000 км; на 40% - 12 000 км; на 60 % - 18 000 км; на 80 % - 24 000 км и на 100 % - 30 000 км. Но, как бы там ни было, не все шины выдерживают 30 000 км. Исследование, которое проводилось в течение многих лет, показало, что согласно статистике, на 100 шин, введенных в эксплуатацию, 5 выходят из строя после 6000 км, 10 – между 6000 и 12 000 км; 25 – между 12 000 и 18 000 км; 30 – между 18 000 и 24 000 км; 30 между 24 000 и 30 00 км. Таким образом, можно определить кривую продолжительности жизни шин, которая давала бы число шин, находящихся еще в эксплуатации после пробега 6000, 12 000 и т.д. километров. Дирекция планирует ездки машин на неделю; важно заказывать шины в количестве, достаточном, чтобы произвести вследствие износа или случайного повреждения. Допустим, что машина пробегает за неделю 2000 км; что за неделю дает пробег в 80 000 км для всех машин и 800 000 км для всех шин. Какой должен быть режим их поступления, или, иными словами, норма поступления запасов? Вариант 13.1. Решить поставленную задачу рекуррентным способом [10]. Вариант 13.2. Решить поставленную задачу, применяя расчет по математическим ожиданиям [10]. ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ 1.Сведение к задаче линейного программирования задачи темы 1. Пример. Пусть три типа судов следует распределить между четырьмя регулярными линиями. В приводимой ниже таблице заданы количества судов каждого типа, месячный объем перевозок каждым судном на каждой регулярной линии и соответствующие эксплуатационные расходы. N типа судна Þ N линии ß 1 2 3 Мини­мальный объем перевозок 1 300000 2 200000 3 100000 4 500000 Число судов 50 95 30 Составить математическую модель для задачи линейного программирования следующего содержания. Математическую модель составить для двух вариантов: 1.поставлено требование, чтобы в перевозках участвовали все суда; 2. часть судов, при условии выполнения условия минимального объема перевозок разрешается сдавать в аренду. Обозначим через число судов j- го типа (j =1,2,3), которое планируется закрепить за i -й (i -1,2,3,4) регулярной линией. С учетом введенных обозначений математическая модель задачи для 1-го варианта может быть представлена найти при ограничениях и при Последние три ограничения в виде равенств учитывают требования первого варианта о задействовании в перевозке груза всех судов. Математическая модель для 2-го варианта может быть представлена и при Рекомендация . В большинстве учебных пособий симплекс-метод, метод симплекс-таблиц изложен так, что переменные задачи линейного программирования имеют один индекс, т.е. Поэтому имеет смысл ввести новые обозначения в представленных выше математических моделях. Например, для первого варианта: найти при ограничениях и при Из сопоставления двух моделей для и видно, что соответствует и соответствует 2.Сведение к задаче линейного программирования задачи темы 2 Пример . Пусть для выполнения некоторой производственной программы, рассчитанной на пять последовательных дней, требуется к началу -го дня единиц специального инструмента, который к концу дня весь изнашивается, при этом Часть (весь) изношенного инструмента в конце -го дня может сдаваться в обычный ремонт, часть (весь) в срочный, а часть (весь) может не сдаваться в ремонт, оставаясь например на складе использованного инструмента. Пусть обычный ремонт одного инструмента длится дня и стоит руб., а срочный ремонт одного инструмента длится день и стоит рублей. Кроме того, один новый инструмент стоит рублей. Составить математическую модель задачи линейного программирования. Введем следующие обозначения: число инструментов, покупаемых для использования в й день; число инструментов, сдаваемых в обычный ремонт в конце -го дня; число инструментов, сдаваемых в срочный ремонт в конце го дня; число изношенных инструментов, оставшихся не сданными в ремонт к концу го дня. Тогда число инструментов, поступающих в употребление в начале го дня, состоит: из инструментов, сданных в обычный ремонт дней назад и полученных из ремонта в конце го дня; из инструментов, сданных в срочный ремонт дней назад и полученных из ремонта в конце го дня; из инструментов, приобретенных к началу го дня, т.е. где количество инструмента, купленного для использования в 1-й день; , так как до начала выполнения производственной программы в ремонт не мог поступать использованный инструмент и в первые дней (в нашем случае 2 дня) еще не поступит из ремонта в употребление ни одного инструмента, сданного даже в срочный ремонт, а в первые дней (в нашем случае 3 дня) не поступит в употребление ни одного инструмента, сданного в обычный ремонт. В конце го дня окажутся использованными инструментов, бывших в употреблении в этот день и инструментов, оставшихся не сданными в ремонт к концу го дня, т.е. , из них единиц поступает в обычный ремонт, единиц - в срочный ремонт и осталось не сданными в ремонт единиц инструмента При этом надо учесть, что инструмент, который возвратится из ремонта в конце го (в нашем случае 5-го дня) и позже, уже не понадобится. Поэтому еще за дней (в нашем случае один день) до конца программы не следует сдавать его в обычный ремонт, т.е. и за дней ( в нашем случае за два дня) до конца программы не следует сдавать его в срочный ремонт, т.е. За весь срок выполнения производственной программы будет куплено инструментов и израсходовано на это рублей; будет сдано в обычный ремонт инструментов и израсходовано рублей; будет сдано в срочный ремонт инструментов и израсходовано на это рублей. Тем самым задача заключается в минимизации общей стоимости издержек при ограничениях и условиях 3.Сведение к транспортной задаче задачи темы 2.