Методические указания по курсам Исследование операций и Математическое программирование

МИНИСТЕРСТВО в ы с ш е г о и СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ СССР московский АВТОМОБИЛЬНО - ДОРОЖНЫЙ ИНСТИТУТ

А.в.Ефремов, И.З.Лнтвин, С.Т.Худяков

МЕТОДИЧЕСКИЕ УКАЗАШ! ПО КУРСАМ "ИССЛЕДОВАНИЕ ОПЕРАЦИЙ" И "МАТЕМАТИЧЕСКОЕ ПРОГРАШИРОВАНИЕ"

Р Н БИБЛИОТЕКИ ?1 А Д И

МОСКВА - '

ПРВДСЛОВИВ Методическмв указания являются руководство!! в оргааизащш и ироведеним самостоятельной работы гфи шзучеши курсов "Иссле­ дование оаераций" • "Математическое программирование" и пред­ назначены для студентов я преподавателей,Указбшия включают о б ­ щую характеристик курсов, особенности самостоятельной работы и отчетности, тематику, содержание и порядок выполнения расчетно-исследовательских работ, а также задачи для самостоятельного решения и контроля знаний студентов. Большинство из помещенных в указаниях задач составлены автораш. Однако некоторые аз нях заимствованы из известных пособий по иоследовашоо операций и математическому программировании [1-3,5-1о] . Помимо основных авторов в написании пособия принимал участие доцент Пустовалов В.А..Им сформулировано задание на расчетно исследовательскую работу для студентов факультета ОПД.

ЧАСТЬ I . САМОСТОЯТЕЛЬНА,! РАБОТА. СОДЕРЖАНИЕ КУРССГ,. РЕКОМЩЦУЫДАЯ ЛИТЕРАТУРА § I. Особенности курсов Среди многочисленных задач, связанных с дальнеЛтом разв!-, тием сштомобильного транспорта и дорожного строительства,яа*1 более важной является задача совершенствования управления. Современные автотранспортные и ремонтные предприятия, констр торские бюро и научно- исследовательские институты, заправо" ные станции и станщи обслуживания автомобилей представ ля».? собой сложные организационно- тех»шческие системы, эффектив­ ность 'й^нюдаонирования которых сущесгвеннс зависит от качес, управления этими системами. Для достижения высокого качест? упрчьления такиг.и системами или их элементами совре:/енно^•

руководителю недостаточно иметь личяыв опыт и организаторские способности в их традиционном понимании. При подготовке решений руководитель выяуаден учитывать многочисленные факторы» часто противоречивые оообраяення и опиратьоя при выборе окончательного решения на сложные критерии эффективности достижения конеадых целей. При решении широкого круга задач оптимизации управляющих решений больщую помощь руководителю оказывает исследование опе­ раций и ее составная часть- математическое программирование. Исследование операций представляет собой прикладную математичес­ кую науку^ изучающую принципы выбора наилучпшх (оптимальных) решений при управлени» целенаправленными процессами (операциями). Исследование операци*- сравнительно молодая наука. Ее возникно­ вение обычно относят к годам второй мировой войны. Зародившись в области преимущественно военных задач, исследование операций с течением времени вышло из этой узкой сферы. В настояцее время исследование операций- одна на самых быстро развивающихся наук, завоевывакйцая все более обширные области применения. Методы этой науки в последние годы прочно вошли в гфактику многих организа­ ций автомобильного транспорта и дорожного строительства. Задачи исследования операций^ к какой бы области они не относились, имеют общие черты, и при их решении применяются сходные методо­ логические щривмы. Методология операционного исследования вклю­ чает системный анализ задачи организационного управления, постро­ ение математической модели и поиск оптимального (по тому или ино­ му критерию) решения с использованием соответствующего математи­ ческого аппарата. При изучении исследования операций студенты встретятся с рядом новых понятий и с целым арсеналом математичес­ ких средств» К ним относятся: теория вероятностей с ее новейшими разделами (теория случайных процессов, теория массового обслужи­ вания), математические методы оптимизации, начиная от простей­ ших способов нахождения экстремумов, знакомых студенту по курсу "Высшая математика", и кончая современными методами, такими, как линейное, нелинейное и динамическое программирован, е , теория игр. При чтении курса "Исследование операций" предполагается, что сту­ дент владеет основа1МИ математического анализа и элементами теории вероятностей. Следует особо отметить, что эффективность операционных методов анализа и поиска оптимального решения существенна возрастает при

всцользоваям влектронно-вычислитвльной твхиикш, В связи о вти!' в курсе уделяется большое вшшанве решешоо задач о юоольэояа вием ЭДВМ, что требует от студентов знания олгориташчв ЕЛ язи ков • владения основами машинного 1фограммировашш.

Самостоятельная работа п отчетность Новые ооаятия исследовання операций и иатематкческого ирограм иирования, приложения математических методов к задачам и^>актики требует пристального внимания и глубокого осмыслсвааия. чти может быть достигнуто при повседневной оамостоятельвой работе над курса­ ми. Самостоятельная работа вклсчает: - активное восприятие лекционного материала в процессе чтэння лекций; - самостоятельную проработку лекционного материала; - дополнение лекционного матери81ла о нопольаоваяием рекомеядованной учебной и монографической литературы; - бцстивное участие в работе на практическжх • семгнарскнх аааятиях; - самостоятельное решение задач по отработанным на орактическнх занятиях темам; - самостоятельное выполнение предуомотренной срох^анмой • графи­ ком учебного процесса расчетно- исследовательокой работы; - участив в научно- нсследовательской работе. При этом достаточно прочное усвоение материалов одной прочитанной лекции, -знакомство с учебной и монографической литературой по теме лекции требует не менее 2-х часов самостоятельной работы студента. Самостоятельная работа студентов над курсом направляет­ ся и контролируется лектором • преподавателем, проводящим практи­ ческие занятия. Для контроля и активизации самостоятельной рабо­ ты планом прохождения курса предусматривается проведение: - письменных 2 часовых контрольных работ, каждый вариант кото­ рых включает несколько задач по пройденным темам; - серии письменных 15- минутных контрольных летучек, каж,ций ва­ риант которых включает одну- две задачи по одной из пройденных тем; - семинарские занятия с заслушиванием и обсуждением докладов и

геф«ратов студентов по темам, предложенным преподавателем для "олее глубокой проработки наиболее важного материала курса; м.[фоса студентов на лекционных и практических занятиях. Лень проведения контрольных работ предусматривается графиком учебного процесса. Дни проведения контрольных летучек устанав­ ливаются преподавателем, ведущим практические занятия. При про­ ведении контрольных работ и контрольных летучек используются разрабоганные в утгержденные кафедрой варианты. В соответствии с программой кэздый студент в ходе изучения курса обязан выпол­ нить расчетно-исследовательскую работу. Работа имеет самостоятель­ ный характер, охватывает нрчболее важные для данной специальности темы и предусматривает использование современных ЭВМ. Сроки выдачи и сдачи расчетно- исследовательской работы устанавливают­ ся графиком учебного процесса. Ответственным за определение сро­ ков проведения контрольных и расчетно- исследовательских работ, указываемых в графиках учебного процесса, является лектор пото­ к а . Эти сроки через кафедру заблаговременно сообщаются в учебный отдел института и соответствующий деканат. Изучение курса в зависимости от специальности заканчивается зачетом или экзаменом. Зачет и экзамен включают опрос по теории й решение задач. Зачет выставляется студентам, показавшим твер­ дые знания основного теоретического материала курса и умеющим решать практические задачи. Зачет носит индивидуальный характер. Он принимается преподавателем, проводящим практические занятия, в установленный для группы день зачетной недели. В отдельных слу­ чаях студенты, проявившие особый интерес к курсу, систематически работавшие в течение семестра и имеющие только отличные оценки за текущую успеваемость по всем летучкам, контрольной и расчет­ н о - исследовательской работам, могут быть освобождены от офи­ циальной сдачи зачета. Экзамен сдается всеми студентами. Экзаменационная оценка выстав­ ляется в соответствии со следующими критериями оценки знаний студентов, разработанными Минвуз"ом СССР. Оценка "ОТЛИЧНО" выставляется студенту, глубоко и прочно усво­ ившему программный материал, ясчерпьгеающе, последовательно, гра- ^ мотно и логически стройно его излагающему, в ответе которого тесно увязывается теория с практикой. При этом студент легко находит ответ при видоизменении задания, свободно справляется 6

с задачами, вопросами и другими видами применения знаний, иоя;1зьЙает знакомство с монографической литературой, П).>авил1 но обос повывает принятые решения, владеет разносторонними нар ж-ши и приемами выполнения практических работ. Оценка "ХОРОШО"выставляется студенту, твердо знающему 1'рогр(Шмный материал, грамотно и по существу излагающему е г о , не доиускающему существенных неточностей в ответе на вопрос, ьрарильно применяющему теретические положения при решешш практических вопросов и задач, владеющему необходимыми навыками и приемами XX выполнения. Опенка "УДОВЛЕТВОРИТЕЛЬНО" выставляется студенту, которыЛ имеет знания только основного материала, но не усвоил его деталей, допускает неточности, недостаточно правильные формулировки, нару­ шения последовательности в изложении программного материала и испытывает затруднения в выполнении практжчесряи работ. Оценка '^{ЕУДОВЛЕТВОРИТЕЛЬНО" выставляется студенту, который не знает значительной части программного материала, допускает суще­ ственные ошибки, неуверенно, с большими затруднениями вынолня'-' практические работы. Студенты, не написавшие на положительную оценку контрольной р жооты и не сдавшие и не заидатившие в срок расчетно-исследовате и ской работы, к зачету и экзамену не допускаются.

§ 3. Содержание курса "Исследование операций" В соответствии с учебными планами курс "Исследование опера­ ций" читается в рамках курса "Высшая математика" на &- м семес­ тре обучения для студентов факультетов АТ,ДМ,КМ,ОГЩ дневнсЛ и вечерней 1|)орм обучения. Содержание курса определяется типовими и рабочими программами. В рабочей программе курса для стулен-^ указаяних (акулътетов предусмотрено изучение следующих тгм / вопросов. Введение '^е1;:е!тя партии и правительства о совершенствовашгн методов управления производством и повы1иении уроню! планово-гчсоиогг,- ч-' кой работы во всех эвень>тх народного хозяйства. Исследование

оп» раци! как одна кз важне1шва комплексных прикладных математи­ ческих дисциплин, охватываюори вопросы оргаяжзациоаного управле­ ния в принятия решений. Связь исследования операций с другжмв наукам». Краткий исторический очерк развятия исследования опера­ ций. Роль советских ученых в становления я развитии нсследованм операций. Структура курса. Особенность самостоятельно! работы. Отчетность з а курс. Рекомендуемая литература. Тема I» Основные принципы исследования операций Оиерашя. Цель операции. Эффективность операции. Критерий эффектгаиостн операции. Оптимальное решение. Математическая юдель «тврацнн; Основ:ш« этапы операщонного исследования: постановка задачи, построение математической модели операции, выбор метода решения.Типичные задачи нсслядоваяия операций. Классификация за­ дач. Принципы принятия решений и выбора критериев эффективности. Принятие решеии! в условиях определенности и неопределенности, Частные и обобщенные 1фитврии эффективности. | е м а 2^ Мето^;и ^сследованиа эффективности оперятуг^ Общая характеристике методов исследования и оценки эффективности оиерацЕй. Прямые и 1«)сввнныв методы, аяалитаческие я статисти'^^скр*- методы. Случайные функции. Законы распределения и характерис­ тики олучайных функций. Основные типы случайных процессов. Мар­ ковский случайный процесс. Нормальный случайный процесс. Потоки случайных событий. Стационарность, ординарность, последействие. Простейши! поток, Нестацион^ный пуассоновсквй поток. Потоки Эрланга. Системы массового обслуяивания о отказами и ожиданием. Уравнение Эрланга. Оценка эффективности систем массового обслуиивания. Статистическое моделирование. Уоделироваяие сл]гчайных величия, случайных событий и случайных процессов. Ыоделирование систем массового обсдуиивания. Тема 3> Методы решения акстремальннх задач в статических линей­ ных моделях Постановка задачи линейного программирования. Геометрическая внтер{фетвция задачи. Каноническая форма записи задачи линейно­ го программирования. Теорема о сущестговашш решения. Базис опор­ ного плана. Базисные переменные. Симсгвкс- метод. Идея метода. Формулы и условия перехода. Признаки прекращения счета. Таблич­ ный симплекс- метод- Фо^1«врсваяие опорного базисного решения. Фиктивный б а з и с . М-задача, Скмплеко- таблица. Пересчет алементов в

т ^ л ю д 1 . Отыскание решения. Двойственная задача линейного прог­ раммирования. Структура и свойства двойственной задач!». Транспорт­ ная задача линейного программирования. Спорные планы ргшспортной задачи. Методы нахождения опорных планов. Решение трагзаортной задачи. Метод потенциалов. Тема 4, Методы решения экстремальных задач в статических нелиней­ ных моделях Постановка задачи нелгнейного программирования. Особенности и об­ щая характеристика методов решения задач нелинейного гфограммирования. Аналитические методы решения нелинейных экстремал^^шх з а ­ дач. Метод множителей Лагранжа. Теорема Куна-Таккера. Выпуклое программирование. Методы пошаговой оптимизации. Градиентный метод. Метод н а и с к о р ^ е г о спуска. Учет ограничений. Метод штрафных функций. Метод конфигураций. Тема 5. Методы решения экстремальных задач в динамических моделях Динамические модели. Классификация моделей. Общая характеристика методов решения экстремальных задач в динамических моделях. Условные и безусловные оптимальные решения ( управления). Метод динамического программирования. Принцип оптимальности, функцио­ нальные уравнен :3вллмана и методы их решения. Тема 6, Методы решения экстремальных задач в конфликтной ситуации Понятие конфликтной ситуации. Определение игр. Классификация игр. Решение простейших матричных игр. Заключение Тенденции и перспективы развития исследования операций. Актуаль­ ные задачи оптимизации в области проектирования, испыташий и эксплуатации автомобильно- дорожных средств и систем. Тема расчетнэ-исследователъской работы для студентов факультетов КГ.т.1а Исследование эфезда КПСС о роли прикладной математики в решении задач упрайленю: народным хозяйствам. Основные принципы исследо­ вания операций. Показатель эффективности. Этапы решения задачи исследования операций: построение математической модели, ее опти­ мизация.. Разделы исследования операций, включаемые в курс "Мате­ матическое программирование". Структура курса. Особенности само­ стоятельной работы. Отчетность за курс. Рекомендуемая литература. Тема I , Математические модели линейного программирования Математическая модель линейного программирования. Задача линей­ ного программировакля. Каноническая форма задачи линейного программщ)ования. Векторные и матричные формы записи. Приведение за­ дачи теиейного программирования к каноническом!' виду. Понятие плана. Оптимальный план. Опорный план. Геометрическая структура множества решений. Многогранник решений. Теорема об оптимальном алане. Графический метод решения задачи линейного программирова­ ния. Угловые точки к опорные планы. Решение задачи линейного арограммирования методом перебора опорных планов. Симплекс-метод. Алгебра симплекс-метода. Критерии ввода векторов в базис и выво­ да векторов из базиса, Симплеко-таблица. Метод фиктивного базиса. М-вадача. Двойственность в линейном программировании. Двойствен­ ные несимметричные задачи. Первая теорема двойственности. Двой­ ственные симметри-чные задачи. Вторая'теорема двойственности. Целочисленное программирование. Геометрическая интерпретация ме­ тода Гомори. Составление дополнительного ограничения в методе юмори. Задача об оптимальном раскрое. Транспортная задача. Суще. гвование планов. Свойства матрицы планирования. Цикличность 1прных планов. Методы северо-западного угла и минимальной стои­ мости. Свойства оптимальных планов транспортной задачи. Теорема (ьннияг'а. М"тод потенциалов. Этапы решения транспортной задачи. 10

За^дача об оптимальном закреплении операций. Задача о на.1ыаче-и?|. Сема 2. Принципы принятия решений в исследовании операций Задачи исследования операций в условиях определенности. Частно; а обобщенные показатели эффективности. Метод экспертных оценок. Йетод уровеняых коэффициентов.. Задачи исследования операгдай в условиях неопределенности. Матрица рисковЛСритерии мини^^ума рис­ ка, Вальда, Сэвиджа. Гурвица. Гема 3. Математические модели матричных игр Зсновные понятия матричных игр. Игры с нулевой с у ш о й . Платежная 14атрица. Чистые и смешанные стратегии. Выбор показателей «ффектин яости. Оптимизация моделей матричных и г р . Способы нахоядегшя огпв мальных стратегий. Теорема о седловой точке. Решение игр симплексметодом. Оптимальные стратегии игроков и двойственные зекдачи линейного программирования. Решение некоторых игр, Гема 4 . Математические модели сетевого планирования Понятие о графах и сетях. Элементы теории графов. Задача о макси­ мальном потоке. Основные теоремы о потоке в сети. Алгоритм ФордаФалкерсона, Задача о критическом пути. Область применения при планировании и управлении. Гема 5. Математические модели динамического программирования Задачи динамического программирования. Построение математическо'* модели. Понятие управления. Показатель эффективности. Фазовое пространство. Принцип оптимальности Беллмана. Задача оптималь) ро распределения ресурсов. Тема 6. Математические модели нелинейного программирования Метод множителей Лагранжа, Теорема Куна-Таккера а область ее риложения. Выпуклое программирование. Квадратичное прохфаммир 'Т'чние. Метод Франка-Вольфа, Градиентные методы . Метод наискорей­ шего спуска. Метод штрафных функций. Метод кон(|игураций. Тема расчетно-исследовательской работы Разработка оптимального плана распределения автобусов по маршру-

§ 5, Содержание практических занятий Групповне пра1ктичвские занятия являются основной формой ра­ боты студентов над курсами под руководством преподавателя. 11

•1а прачтических занятиях могут разъясняться некоторые наиболее трудные для понимания вопросы теории, но основная цель занятий состоит в овладении обучающимися приемавш и навыками решения практических задач наиболее близких по тематике к щюфялю их буду­ щей деятельности.Построение практических занятий может быть р а з ­ личным. Как правило такое построение включает: - проверку домашних заданий; -опрос по теории р -рассмотрение результатов опроса, корректировку и разъяснение допущенных ошибок; - решение заДач по теме практического занятия; - выдачу задания на самостоятельную работу. Помимо этого на практических занятиях с целью контроля самостоя­ тельной работы студентов и степени усвояемости курса Щ)Оводятся письменные контрольные работы и контрольные летучки. Контрольная работа проводится по нескольким пройденным темам, включает толь­ ко задачи и рассчитывается на практическое занятие, т . е . на два часа самостоятельной работы студента. Допускается проведение контрольной работы по одной, наиболее важной и объемной теме курса. Контрольная летучка проводится по одной из пройденных тем или по наиболее важному вопросу темы. Она включает обычно одну задачу, рассчитанную на решение в течение 10-15 минут. Контроль­ ные летучки могут быть проведены в начале занятия по ранее отра­ ботанной теме или в конце занятия по теме, пройденной на этом ИЛЕ предыдущем занятии. На практических занятиях при индивидуальной работе с обучающимися должна быть обеспечена максимальная актив­ ность каждого студента и его непременное участие в решении и об­ суждении итогов или этапов решения каждой задачи или вопроса тео­ рии .Практические занятия проводятся по единым методическим разра­ боткам на каддое практическое занятие ^ утвержденным кафедрой. Задачи подбираются из настоящих методических указаний или из дру­ гих учебных пособий по исследованию операций и математическому программированию о учетом профиля подготавливаемых специалистов. Тематика и последовательность практических занятий строго увя­ зывается с лекционным материалом, что обеспечивается постоянным контактом между лектором и преподавателем- ассистентом. Содержание практических занятий по курсу"Исследование операций" Факультеты АТ,НМ,ОПД (дневная форма обучения) I . Операции с векторами и матрицами. Система линейных уравнений. 12

Еоо^1ановы исклочеяш!. 2 . Построение иатематичесно! модели операции. 3. Принятие решений в условиях определенности. 4. Принятие решений в условиях неопределенности. 5. КЧгфковский случайный процесс. 6 . Аналитические методы исследования эффективности систем массо­ вого обслуживания, 7 . Исследование эффективности систем массового обслуживания мето­ дом статистических испытаний, 8. Каноническая форма записи и графически! метод решения задач линейного программирования. 9,10, Решение задачи лияв!ного Хфограммировавия симплекс- методом. I I . Контрольная работа. 12,13, Транспортная задача линейного программирования, 14.Аналитические методы отыскания экстремума нелинейной функции. 15. Градиентный метод. 16, Задача динамического программирования. Факультет ДМ (дневная форма обучения) I , Операции с векторами и матрицами. 2, Принятие решений в условиях определенности и неопределенности. 3. Марковский случайный процесс. Аналитичесгле методы иса;хедования эффективности систем массового обслуживания. 4. Исследование эффективности систем массового обслуживания мето­ дом статистических испытаний. 5,6. Симплекс- метод решения задачи линейного программирования. 7. Контрольная работа. 8. Метод множителей Лагранжа и методы пошаговой оптимизации. Факультеты Д'1\АТ.0ПД (вечерняя фоуш обучения) I . Операции с векторами и матрицами. 2. Принятие решений в условиях определенности и неопределенности. 3, 1Ларковский случайный процесс. Аналитические методы исследова­ ния эффективности систем шссового обслуживания. 4 , Исследование эффективности систем массового обслуживания мето­ дом статистических испытаний, 5,6. Симплекс-метод решения задачи линейного программирования. 7 , Контрольная работа. 8. Метод мисжителей Лагранжа и методы пошаговой, оптимизапди. 9, Задача динамического програV!мирования, 13

Содержание практичесюсс занятий по курсу "Математическое прог­ раммирование" I . Приведение задач линейного программирования к каноническому виду. 2. Приведение задач линейного программирования к каноническому виду. 3 . Построение многогранника решений. Графический метод решения задач линейного программирования. 4 . Графический метод решения задач линейного программирования. 5» Контрольная работа. 6.Решение задач линейного программирования методом перебора опорных плешов. 7, Симплекс— метод. 8 . Симплекс- метод, М-задача. 9, Симплекс-метод, М-эадача. 10, Контрольная работа. I I . Двойственные задачи линейного программирования. 12. Транспортная задача. 13. Транспортная задача. 14. Контрольная работа. 15, Принятие решений в условиях определенности и неопределеннос­ ти. 16, Ршпение игр. 17. Выдача заданий на расчетно-исследовательскую работу. 18. Решение задач сетевого планирования, 19. Решение задач динамического программирования. 20. Решение задач динамического программирования. 2 1 , Контрольная работа. 22. Геометрическая интерпретация нелинейных задач, 23. Квадратичное программирование, 24, Метод множителей Лагранжа.

§ 6. Рекомендуемая литература Для глубокого усвоения и осмысливания курсов недостаточно использования только лекционного материала. В дополнение к лекциям необходимо знакомиться о учебной и монографической ли' 14

тер&турой- Научить будущих специалистов умению работать с лите раУурой- важная и трудная задача каждого преподавателя читшаун • го лекции или проводящего практические занятия. Каждый зтудент должен чувствовать настоятельную потребность обращаться к лите­ ратуре в процессе обучения и нахоЖить в ней саглостоятелъно отве­ ты на интересующие его вопросы, расширяя тем самым свой кругозор и существенно дополняя лекционный материал, в котором могут быть только постановки нерешенных вопросов или краткий анализ лерспектив развития той или иной проблемы науки. Приводимая ниже литература разбита на три категории. В первую ка­ тегорию включена основная литература., предусмотренная ра(^чей программой курса. Изучение этой литературы считается обязательны.'. для каждого студента. При этом особое внимание следует уделить изучению учебных пособий, изданных в институте. Ко второй катего­ рии отнесена дополнительная литература, которая также предусмот­ рена рабочей программой курса и хюторая при неооходамости может заменить или дополнить основную литературу. К третьей категории относится литература монографического характера, (на может бить использована студентами и преподавателями для более углубленного изучения отдельных вопросов исследования операций и математичес­ кого программирования при подготовке студента^щ ре()тератов и ;,ч1,1->7о. 4. В^релюв А.В. Методические разработки к решению задач линей­ ного программирования с помощью ЭЦВМ по курсу "Исследование операций".-.'б'.: МАЛИ, 1977. 5. Ефремов А.Ь. Методические указания к решению задач математи­ ческого программирования с применением ЭВи.-и.: ЩДи,197В. 1Ь

• . Зайчелко С П , Исследование операций.-Киев: Вища школа,1977. V. Кодолов И.М., Ефремов А.В., Цальп В.Д* Методы оптимизации в инженерных и акономичесюгх задачах (линейные модели) .-М.:МАДИ, 1978.

I 2 I

2 I I

ф

2 I I

I -I -I

-2 2 I

8)

2 -I -2

-I 3 2

2 I -2

1.17. С помощью Щ)еобраэований Жордана- Гаусса вычислить ранг матриц: 1)

28

I 2 а

3 -I 3

5 3 19

4 I II

г

3 - 2 5 1 8

4 1 7 2

3 -I I 7

I 2 5 7

5 -3 -I 9

3 е 3 3 6

- I 4 7 I

-Б -7 -е I -I

2 4 2 2 4

2 7 -в

1.18. Определить ранг патрицы и установить вид лииейноЯ эввясииости между векторами дли следупцкх матриц: 6 5 8 7

2 I 2 3

2 2 3 2

6 4 7 8

3 3 2 о

& 7 6 1

I 2 2 I

9 12 10 7

2 I 3 2

2 -3 5 0

4 -4 9 I

I 2 2 3

4 5 4 5

3 3 2 2

|1 -I 11 3 4 11 3 5 1 I 11 2

3 2 Г

..з|

Ф 1 5 7 & 8

. '

2| : 8) 1 I 3 3' 2' • ! 2 Г» • 1 3 О! :

3 8 5 7

|ь 5 4 3

8 7 6 5

2 9 2 т

6) !I I 1• 2 • 11 ;•:)

5 7 3

2 3

3)

•"•'

; 2 2

2

9, !! ; • 1 1( 1 1 12 1 !

4 5 8 7

4 2

I 2 3 3

3 2 2 2 °1 I 4 1

4, с• 1

1 Л 9 . Найти линейную комОинацив векторов '^11.2 - А3 , ео;;;. А^ = ( 4 , I , 3 . - 2 ) ; А2 « ( I . 2 . - 3 , 2 ) , А3 ="( й>, 9, I . - Ь ) . 1.20. Найти вектор X из уравнений: I) + 2А2 + ЗАу + 4Х = О, ес^^. А1 = ( 5 . - 8 , - 1 . 2) ; .Ъ, = ( 2 . - 1 , 4. - З )

;

Ду = ( - 3 , 2, - 5 , 4)

2) 3 (А^ - Х) + 2 (Аз ^ Х) = 5 (А3 + Х) , если А ^ = ( 2 , 5, I , 3 ) ; А2 = (10. I , 5, 10) ; Аз = ( 4 , 1 . - 1 . 1) . 1.21. Пусть векторы А^, А2, Ад линейно эависимь и А/^ не выражаетсь линейно через А^ и А2. Доказать, что вркторы А| и А^ ра:)личаются между собой лишь числоиым шюжителем. 1,2:^. Установить, что векторы А^ = ( 1 , 2) и А2 = ( 2 , 3 ) базис и выразить вектор А = (О, 4) через него.

.П[,П1УЙ

1,2:). Найти базис системы векторов и разложить все векторы этой системы по базису: I)

А1 = ( I , 2 , З ) ^ А2 » ( 2 , 3 , 4) ; А4 = ( 4 , 3 , 4 ) ^ А5 « ( I , I . I ) . А!» (2, - I ) ;

3)

% = (3, А1 = ( 2 ,

А3 = ( 3 , 2. 3^ ;

= ( - 1 , 2) ;

А3 » С З . I ) ;

=(2. З) .

I) ;

Аз = ( I , I ) ;

А3 = С З . - 1 ) ;

А4 =(12, З ) .

I ) ;

А2=(1.~1);

Ад» ( 1 . 2 ) ;

А4=(3.

5)

^1 = ( 2 . I , 3 ) ; А. = СО^ I . 0 ) ;

А2 = ( 1 . О, О) ; Аб = ( 0 . 0. I ) ;

6)

А^ = ( I , 1 , 0 , 1 ) ; А4 5.-6, I ) ; А^ = С 0 , О, О, I ) ;

2).

Ад -=(-1, 2,-2) ; =(3^-2.. I ) .

Ад = ( 1 , - 1 ^ I , О) ;. Ад = ( О , 1 , - 1 , О) ; А5 = ( 4 , - 4 , 5, 3 ) ; А^ = ( I , 6 , - 1 . I ) ; Ад =Сг6, 8,-12.-3) .

1.24. Дан вектор А - ( - 2 , Определить, составляют ли Если составляют, то найти же вектора в этих базисах

I ) в базисе 82 » ( I , О) и В2 =(0, 1). базис векторы С^ = ( 2 , I ) и С2 = ( 1 . ! ) • свлзь между координатами одного и того и выразить вектор А в новом базисе.

1.25. Дана система вактаров : А1 - ( I , 2 , 3 , 4 ) ^ А2 = С-4, 3 „ - 2 . I ) ; Ад = ( 2 , А4 = (3,. 2 , I , 5 ) ; А5 = ( - 1 , - 2 , 3 , 2 ) ; А^ =(-3, Найти базис этой системы, разложить векторы систшы перейти к новому базису и раалокЕТЬ вектор» системы бавису.

1.-1,-3) ; 4 , 2, З ) . по базису, по новому

1,26. В естественном базисе заданы векторы. Установить, состав­ ляют ли они б а з и с . Бели составляют, то найти связь между старым и новым базисом, а также найти в новом базисе компоненты вектора В = ( 2 , - 5 , 4) . Ад = ( 1 , 3, 2 ) . А^ - ( 2 . О, I") О = ( 3 , 4„ 5) Ад = ( 0 , 7 , Р ) . 2) А^ = ( 9 . 3„ 0 ) А2 = ( 7 . 4, 3 ) Ад = ( 2 , О, Ю ) . А2 - ( 4 , 7 , - 3 ) 3) Ау = ( 3 , 9, 5 ) Ад = ( 5 , 1 4 , 9 ) . О А^ = ( 2 , 2, 0 ) А2 =(-!» 3 , 5 ) = (5,-3,-2) , Л2 = ( 3 . 0 , »:> 5) А| ( 2 . 7, 5 ) 6) Ау -- ( I , 4, 5:) ; к;^ 9, Ю : % 0. I ) •

1.^7.

Определить вое базисные решения системы ;уанн&ии(' + ЗХд = 2 ; + = 3 .

2)

^2 + ^3 = 3 ; ^2 + 2X3 = 2 .

4)

+ 2X2 + = 4 ; - 3 X 2 + 2X3 = I .

6)

I) 3)

* »1 -

5) 7)

*1

+ ЗХ3 . — »3 =

• •

+ 2X2 + 3x3 = + + 2х., =

I , 1.-'' ^ 3.

2X1 'I +

н

+ 2X3 — Хз =

3 ; 3 .

+2X2 -

- 2 ; = 2 .

8)

3X1 + 2X2 - Хд = ^1 — н + 2X3 =

а 1 I.

" ^2 + +2X2 -

=5 ; =1 .

10)

2х^ - н - 2X3 = Зх^ - 3X2 -

2 ; 4.

^1 9)

3X1 > *1 •

*3

1.28. Найти два базисных решения системы уравнений 'I »1

+ 3X2+ 2Хг Ч

Х3+ 2X4» - 3 ; ХдЧ Х4= О О *4=

Ц 2 9 . Исследовать на совместность, найти общее решение базионое решение для систем уравнений: 1^

х^ + 3X2 * ^ x^ - 2X2 * 2Х| +11X2

одно

* 7^4 * ^ = I ; •" *^4 * ^ ~ 2 ; *25Х4 +22X5 = 4 .

2) 2x^ - Х2 + ЗХ3 - 7x4= 5 ; 6Х| - 3X2 + Хд - 4X4= 7 ; 4x^ - 2X2 -31X4= 18 . З)

2Х| + 7X2 + ЗХд + Х4= 6 Зх 2 + 5X2 2 ^ + 2X4= 4 ЭхI • 4X2 + ^ + 7x4= 2

1.30.

Решить системы линейных уравнений методом 2x^+Хз= 2 2) ^2 Хд = 5 3X2 * зx^ + 5Хд = -7 4X12x^+ 3X23x3=14 3X2 ~

I)

3\ 5x3 =

. «От I о 3 ; О ; 3 ; 6.

3) Хт ^

-•- Хд +

в 6 ;

4) 82^1^

'

2x^+ 2X2 ~ 4^^+ " Зx^• 3X2 "

+ 4X4 ^ "•• ^4 -"З + 2x4 »

12 * » 6 ; б .

% 2» Математъгчвокие 1юдв.1ш ооеращс! 2,1. Нааовятв воэшжныв 1ефвтерш1 еффекпвноотж в слвдртпох опер»пняхг - работа автомоблльного завода, выпускающего раэлпные иЕф^а автоиобилеВ; - работа автотранопортвого предпрвятмя; - обслуживание автомобилев отанцие! технического о б с л у ш в а я м ; - обслуживание автомобилей бензозаправочной стаяхшей;. - приобретение автомобиле в личное пользование; - поездка на автомобиле из одного города в другой при а а л и ч п нескольких маршрутов; - строительство автомобильной дороги; - перевозка грузов автотранспортом от неокольвхх поотавщвков к нескольким потребитолям. 2,2, Запишите математх^ческую модель в задачах исследования опера­ ций: I ) Механическая мастерская выпускает два типа недели! • причем иэиетч каждого типа изготовляются двумя разными станками. При этом инготовление изделия первого типа требует трех часов работы пер­ вого станка и двух часов работы второго станка; изготовление и з делия второго типа требует соответственно двух и трех часов. Первый станок можно использовать только 8 часов, а второй - толь­ ко 7 часов в д е н ь . Прибыль, получаемая от реализация каящого иаделия,равна 200 р . , а количество реализуемых изделий и« имеет ог­ раничений. Определить количество каждого вида изделий, которое может быть произведено для получения наибольшей прибыли, 2} Предприятие планирует закупить несколько автомобиле! двух но­ вых марок А в В. Автомобиль марки А стоит 30 тыс. р . , а автомо­ биль марки В - 50 тыс.р. В гараже предприятия может поместиться ив больше 20 новых маоан. а аа заяупну машн ассигновано 700^ тыс .р

лжидпймяа прибыль ОТ эксплуатащш одной машины иесрт А равна 16* тыо.р, в г о д , а от эксплуатации машины марки В - 14 тыс.р. Определить количество закупаемых автомобилей каждой марки, кото­ рое обеспечит получение наибольшей прибыли. З) Промышленное объединение имеет два завода и два склада в раз­ ных частях страны. Каждый месяц первый завод производит 4 уоловяых единицы продукции, второй- 7. Вся продукция, произво.!Шмая заводами, должна быть вешравлена на склады. Вместимость пер­ вого склада равна 6 условным единицам продукции, второго- 5 , Издержки транспортировки в единицах стоимости условной ^ н х о ы продукции с завода 1(1 = 1,2) на склад ] С] = 1г2) приведены в табл. 2 . 1 . Таблица 2.1 Склады Заводы 2 I 4 5 I 7 2 3 Определить план верввозок (количество единиц продукции, отправ­ ляемое с 1-го завода на ^ -й склад) из условия минимизации ежемесячных расходов на транспортировку* 4) Имеется два хранилища с однородным продуктом, в которых Г'".; редоточено 200 и 120 тонн продукта соответственно. Продукт 105^. ходимо перевезти трем нотребителян в количестве 80, 100 я 1,40 тонн каждому. Расстояния от зфанилищ до потребителей (в 104,.) указаны в т а б л . 2.2. Таблица 2.2 Потребители Хранилища 2 3 I 30 I 20 50 2 60 20 40 Затраты на перевозку I тонны щюдукта на I им. оостоянаы и раввы 0,25 р . Определить план перевозок щюдукта из хранилищ к потре­ бителям из условия шшинизации транспортных расходов. 5^ У прямолинейного бервЕга реки частные владельцы получают участ­ ки для возделывания огородов. Каждому иэ них отпускается материал 33

для строительства забора длиной ^ Сберег реки забором не огорагкивается) . Найти размеры учазтка наибольшей площади, б) Проектируется юистерва для хранения жидкого топлива в форме прямого кругового цилиндра. На изготовление цистерны расходуется листовая с т а л ь , I м^ которой стоит С р . Цистерна должна вмещать не менее топлива. Найти размеры цистерны минима^1ьной стои­ мости. 2,3. Запишите математическую модель задачи 2,2,(1) для общего случая, обозначив x^ (^ «= 1 , 2 , . . л ) - количество изделий ^ - г о типа; ( ( = 1 , 2 , . . , , т ) - ресурс времени для I - г о станка; 011| - время, затрачиваемое на изготовление изделия ^ - г о типа яа I - и станке; С^ - стоимость изделия ^ - ^ о типа. 2,4. Запишите математичесвдпо модель задачи 2,2,(4)длн общего случая, обозначив х^|(1= 1 , 2 , . , , , Ш ; ^ = 1 , 2 , . . . , Л ) - коли­ чество единиц г р у з а , перевозимого из 1нго склада к ^-мупотреби­ телю; а ! , - запася груза на 1-м складе » ^' - потребности в грузе для ^ - г о потребителя ; С^^ - стоимость перевозки едини­ цы груза из I - г о склада к ^ - му потребителю. Модель запишите для случаев: - емкость складов не должна быть гфввышена, а заявки потребите­ лей должны быть удовлетворены; - сумма всех заявок равна сумме всех запасов,

§ 3, Принятие решений в условиях определенности 3.1. Рассматриваются четыре варианта землеройной дорожной машиян: А , Б , 3 , Г . Каждый вариант может применяться в условиях 1,2,3. Для оценки уровня качества машины используется комплексный показатель Кц, характеризующий производительность машины в м^ г.чунта/ час. Иеличины производительности для каждого варианта в соответствуюншх условиях приведены в табл. 3 , 1 . Необходимо выбрать лучший вариант дорожной машины на основании ( равнения средних взвешенных ари(|метических показателей, если

Вариант машины А Б В

1 20 25 15 30

Производительность Кц 2 30 20 25 25

в м^/ час 3 25 ' 30 50 20

Г коэффициенты весомости для различных условий равны © 4 = 0»24; с / з = 0,47.

» 0,29;

ЗЛФ Не'^бходимо определить средние взвешенные ари^етический в геометрический показатели надежности восстанавливаемых изделий трех вариа.тов А, Б , 3 и оценить уровень их качества» Основным показателем качества оцениваемых изде^шй принят коэффкциент готовности Ку • Значения коэффициентов готовности по группам условий I , 2 , 3 и коэффзциевты весомости, соотзетствукшше этим условиям, приведены в табл. 3.2. Варианты изделий А Б В Коэффициенты веса

I 0,46 0,40 0,02 0,2

Коэффициенты готовности К^. 2 3 0,64 0,60 0,67 0,72 0,71 0,90 0,3 0,5

3 . 3 . Для пяти щюектов технических уотройотв определены отнооятельные единичные показатели технического совершенства конст^ухц о и коэф|^щивнты в'^сшости единичных показателей. Чжсленшм значения единичных показателе! н воэффшвентоь весомости пржведены в табл, 3.3. Таблица 3.3 Варжавта Относительные единичные показатели техаичеоСложно­ Веоа Времевн Автома­ Моцнооти УШ!(]Вких у с т сти подго­ тизации кацки ройонв товки 1>2 «1 ч «4 % Кб 2 3 5 7 4 I б I ЦООО 0,068 1,000 1,000 0,721 0,614

Продолкевле таблкш 3.3 ——л I 2 3 7 4 5 6 2 0,720 0,807 0,416 0,800 0,780 1,000 3 0,658 0,358 0,916 0,765 0,524 0,780 4 0,423 0,970 0,980 0,310 0,755 0,700 5 0.467 0.865 0.660 0.554 0.700 0.864 Коэф(|ш01енты веса 0.157 0.195 0.140 0.210 Р. 124 9.174 Провеств ранжировку проектов технических устройств в соответствии со эначенил1|(и средних взвешенных арифлетичесхих обобтенннх пока­ зателей технического совершенотва конструкции»есла известно,что увеличению относительных единичных показателей соответствует улучшение конструкции. 3,4. Для ояти проектов транспортных устройств определены отно­ сительные единичные показатели технического совершенства кон­ струкций. Численные значения относительных единичных показателей приведены в т а б л . 3,4, Таблица 3.4 единичные показатели Относительные Варианты Скорости Прочнос­ Устой­ Мощности Металло- Перег­ транснортных у с т ­ чивости еикости рузки ти ройств % «6 ч % 0.91 • 1,000 0,767 1,000 0,798 1,000 I 0,924 0,936 0,920 0,652 1,000 1,000 2 0,941 0,924 0,929 0,933 0,929 1,000 3 1,000 0.974 1,000 0,915 0,875 0,956 4 1.000 0,971 0,967 1,000 0,875 0.781 5 Увеличению единичных показателей соответствует улучшение техничес­ кого совершенства транспортного устройства. Требуется определить оптимальный вариант проекта транспортного устройства из условия максимума обобщенного среднего взвешенного ари(|Еыетического пока­ з а т е л я . Коэффициенты весомости найти методом уроненных коэффициен­ тов с использованием процедуры обработки еддничных показателей по методу средних. • 3.5. Определить уровеп; кач< отва о.днотипннх двигателей разливших

в а ^ а н т о в и иайти оптимальннй вариант. За обобщенны! покаэате^^ь качества выбрать средни! взвешенный арифметический показатель. Абсолютные показатели качества двигателей различных вариантов приведены в табл, 3,5. Таблица 3.5 Абсолютные единичные показатели качества Варианты Маоса Крутящий моиент двигателей Мощность Кд, кг Крг КГС'М Ку,Л,С. 67.0 830 180 I 1000 70,7 176 2 860 66.0 176 3 830 66.9 181 4 860 67.9 177 5 790 66,3 180 6 910 69,0 175 7 850 67,8 176 8 890 68,1 180 9 890 68.2 179 1С При определении относительных единичных показателей качества абсолютные показатели качества эталонного (базового) варианта принять равными: К| = 185 л , с , ; к ! = 75 кгс«м ; Кд = 750 к г . Коэффициенты весомости определить по методу уроненных коэф^^яциентов с использованием процедура обработки относительных единичных показателей по методу средних.

^ 4 , Принятие решений в условиях веощ>еделенности 4.1. При выборе решения х^(1= 1,2,3) кавдому возможному состоя­ нию среды $к ( к = 1.2,3,4) соответствует один результат (исход) и . и ( 1 = 1,2.3 ; к = 1,2,3,4) . Элементы Иск , являющиеся мерой полезности результата, приведены в т а б л , 4 . Г ; Решения ^1 Ч

I 2 3 5

Состояния 2 6 9 I

средк ..3 % 1 6

4 В 4 2 37

Заяисать в виде таблиц» элементи матридн рисков я выОретк опти­ мальное решение в соответствии о критериями Вальда, Савидда и гурвица при бС в 0,5. 4.2, НамечаетсА крупномаоитабное производство легкового автомо­ биля. Имеется четыре варианта проекта автомобиля Х{^(1в 1,2,3,4) подготовленные отечиствешшми проектными органиэшщями. С по­ мощью экономических расчетов вычислена экономически 8ф|)ективностъ 11(1^ , характеризующая кавдыв из проектов в за]?тсимоств от рентабельности производства со истечению двзгх сроклв $('.4 650 3^1

Опредашггь напбслее цел сообразное количество обслуживаемых автомашин в проектируемой стшщии технического обслуживания с использованием различных нритериев, приняв равновероятные с о с ­ тояния среды при определении математических ожиданий полезности и риска ж = 0,5 гфи определении критерия Гурвица.

§ 5. Марковский случайный процесс 5.1 Система 5 - автоллашииа может находиться в одном из пяти возможных состояний: - исправна, работает; - неисправна, ожид^ает осмотра; - осматривается; - ремонтируется; - списана. Построить граф состояний системы. ;).2. Техническое устройство 5 состоит из двух узлов: I и II, каждый из которых может в ходе работы устройства отказать (выйти яз стрс«^ . Перечислить возможные состояния технического устрой­ ства и построить граф состояний для двух случаев: а) ремонт узлов в процессе работы устройства не ироизводится; о) откаяамгаий узел немедленно начинает восстанавливаться. п.З. Техническое устройство имеет два возможных состояния: 5^ - исправно, работает; - неисправно, ремонтируется. Матрица переходных вероятностей имеет вид р ^

0,7

0,3

0,8 0,2 Построить граф состояний. Найти вероятности состояний после треть­ его тага и в установившемся режиме, если в начально!- состоянли техническое устройство исправно. 5.4. Магазин продает две марки А и В автомобилей. Опыт эксплуата­ ции этих м ^ о к автомобилей свидетельствует о том, что для них имеют место различные матрицы переходных верояа'ностей, соответсти.уиияе состояниям "работает хорошо"(состояние I ) и "требует 40

реаюнта" (состояние 2 ) : автомобиль марки А, автомобиль марки В .

0,9

0.1

0,6 0,8

0г4 0,2

0,7 0,3 Элементы матрицы перехода ощ)еделены на годовой период эхоилуатации автомобиля. Требуется: I . Найти вероятности состояний для каждой марки автомобиля после двухлетней эксплуатации, если в начальном состоянии автомобиль "работает хорошо" ; 2 . Найти вероятности состояний в установившемся режиме для каждой марки автомобиля; 3 . Определить мар10г автомобиля, являющуюся более 1Ц)едпочяягель­ ной для приобретения в личное пользование. 5.5. Организация по прокату автомобилей в городе Я выдает автомобили нащ)0кат в трех пунктах города А, В, С. Клиенты могут возвращать автомобили в любой из трех пунктов. АН.АЛИЗ процесса возвращения автомобилей из проката в течение года показал, что клиенты возвращают автомобили в пункты А, В и С в соответствии с ьвроятностями, приведенными в табл. 5 . 1 . Таблица 5.1 Пункты приема автомобилей Пункты выдачи В С автомобилей А 0 0,2 0,8 А 0,8 0 0,2 В 0,6 0,2 0,2 С Требуется: I . В предположении, что число клиентов в городе не изменяется, найти процентное распределение клиентов, возвращающих автомобили по станциям проката к концу года, если в начале года оно было равномерным; 2. Найти вероятности состояний в установившемся режиме; 3. Определить пункт проката, у которого более целесообразно строить станцию по ремонту автомобил, 5.6. Водитель такси обнаружил, что если он находится в городе А, 41

то в среднем в 8 случаях из 10 он везет следующего пассажира в город В, в остальных случаях будет поездка по городу А. Если же он находится в городе В, то в среднем в 4 случаях из 10 он везет следующего пассажира в город А,, в остальных же случаях будет поездка по городу. В. Требуется; I . Перечислить возможные соотояния процесса и построить граф состояний; 2 , Записать матрицу первход1шх вероятностей; 3. Найти вероятности состояний после двух шагов процесса, если а) в начальном состояний водитель находится в городе А; /• издается три сатирических журнала: "Перец", "Лук", "Чеснок" и читатели подписывают только один из них. Пусть в среднем читатели стремятся поменять ядфнал» т . е . подписаться на другой не более одного раза в год и вероятности таких изме­ нений постоянны. Гезультаты изучения, спроса читателей на журналы цают следующее процентное соотношение: I . 80/? читателей возобновляют подписку на тот же журнал в следуюи|вм году; 2, 15% читателей "Перца" подписываются на "Лук"; 3. 1055 читателей "Лука" подписываются на "Чеснок"; 4. 93? читателей "Чеснока" подписываются на "Перец*. Требуется; I , Записать матрицу переходных вероятностей для средних годовых изменений; 2. Предположить, что общее число подписчиков в городе постоянно и определить, какая доля из их числа будет подписываться на ука­ занные журналы через два г о д а , если цо состоянию на I января теку­ щего года каждый журнал имел одинаковое число подписчиков; Найти вероятности состояний в установившемся рехчме и опреде­ лить журнал,, который будет пользоваться в будущем меньшим спросом V Читателей. ^..н. Техническое уетр>зйс-тво оэсиит адух дашв а может находить>';я в одн-:>м из состге,'ЯШи1:

- оба узла исправны, работают; - неисправен только первый узел; - неисправен только второй узел; - неисправны оба узла. Вероятность выхода из строя (отказов) после месячной эксплуатации для первого узла р-^ = 0,4; для второго Р2 = 0,3, а вероятность совместного выхода их из строя Р | 2 = 0 , 1 . В исходном состоянии оба узла исправны, работают. Записать матрицу переходных вероятностей и найти вероятности сос­ тояний после двухмесячной эксплуатации и вероятности состояний в установившемся реяиме. 5.9. Техническое устройство состоит из двух одинаковых параллель­ но соединенных узлов. Вероятность исправного состояния за месяц эксплуатации каждого узла равна 0,9, Узлы выходят из строя (отка­ зывают) независимо друг от друга. Если узел отказал, то он не подлежит восстановлению. Требуется: I . Перечислить возможные состояния марковской цепи, если в качес­ тве состояний рас сматривать комбинации исправных узлов; 2, Составить матрицу переходных вероятностей; 3. Найти вероятности состояний после двухмесячной эксплуатадаи устройства, если в начале первого месяца узлы исправны; 4. Найти вероятности состояний в установившемся режиме. 5,10. Дра кораб^и стреляют друг в друга одновременно и через рав­ ные промежутки времени. При каждом обмене выстрелами корабль А поражает корабль В с вероятностью 1/2, а корабль В поражает корабль А с вероятностью 3/8. Предполагается, что при любом попа­ дании корабль выходит из строя и следовательно не может произвес­ ти выстрела. Рассматриваются результаты серии выстрелов. Перечислить возможные состояния марковской цепи, если в качестве состояний рассматривать комбинации кораблей, оставишхся в строго. Состарить матрицу перехода. Определить вероятности состояний после обмена одним и двумя выстрелами, если в начальном состоянии оба корабля были в строю. 5.11. Человек сидит на одном из стульев в ряду из 11яти стульев. 43

Для определения овоах перемещений, он бросает игральную кость и поступает следующим образом: I . Если оа сидит не ьа крайнем с т у л е , ! о : - перемещается налево при выпадении I лли 2; - перемещается направо при выпадении 3 или 4; - остается на том же месте при выпадении 5 или 6. 2 . Если он сидит на крайнем стуле, то: - возвращается на средний стул» когда выпадет нечетное число; — остается на том же месте при выпадении четного числа. Записать матрицу переходных вероятностей и определить вероятнос­ ти состояний после двух бросаний игральной кости, если в началь­ ном состоянии человек сидит: а)на крайнем стуле; б)на среднем стуле. 5.12. Размеченный гра^ состояний системы 5 имеет вид, показанЯП ный на рис. 5 . 1 . с 0

• ^5 Рис. 5.1 Записать систему дифференциальных уравнений Колмогорова и началь­ ные условия для решения системы, если известно, что в начальный момент система находится в состоянии . 5.13. Физическая система 5 имеет возможные состояния: . ^2 « 5 з . ^4 • Размеренный граф состояний системы с ука­ занием численных значений интенсивностей перехода показан на рис. 5.2. 0^

2

^3

Рис. 5.2 Вычислить вероятности состояний в установившемся режиме. 44

5.14. 1раф ооотояниВ системы показан на рис.

5.3.

Рис. 5.3 Написать алгебраические уравнения для вероятностей состоявий в установившемся режиме. 5.15. Граф состояний системы имеет вид, приведенный яа рис. 5,4.

5в

^

Лаз

\ч

3>ъ

Р и с . 5.4 Написать алгебраические уравнения для вероятностей состояний в установившемся режиме и найти выражения для этих вероятностей. 5.16, Найти вероятности состояний в установивп-емся режиме для процесса гибели и размножения, граф которого показан на р и с . 5.5. 2

1 —^-». 'я

— 2

Рис, 5.5

§ 6.

Потоки случайных событий. Системы массового обслуживания 6 . 1 . Поток машин,, следующих по шоссе в одном направлении, прем ставляет со.^ой простр.1Аший поток с плотностью Л , Человек выхо• дит на шоссе, чтобы остановить первую попавшуюся машину, идущую в данном налоавлении. Найти закон распределения времени Т, кото­ рое ему придется адать; определить его математическое ожидание и среднее квадратическое отклонение 6^^ . 45

6.2. Тот же вопрос, что и в задаче 6 . 1 , но поток машин регуляр­ ный (машины следуют одна за другой через строго определенные кфомезсутки времени) , о той же Е ОТНООТЬЮ Л . 6.3. Пассажир выходит на автобусную остановку и ждет очередного автобуса. Автобусы подходят к остановке через случайные, взаимонезавнсимые и одинаково расщ)еделенные промежутки времени Т^г, Т 2 , . . . (Т^> О ) . Каждый из этих промежуткоь времени имеет одну и ту же плотность раохфеделения ^(-Ь) , Требуется найти закон распределения времени ожидания очередного автобуса при условии, что пассажир не знает расписания движения автобусов, что озна­ ч а е т , что выход пассажира на остановку автобуса некоррелироврч с моментом прибытия автобуса. 6.4. В условиях предыдущей задачи закон распределения промежутка между автобусами есть закон равномерпого распределения в интер­ вале от 5 до 10 микут6.5, В условиях задачи 6,3 найти закон распределения времени ожидания очередного автобуса, если поток автобусов ьредстаглявт собой поток Эрланга к-го порядка. 6»6, Поток отказов при работе ШВМ - простейший с интенсивностью X , а поток восстановлений тоже простейший с интенсивностью ^К , Определить вероятности состояний ЭЦВМ в установившемся |.зжиме работы. 6,7. Одноканальная СШ с отказами представляет собой одну телефо ную линию. Заявка- вызов, пришедший в момент, когда ^шния эаяша получает отказ. Интенсивность потока вызовов Л = 0,В (вызовов в минуту) . Средняя продолжительность разговора 1,5 мин. Все потоки событий - простейшие. Определить характеристики эффективности СМО в установившемся режиме работы: - относительную пропускную способность; - абсолютную пропускную способность; - вероятность отказа. 5.8. В одяоканальную СМО с отказами поступает простейшиД поток 46

заявок о иятенсявяоотью X = 0 , 8 (заявки в лшнуту"). Время обслу!ииваяия заявки имеет показательное распределение с 171^ = 3 мин. НалТВ: - вероятнооти ооотояний системы в неустановившемся режиме работы; - вероятность отказа в обслуживании при установившемся режиме работы СМО. 6.9. На диаиетчедский пункт легковых такси поступаэт простейший поток заявок с плотностью 1Я автомашин в ч а о . Определить чероятнооть того, что интервал между двумя последовательными заявками превзойдет его среднее значение. 6.10. Повторяются условия задачи 6.7 (Л ^ 0,8; - 1,5 мин.) , однако вместо одноканальной СШСЯв I ) рассматривается трехканальная(11= 3) , т . е . число линий связи увеличено до трех. Найти вероятности состояний в установившемся режиме, относитель­ ную и абсолютную пропускную способность, вероятность отказа и среднее число занятых каналов. 6.11. Рассматривается работа автоматической телефонной станции (АТС),, рассчитанной на одновременное обслуживание 20 абонентов (двадцатчканальная СМО) . Вызов на АТС поступает в среднем через 6 секунд. Каждый разговор длится в среднем 2 минуты* Если абонент застает АТС занятай, то оя по.тучает о т к а з . Если абонент застает свободным хотя бы один из 20 каналов, то он соединяется о нужным ему номером. Определить: вероятность обслуживания., Сфеднее число занятых каналов, вероятность занятости канала, среднее время простоя канала, 6,12. Автозаправочная станция (АЭС) прадставляет собой СМО с од­ ним каналом обслуживания (одной колонкой). Площадка при АЗС допускает щребывание в очереди на запраыог не более трех автомашин одновременно. Бели в очереди уже находится три машины, очередная мапшяа, пробывшая к станции,в очередь не становится, а Ефоезжает мимо. Поток машин, прибываиицгас для заправки, имеет интенсивность Л = I (машина в минуту) • Процесс заправки продол­ жается в среднем 1,25 минуты. Все потоки- простейшие.Определить: - вероятлостъ отказа в обслуживании;

- относительную - среднее число - среднее число мую; - среднее время - среднее время

и абсолютную пропускную способности СМО; машин, ожидающих заправки; машин, НЕГОДЯЩИХСЯ на АЗС, включая и обслуживае­ ожидания машины в очереди; пребывания машины яа АХ, включая и обспуживание.

6,13. На железнодорожную сортировочную горку прибывают составы с интенсивностью Л = 2 (состава в час) , Среднее время, в течение которого горка обслуживает состав, равно 0,4 часа. Составы, при­ бывающие в момент, когда горка занята, становятся в очередь и ожидают в парке прибытия, где имеется три запасных пути, на каж­ дом из которых может ожидать один состав. Состав, прибывший в мо­ мент, когда все три запасных пути в парке прибытия заняты, стано­ вится в очередь па внешний путь. Все потоки событий простейшие. Найти; - среднее число составов, ожидающих в очереди (как в парке при­ бытия, так и вне его) ; - среднее время ожидания состаша в парке прибытия и на внешних путях; - среднее время НЕ1Х0ждения состава на сортировочной станции, вклю­ чая ожидание и обслуживание; — вероятность т о г о , что прибывший состав займет место яа внешних путях. 6.14, Рассматривается работа АХ, на которой имеется Четыре зап­ равочных колонки. Заправка одной машины длится в среднем 3 мину­ ты, В среднем на АХ каждуэ минуту прибывает машина, нуждающаяся в заправке бензином. Число мест в очереди не ограничено. Все ма­ шины,, вставшие в очередь на заправ!^, дожидаются своей очереди. Определить среднее время, проходящее с момента прибытия машины на заправку, до момента ее эагфавки, а тешхе другие характерис­ тики работы АХ^ среднее число занятых заправкой колонок, сред­ нее число машин в очереди среднее время простоя колонки между заправками. 6.15. Имеется автомат по изготовлению деталей из заготовок. Если в автомате происходит сбой,, то он останавливается и ремонтирует­ с я . Поток сбоев простейший, а время ремонта распредглено по пока48

аательиону закону. Среднее времн безотказной работы и среднее время устранашш невсправноста автомата равны. Известно, что в начальный момент времена ^ О автомат исправен, а в момент в 6А 3 мин. вероятность нсоравности автомата равна 5/9. Найтя: — вероятность т о г о , что через; 10 минут работы автомат будет неисправен; - вероятность т о г о , что за 4 минуты не произойдет ни одного отказа. вЛ6, На станцию технического обслуживания автомашин каждые 2 часа подъезжает в среднем одна машина. Станция имеет несколько помещений, в каждом из которых может обслуживаться одна машина. Во дворе станции могут одновременно находиться, ожидая очереди, не более двух машин. Среднее время обслуживания одной машины— - 2 ч а с а . Поток подъезжающих машин - простейший. Определить: - число помещений для ремонта, если известно, что вероятность ожидания равна 7/23 ;. - минимальное число помещений, которое необходимо оборудовать, чтобы вероятность ожидания сократилась не менее, чем втрое - как изменятся при этом следутоще показатели эффективности работы станции: вероятность отказа в обслуживании, средняя дли­ на очереди, среднее число занятых помещений, среднее число машин на станции обслуживания. 6.17. На АЗС каждую минуту прибывает в среднем одна автомашина. Поток прибывающих машин можно считать простейшим. На станции установлено минимальное число колонок, при котором выход из строя одной из них еще не нарушает стационарности режима ра/боты станции. Среднее число занятых колонок при этом равно 2. Ощ)еделитъ: — число колонок на АЗС ; - среднее время заправки одной машины; - среднюю длину очереди; - среднее число машин на АЗС, находящихся в очереди и на заправ­ ке; - вероятность т о г о , что время ожидания начала захфавки будет лленьше I м-ь- '/ты; - число КОЛ' но'^, которое надо установить, чтобы вероятность ожи­ дания была ,.1е!ч пе 0,03 . 49

о . 1 8 . В столовой самообслуживания обеды выдают два повара. Число мест з а столами всегда достаточно для размещения лиц, уже получив­ ших обед. Среднее время обслуживания (выдачи обеда) одного посети­ теля - 4 минуты. Поток посетителей - простейший, в среднем з а 2 минуты прибывает один человек. Условия работы отоловоС таковы, что в очереди одновременно может стоять ограниченное число человек. Определить: - ограничение не длину очереди,, если вероятяость ожидания рсзаа 0,38 : — вероятность отказа в обслуживании, среднюю длину очереди и сред­ нее число занятых поваров при найденном ограничении на очередь ; - изменение показателей эффективности при увеличении времени обслуживания в 1,5 раза и увеличзнии числа поваров, выдающих обед, до 3-х .

§ 7. Графический метод решения задач линейного программированиа 7Л, Решить следующие задачи линейного тфограмыирования графичео КИМ методом: I) Из двух сортов бензина образуются для различн^ас цалей две сме­ си А и В. Смесь А содержит 60^ бензина 1нро сорта и 40^8 - 2-го сорта, смесь В - 80/2 - 1-го сорта и 205? - 2-го сорта. Продажная цена I кг. смеси А - Ю коп/ кг. и смеси В - 12 коп/ к г . Составить план образования смесей,, при котором будет получен м^лссимальный доход, если в наличии имеется 50 т.бензина 1нго сорта и 30 т . - 2го сорта. 2) При откорме каждое животное ежедневно должно получать не менее 9 единиц питательного вещества $1 , не менел 8 единиц питатель­ ного вещества 5 а ^ не менее 12 единиц питательного вещества $^ , Лля составления рациона используют два вида корма. Содер­ жание количества единиц питательных веществ в I к г . каждого вида корма и стоимость I к г . корма приведены в_табл, 7 , 1 ,

50

Таблица 7 Л Питательные вещества

81

Колич. ед» питательных веществ в I кг.корма Корм I Корм 2 3 I I 2 I 6

Стоимость I кг» корма в коп. 4 6 Составить дневной рацион нужной питательности, имеющий минималь­ ную стоимость. З) Звероферма выращивает черно- бурых тис и песцов. На зверофер­ ме имеется 10.000 клеток. В одной клетке могут жить либо 2 лисы, либо I песец. По плану на ферме ДОДАНО быть не менее 3000 лис и 6000 песцов. В одни сутки каждой л^-^е необходимо выдавать 4 еди­ ницы корма, а каждому песцу- 5 единиц. Ферма может иметь ежедневнс не более 200.000 единиц корма. От реализации одной шкурки лиси­ цы ферма подучает прибы.то в 10 р у б . , а от реализации одной шкуррси песца- 5 руб. Какое количество лисиц и песцов нужно держать на ферме,, чтобы получить наибольщую прибыль. \/-0 изготовления изделий А и В имеется 100 кг. металла. На изготовление одного изделия А расходуется 2 к г . металла, а изде­ лия В - 4 к г . Составить план производства, обеспечивающий получе­ ние наибольшей выручки от продажи изделий,, если отпускная стои­ мость одного изделия А установлена 3 р . , а изделия В - 2 р . , причем изделий А требуется изготовить не более 40, а изделий Вне более 20. / 5) Производстьинная мощность цеха сборки- 120 изделий типа А и 360 изделий типа В в сутки. Технический контроль пропускает 200 изделий того или другого типа безразлично . кхзделия типа А вчетверо дороже издели*^. типа В. Требуется спланировать выпуск готовой продукции т а к , чтобы предприятию была обеспечена наиболь­ шая прибыль. б) Для изготовления изделий А и В склад может отпустить металла не более 80 к г . , причем на изделие * расходуется 2 кг.,

а на 51

Изделие В - I к г , металла. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль,, если изделий А требуется изготовить не более 30 шт., а изделий В - не более 40 шт.,. причем одно изделие А стоит 5 р . , а В - 3 р . 7) В мастерской промартели освоили Гфоиэводство столов и тумбо­ чек для торговой сети. Для их изготовления имеется два вида д р е ­ весины: I и I I . Склад может отпустить древесины I не более 72 м^, древесины I I не более 56 м®. Для изготовления стола требуется 0 Д 8 м^ древесины I типа и 0,08 м^ древесины I I типа. Для и з г о ­ товления тумбочки требуется 0,09 м^ древесины I типа и 0,28 ьг^ древесины I I типа. От производства одного стола щромартель полу­ чает чистого дохода 1,1 р , , а от производства одной тумбочки0,7 р . Сколько столов и тумбочек должна гфоизводить промартель из имеющегося материала,, чтобы обеспечить наибольший доход. 8^) Организация планирует закупить несколько автомобилей двух марок А и В , Автомобиль марки А стоитЛйОО р . , а марки В - 10.200р. Известно, что в гараже может поместиться не более 20 новых ма­ шин, а на закупку машин ассигновано 150,000 р . Ожидаемая прибыль от эксплуатации одной машины марки А равна 2500 р . , а от эксплуа­ тации машины марки В - 3200 р . Какое количество автомобилей каж­ дой марки должна купить организация, чтобы общая прибыль от их эксплуатации была максимальной. 7^2. Решть графически следующие вания: I ) т а х 1 = х^ + 2x2 22 5X1 2 ^1 - 2X2 > с^ + 2X2 4 14 к^> о ; Х2> з)

52

т а х 1 = X, V- 2X2 *• - 2Хт х^ 4 г Х2 « I ч О ; О

задачи линейного программиро­ тах1< - 2x^ Зx^ - Х| Хх

2Хт + 3X2 ^ ^ + Х2 > 8 -»• ^ 8 + Х2 < Ю

таx^ » зx^ + Х2 ^1 * ^ < 2 ЗХ]^ + Х2 < 3 х ^ > О ; Х2>0

5)

2X1 ; 2X2 < 3 Х243 > - X I * 2X2 ^ ^ Ч * Х2>1 XI > С) ; Х2> 0 >

т1п1 « 3 X 1 - 2 X 2 ^1 + Х 2 4 1 •1^ 3X2 > 6 • •, ? ., •^! 3X1 - 2X2 < 0 1 1 2X1 - 3X2 > 0 0 ; Х2> 0

7)

> Н 2X1 * 5X2^10 ^1 * Х 2 > 1 ^1 * 10X24 5> , ^1 - 2X2 < 2 X I > 0 ; Х2> 0

8)

6)

•

10)

9) 2Х2> 2 2 X 1 - *2> 2 -Х1 + Х2>0 XI > 0 ; Х2> 0

, ; 1 ,

- X I -3X2 + Х2< I + 2X2 < I ^1 - 3X2 < 0 -3X1 + 2 Х 2 > - 3 XI > 0 ; Х2 > 0 т а х 1 - XI - 3X2 «I - Х 2 < I ^ > I 2X1 - Х 2 >/ I Ч > 0 ; Х2> 0

7.3« В оледущих задачах ощредвлггь графически область изменения параштра Р , в которой: - задача имеет единственное решение; - задача имеет бесчисленное множество решений;. - задача на имеет решения; - уоло&яя задача противоречиви* I ) та. I » РХ1 + 12 >2> ч> ^ 3) т{л1 > X XI -•• 2X2 4 ^2 < 2 2^1 Х2> Хт > О •

т й 1^ в XI - Рх2 - X I + Х2 < I 3^1» О ; Х2> 4) т^п^

РХ1 - Х 2 ЗХ2< 3 2X1 Х2 -8 ; XI - 2x3 > -12 ; 2X1 XI4

* ^3 "^^^ ' О ; Хд > О .

§, 9. Решение задач линейного програламирования сгашлекс- методом 9 . 1 . Цех выпускает трансформаторы двух видов, данные о которых помешены в т а б л . 9 . 1 . Вид трансфор­ матора I II

Расход сырья на один трансфор­ Прибыль от реализа­ ции одного трайоформатор в кг. натора в руб. Еелезо Проволока 3 5 1,2 2 3 1.0

получить максимальную прибыль^ еолй тх располагает 480 к г . желе­ за и 300 к г . проволоки. 9.2. Хозяйство располагает оледующими ресурсами:, площадь- 100 едиящ„ труд- 120 вдшшц, т я г а - 80 единиц. Хозяйство производи четыре вида продукщш! П1 , П2 , Пд , . Затраты ш производ­ ство едя вицы каадого вида щюдукшш я доход от их производства укаваны в табл. 9 ^ г . Таблица 9.2 Затраты на едини]цу продукции Доход от едини­ Продукция цы продукции Тяга Площадь Труд I 2 2 2 4 3 3 I 4 2 • I 3 ^3 4 I 5 5. мальнус прибыль* 9.5. В институте проводится конкурс на лучшую стенгазету. Одному из студентов дано следующее поручение. 55

I . купить акварельной щ>аохи по цена 30 к . , цветные варандашк по цене 20 к . , линейки но цене 12 к . , блокноты по дане Ю к. 2 . 1фасок нужно купить иа иенее 3-х коробок,, блокнотов - столь­ ко, сколько коробок карандашей и красок вместе, линеек — не более 5-ти. 3. На покупки можно израсходовать 3 рубля. В каком количестве студент должен купить указанные 1федмвты, чтобы общее число предметов было наибольшим. Э Л . Из трех продуктов 1^ 11,. Ш составляется омесь. В состав смеси должно войти не менее в едишд химического вещества А, не менее 8 единиц химического вещества В и не В1енее 12 единиц хими>' ческого вещества С. Содержание каждого химического вещества в единице каждого из продуктов приведено и табл. 9.3. Там же приве­ дена стоимость единицы каждого продукта. Таблица 9.3 Продукт

X П П1

Содержание химического вещества в единице продувста В А 2 I 3 I 1^

Стоимость едв- | ницн продукта I в рублям ; 2 3 2,5,

Составить наиболее дешевую смесь. 9.5, Решить табличным симплекс- методом задачи, приведенные к канонической формг 1)тсиг1= Х| - 2X2 •*" 2 % 3^X4; XI + Х2 • 2x3 + 2X4 = 8 ; 2X1 * 2 ^ * ^ * ^4 = XI - 2X2 + Хз + 2x4 = I XI >/ 0; 3)|»Н111 = 3x1 2x1 * 2x3 Хз XI + 2X2 У 56

+ 2x3 + Х3 + + ЗХ4 = • 2x3 + Х4 = + 2x3 + 2x4 0; ^ = 1 7 4 .

2 ) т а х 1 = 2x^ + V1 +^2 3 ^ , +^ 2X1 Ч^ 2X1 + 2X2 х^>0;

Хз + 1з + 2x4 ; Хз + 2x4 = 16; 2x3 • 2x3 * Хд = 4; = 174.

Х4; 4 ) т а а 1 = 3x1 + 2X2 * Хз + 2x4 9 ЗХ4 = 10 2X1 •*• 4 = 4 2x3 ^ х^ 8 XI + 2X2 + 2x3 + 2x4 у о; ^ = 1 Т 4 .

; 6)тах1=: 2X1 - Х2 + Зхд - 2X4 *1 ^ *2 ^ 2Хг^ х^ = 3 2X1 • Н * ^Ч * Н ' 2X1 + *2 *3 2x4 = 4 Х2 + 2X2 + *3 * °^ ^* ЗХ| + 3X2 + Хд + Зх^ = 15; XI + 2X2 ^ *4 = 5 x^> 0; ^ = 174. x^ >/ 0; ^ =г 174.

5)тах1в

+

+ ЗХ3 +

8)га(а1= XI +2x2 + ^3 + ^4 7)ш1 = 2X1 + Х2 + 2Хд + ; XI + Х2 - Хд + Х4 = 4 2X2 * ^ * 2Хд + х^ = 8; XI + 2X2 + Хд + 2X4 = 10; 2X1 *2 2*3 ~ *4 = 4 2X1 + Х2 + 2хд + 2X4 = 10; *1 - *2 + '^З * *4 = 2 x^ ^ 0; ^ = 174 : > 0; ^ = 174. 9)пюх1 = 4X1 + 2X2 + 2Хд + ; х^ + Х2 + Хд + 2x4 = 2x1 * Ч * Ч * 2*4 = х^ + Х2 + 2Хд - 2x4 ^ х^> 0; ^ «X 174. 11)тох1= XI + 2X2 ^*3 " *4 • XI 4- Х2 + Хд + х ^ в XI + 2X3 + Хд + 2X4 = XI + 2X2 •*• 2*3 + *4 = x^> 0; ^ = 174. 13)тах1= ЗХ1 -»• Х2 + 2хд + х^; XI + Х2 + 2X4 = 2X2 + 2Хд + Х4 = XI + Х2 + *3 + 2X4 = х ^ > 0; ^ = 1 7 4 .

10)т(1х1 XI + 2x2 + Зхд + 4x4 XI + Х2 - 2x3 + х^ = 8; XI - 2X2 + Хд + 2X4 = XI + 2X2 + 2X3 + 2X4 = 6; х^> 0; ^ = 174.

4; 6;

2 4 8

12)тах1 = XI - 2x2 * ^*3 '••^4 XI + Х2 + 2Хд + = 7 XI - 2X2 + ^3 * 2*4 = I 3X1 + *2 "*• ^*3 ••• 2*4 13 х^> 0; ^ = 174.

I4)таа^= 2X1 + Х2 + ЗХд + 2х, Х2 + 2Хд + 2X4 = 8 6; 7; 2X1 * 2*2 *3 *4 ~ ^ 7; 2*1 + ч- 2хо ^4 = б х ^ ^ 0; = 174.

15)тох1= 2X1 + Х2 ~ Хд + 2х^; XI + 2X2 - ^» Х2 + Хд + 2X4 = 6; XI + 2X2 + 2*3 = 10; х-,> 0; I = 174.

16)тах1 = XI + 2X2 ~ *3 ^ ^*' XI + 2X3 + 2x4 = 5 XI + Х2 + 2Хд = 4 2X2 + Хд =4 х : > 0; ^ = 174.

97

- 2X2 + 2X3 + Зх^ •дхЬ = X I * Ч - *?Хз + 2x4; 18^110» 1= + 2X4 = 4 5 Х4 = ^1 + Ч ч 3 Х2 + 2X3 + *4 = 6 + Хз 6 6 -.2X2 2х> Хг- + Хд + *4 = 0; ^ = 174. 0; = 174. ;)п1а11 = - 2x2 + Х3 -2X1 Ч * *4 = О =- 2 ч * ч = 12 2х^ - Х2 + 4x3 х^ ^ 0; ^ = 1,4. ^)|пи1 = 4X1 + 3X2 -3X2 Хз ^1 - 2 * 2 + ч ^1 0; \ = х^>

+ 2x3 + + * 4 ; 2 2 ) т а х Ь = х-^ ЗхI + 2X2 + х^ - '> 2ХI + 5X2 = 4 + х^ Зх^I + 4X2 = 3 174.

+ Х2 + 5X3 + 4x3 + 5x3 0; ^

-г + + + =

Хд Х4 = 22 Х4 = 24 14 = 26 174.

- 5X4 * *3 "* *4 ;2^т

Х2 + ЗХ3 - 2x4 + Х5 Хд = I = I *5 = 2 0; ^ = 1 7 5 .

Э.о. Репшть симплекс- методом следующие задачи линейного програло.о1рова1сия, представленгше в общем виде: I) тазе ^ = - 2x2 - ЗХ2 + 2X4 Зг^ ;. 2X1 - Хд + Хд 4 12 ; х^- + Х4 ^ 5 2X2 + 2X3 + Хд - 2X5^ 20 *1 " *2 - 2*3

2x4 - 2х^ 4 10 ;

-^Ху + 2X2 - 2Хд - 2x4 + х^ ;С 24 ; х ^ ^ 0; ^ = 175.

2)

Ь

= XI

Ч ^1 - 2 * 2 3X2 х^ >

З)

таг I

4)

ти I

=

*2 0;

*3 .-

- 3 2 4 5 3

- 2х^ - X. ^ = 175.

4x4 - З Х 5 ^ ч ч * Зхз - *4 + 2x5 < 10 -2X2 -Зх 4 + *5 » •- 6 3X2 + 4X2 + *3 + 2x4 + *& < 25 х ^ > 0; = 175. X - 1- 2X2 -

*5 • 2*2*32Хт + 2 x 3 - *4 * Х4 + *1 -2*2 Хр + Х2 -» *3 х^ > 0;. *4-

*5 > *5 »

§ 10. Чвойственныв и целочисленные задача линейного арограммирования 10.1. Решить следующие задачи линейного программирования,а такуге двойствэнные несимметричные к ним: таг

- Зх 5X2 Зх^ + + *3 + Х4 = 50 бх^ - 4X2 - Х3 + Х4 = 14 ^ x ^ > 0 ; ^ = ГГ4,

2) тох I = 2X1 - Х2 + "^*3 - 2X4 + Х5 ; -X *2 * *1 - *2 + * 4 = I 1 + *2 ^ = 2 0;. ^ = 175.

59

]С.^.. ?е!2ить следу^^щие задачи линейного програлширования, а так­ же двойственные оиквлтричные к ним: 1)тах1 = - бх^г - - 15. Хд; 2) ^40x1 = Х| - 2 Хд ; - XI + Х2 + ЗХд > 4 ; - 3 XI + 2x2 < 6 2X1 ^ ^ - ^ з ^ ^ ; X I - 4X2 ^ 2 X 1> 0;. /• = 173.. XI - Х2Ч5 ^ X | > 0;. ^ =

; ; ; 1.2.

10.3. При ро :онии задачи целочисленного программирования полу­ чена следуюдая симплекс- таблица (табл. 10.1) . Таблица 10.1 Базис базиса

2

^1 т

2 2 2

%

с 1 ЛИНе&10Й формы 2 2 'то Аз 0 I 0

1/2 3/2 5/2

0 0

ч -3/8 -1/8 -7/8

2

В

0 0 I

11/3 4/5 7/3

2^ - с^ Требуется: - зшюнчить составление симплекс- таблицы; - проверить опорный план на оптиг/альность; - ес;ш необходимо, то записать дополнительные ограничения по ме.тоду Гог.-.ори. 10.4. Ответить на вопросы предыдущей задачи применительно в с и г т е к с - таблице ( т а б л . 10.2). Таблица 10.2 Базис

^1 % ^2

^1 базиса

2

2 2 2

I 0 0

^^^^

с,- линейной формы 2 5 20 А? 0 0 I

Аз 0 I 0

ч 1/7 5А 3/2

2/3 9/4 7

0

3

В

ч . -11/8 -4/3 11/4 - Б / 9 -6/7 12/5 -3/4 -1/12 3

§ и . транспортная (алач-' 1 1 . 1 . В двух пунктах А я В находится соо'1 твенно 1Ы/ и т. горючего. Пункты 1,2,3 требуют соотввтотт^^внио Ш, 70„ ПО т . горючего. Стоимость перевозки одной гонны горючего из пункта А в пункты 1,2,3-6, 10, 4 р . за тонну, а из пункта В в пункты I . . 3 - 12, 2, в р . за тонну соответственна. Поставить план ие^т*-^ < горючего, миниглизирующи* общую сумму Т11анспо1.тных р;и.;хо,гь-н. 11.2, Три завода выпускают грузовые автомо>'?или, ко'юрые отпр^!!* ляются четырем потребителям, 1-й завод 1юставдяет ЭО платформ грузовиков, 11-й-ЗО платформ, П 1 - 40 Ш1ат(^рм. Лля потребите­ лей требуется! первому- 70 платформ, второму- 30, третьему- 20, четвертому- 40. Стоимость иеревозки одной.платформы между каж­ дым поставщиком и каждым потребителем указана в т а б л . 1 1 , 1 , Таблида 11,1 Поставщики I II Ш

I 18 10 16

Потребители 2 20 20 22

.3 14 4С 10

4 10 30 20

Состчвить план перевозок, обеспечивающий митмальяую стоимость транспортных расходов. I I .-3. Строительство магистральной дороги включает задачу чаю.ч ненил имеющихся на трассе выбоин до уровня основной до1Н1ги и срезания в некоторых местах дорох-и вьступов. Срезанным грунтом заполняются выбоины. Перевозка грунта осуществляется грузовика» одинаковой грузоподъемности. Р?1ео:' )чппе в км. от срезов до выбсин и объем работ указаны в табл. 11,2. Составить план цереро гру_кта, %!ин11миэир.ую!1пй количвстЕО километ- Таблица И . 2 1Я1бОИНН Требуемор кпли-торезы II Ш тво нтти Л I 160 3 В 2 50 .л. ^ -С Ц-.„. 90 юо 140

ров, проЦценяых грузовиками. ПЛ. Груз, хранящийся на трех складах и требунщий для перевозки 60,. 80 и 106 автомашин соответственно, необходимо перевезти в четыре магазина. Первому магазину требуется 44 машины груза, вто>~ рому - 70 машин,, третьемуг- 50 машин и четвертому - 62 машины. Стоимость пробега одной автомашины за I км. составляет 10 к. Расстояния между складами и магазиналз! указаны в т а б л . 11.3. Таблица 11.3 Склады I 2 3

.

I 13 г 12

Магазины 3 2 17 6 10 7 2 ^ 18

4 8 41 22

Составить оптимальный по стоимости план перевозки груза из скла­ дов в магазины, 11.5. На складах А,. В, С находится сортовое зерно соответственно в количестве 10,. 15, 25 т . , которое нужно доставить в четыре пункта^ Пункту I необходимо 5 т . , пункту 2 - 1.0 т . ^ пункту 3 - 20 т . и пункту 4 - 15 т . Стоимость доставки едкой тонны зерна со склада А в указанные пункты соответственно равна В, 3 , 5, 2 р . , со склада В - 4,. I , 6 , 7 р . , со скла'ха С - I , 9 , 4 , 3 р . Составить оптимальный план перевозки зерна из условад минимума стоимости перевозки. 11.6. Завод имеет три цеха А, В„ С и четыре склада !.:'1:сччое вр^-чя, в к.'\.л^чвсть!и 40, 50, ПО, 50 ед. При этом г-'ятраты г)! прО'1?]'.'.дс']'ВО е,плнш'.п продукции по прсщфиятиям соотявнльт .'11, ;(;, 35 ед, - при работе в урочное время и соответс:'гро«гю ю У.% ыпт при ум'-1С1[на ."ч'ч ь .ло'тор.'.оил четырем потребртелягл в ко.пичес' п ч / ;'^г , 250, КЧ' 11 ЙОО е.к, ог'отр^'тстиеипс. Тр=1Нс.порт1П!е радхо-

ды Су на перевозку единицы продукции от 1-го предприятия ( I = 1,4) ^ - му потребителю С^ = Т^А) заданы ?абл. 12.1. Таблица 12.1 Предприятш! I 2 3 4

I 25 30 25 42

Потребители 2 30 40 45 36

3 40 30 зс. 25

4 35 2С 34.

Определить оптимальную производственную программу предприятий и оптимальный план перевозок. Указание. 1фоме переменных x^^ для обозначения перевозок ввести переменные х [ , выражающие суммг'.рный выпуск продукции I - г о предприятия. 2) Определить мвото строительства зрвода между двумя пункта!ти сбыта, расстояние между которыми 100 км., и размер поставок в каждый из пунктов, если ралозый выпуск продукции завода состав­ ляет 150 е д . , а зависимость продажной цены единицы продукции от количества поставляемой продукции х^(1= 1,2) в каждый из пунктов сбыт" и затрат на перевозки едишхлы продукции от расстояния у^ между заводом и пунктом сбыта задается табл. 12^2. Таблица 12.2 П'^нкуы сбыта I 2

Продажная пена, руб./ед.

Затраты, руб./ед.

15 - 0,1 х^ 12 - 0,08 х.^

1,5 + 0,1 У! 1,5 + 0,05 У2

з) предприятие может выпускать три вида продукции А, Г и В, р а с ­ полагая для этого ресурсами сырья.в 1000 е д . , которое расходуетсь в ко;шчестве 5; 2,5 и 2 ед. соответственно на каждую единицу прох^юош А, Б и В- Прибыль, получаемая предприятием на каждую едашиог продукции, зависит от вида продукции и от общей величинырасходуем)лс на него ресурсов согласно данным табл. 12.3.

е,5

Расход реоурсрв

до 100

Прибыль

5

А 100-200

Шшт Х2.3 •••""••'•^

'

В 1 Б до 200 200^00 до 300 ;ЮС>-^00 1

3

6

10

4

^

1

Опредп.щть оптимальный план выпуска продущии. о) Определить оптимальную ярограмму выпуска двух видов продукции с уч§тш ограниченных ресурсов сырья (120 кг.) , оборудования (300 станко- часов) и электроэнергаи ( 2 8 0 к В т ч , ) при следущкх йормшс расхода на единицу продукции: сырья 3 и 2 к г , / е д , , электро-. экергви 4 и 7 кВтч, а оборудования 50 - Зх-^ и 20 - йХд, где Х| и Хо искомое число производимых эдишац 1-го и 2нго вида сродукщш,. 12,2, а области, оцределенной неравенствами х^ »• Зх^ ^ 12,^ Ху + ^ 9, Ху; ^ ^ ' ^ ^ иайти точки, в которых достигаютод ?м Р (Хд» - х| + 2 Х| Х2 + 4 *• 5) Ч) " ^1 - ^> ^ * 4 5 ^ 3 ^ ) « «

х| -

х| •: •

Шг^чШ «адашаой матрвщб зацвсат^>. квадратичную форцу ее

п

2 3 3 4 1 5

1 5 3

1 0 2 0 1 3 2 3 1

2)

12.6. По ааданноР квадратя'шой. |орме записать ее матрицу: I)

Р( X) « - Зх^ - 5 / 4 ^ - 6/4*3 + 2x7X2 -

ХдХ^ + 1/2x^X3 •

2) Р(Х) - 4 + 54 ' ^ * •* ^1 ^3 * З) Р(Х^ = * ''^ * + " ^*2% * 4) Р(Х1 « «1X2 + ЧЧ* ЧЧ • 12Л. Установить вид оледуюких квадрэ'-ичюа форм: I) Г(Х) »-2х| - :|-4а| + 2 Х1Х2 - ЗХ|Хз + 2X3X3 ; 2) Р(^) - 5х| • х| • Ц + 4x^X2 - 8X11^ - 4х^ ; 3) ИХЬ (XI-«2)2 • (Х2-Хд)2 ^ (,Ц-Ч^^ • 123. Найти все X г 01И которых квадра^й'^ям яшл^тся полсяЕительно определенной:

'

, 2) Р(Л = 2з^ • х| + а| 4- 2 Л Х|Л52 • 2Ж[Яз ^ 3) Р(Г,« х| + з^ + Ёз^^гЯ Х|^:1^ - 2х^}^ • 4*2%' 12 ..9. Подсчита.ь о главша шнсрои* в махрвдо Ц -1>о порд&ла. 12.10. Найт«{ точк.; локашкиго ккшмзгиа I) р (Х1гХ2> = х| + (-3 - 1)^ ; 2)

^Ч^г^

=Ч

-

ЧЧ

*

4 - ^ 1 ^ 4

5)

ь ( x ^ ,Х2 > = Х2Х2 + 5о/x^ + 20/Х2 ;

4)

Р Сx^,^С2) = х | + х | - х | - 2х^х^ - х |

; 67

12.11. Определить условные глобальные экстремумы функций с по­ мощью метода непосредственного искгочения и метода ь-ложителей Лагранжа: I")

Р Сх1гХ2) = Х | + з с 2

при

Хд- + Х2 = 1 ;

2) Р(Хд.,Х2) =3x^ + 23^-3x^ + 1 при х| + х| = 4 ; 3) Р *^1'*г'^^ ~ ЧЧ Хд-+Х2 = 2, X2^Xз = 2; 4) РСх^гХз) = (XI - 2)2 + - 3)2 при О ^ х^ < 5, О 4 Х2 < 10 при угловии