В обработку поступили две партии досок для изготовления комплектов из трех деталей
Обновлено: 03.07.2024
1.8. Формулы Байеса
Материал тесно связан с содержанием предыдущего параграфа. Пусть событие наступило в результате осуществления одной из гипотез . Как определить вероятность того, что имела место та или иная гипотеза?
При условии, что событие уже произошло, вероятности гипотез переоцениваются по формулам, которые в своё время предложил английский священник Томас Байес:
– вероятность того, что имела место гипотеза ;
– вероятность того, что имела место гипотеза ;
– вероятность того, что имела место гипотеза ;
…
– вероятность того, что имела место гипотеза .
На первый взгляд кажется полной нелепицей – зачем пересчитывать вероятности гипотез, если они и так известны? Но на самом деле разница есть:
– это априорные (оцененные до испытания) вероятности.
– это апостериорные (оцененные после испытания) вероятности тех же гипотез, пересчитанные в связи «со вновь открывшимися обстоятельствами » – с учётом того факта, что событие достоверно произошло.
Рассмотрим это различие на конкретном примере:
Задача 60
На склад поступило 2 партии изделий: первая – 4000 штук, вторая – 6000 штук. Средний процент нестандартных изделий в первой партии составляет 20%, а во второй – 10%. Наудачу взятое со склада изделие оказалось стандартным. Найти вероятность того, что оно: а) из первой партии, б) из второй партии.
Первая часть решения состоит в использовании формулы полной вероятности. Иными словами, вычисления проводятся в предположении, что испытание ещё не произведено и событие «изделие оказалось стандартным» пока не наступило.
Рассмотрим две гипотезы:
– наудачу взятое изделие будет из 1-й партии;
– наудачу взятое изделие будет из 2-й партии.
Всего: 4000 + 6000 = 10000 изделий на складе. По классическому определению:
.
Рассмотрим зависимое событие: – наудачу взятое со склада изделие будет стандартным.
В первой партии 100% – 20% = 80% стандартных изделий, поэтому: – вероятность того, что наудачу взятое на складе изделие будет стандартным при условии, что оно принадлежит 1-й партии.
Аналогично, во второй партии 100% – 10% = 90% стандартных изделий и – вероятность того, что наудачу взятое на складе изделие будет стандартным при условии, что оно принадлежит 2-й партии.
По формуле полной вероятности:
– вероятность того, что наудачу взятое на складе изделие будет стандартным.
Часть вторая. Пусть наудачу взятое со склада изделие оказалось стандартным. Эта фраза прямо прописана в условии, и она констатирует тот факт, что событие произошло. По формулам Байеса:
а) – вероятность того, что выбранное стандартное изделие принадлежит 1-й партии;
б) – вероятность того, что выбранное стандартное изделие принадлежит 2-й партии.
После переоценки гипотезы , разумеется, по-прежнему образуют полную группу:
(проверка ;-))
Ответ:
Понять смысл переоценки гипотез нам поможет Иван Васильевич, которой снова сменил профессию и стал директором завода. Он знает, что сегодня 1-й цех отгрузил на склад 4000, а 2-й цех – 6000 изделий, и приходит удостовериться в этом. Предположим, вся продукция однотипна и находится в одном контейнере. Естественно, Иван Васильевич подсчитал, что изделие, которое он сейчас извлечёт для проверки, с вероятностью выпущено первым цехом и с вероятностью – вторым.
Но после того как выбранное изделие оказывается стандартным, он восклицает: «Какой же классный болт! – его скорее выпустил 2-й цех». Таким образом, вероятность второй гипотезы переоценивается в лучшую сторону , а вероятность первой гипотезы занижается: . И эта переоценка небезосновательна – ведь 2-й цех произвёл не только больше изделий, но и работает в 2 раза лучше!
Вы скажете, чистый субъективизм? Отчасти – да, более того, сам Байес интерпретировал апостериорные вероятности как уровень доверия.
И, несмотря на то, что у байесовского подхода немало критиков, в нём есть и объективное зерно. Ведь вероятности того, что изделие будет стандартным (0,8 и 0,9 для 1-го и 2-го цехов соответственно) это предварительные (априорные) и средние оценки.
Но, выражаясь философски – всё течёт, всё меняется, и вероятности в том числе. Вполне возможно, что на момент исследования более успешный 2-й цех повысил процент выпуска стандартных изделий (и / или 1-й цех снизил), и если проверить бОльшее количество либо все 10 тысяч изделий на складе, то переоцененные значения окажутся гораздо ближе к истине.
Кстати, если Иван Васильевич извлечёт нестандартную деталь, то наоборот – он будет больше «подозревать» первый цех и меньше – второй. Предлагаю убедиться в этом самостоятельно:
Задача 61
На склад поступило 2 партии изделий: первая – 4000 штук, вторая – 6000 штук. Средний процент нестандартных изделий в первой партии 20%, во второй – 10%. Наудачу взятое со склада изделие оказалось нестандартным. Найти вероятность того, что оно: а) из первой партии, б) из второй партии.
Условие отличатся двумя буквами, которые я выделил жирным шрифтом. Задачу можно решить с «чистого листа», или воспользоваться результатами предыдущих вычислений. В образце я провёл полное решение, но чтобы не возникло формальной накладки с предыдущей задачей, событие «наудачу взятое со склада изделие будет нестандартным» обозначено через .
Байесовская схема переоценки вероятностей встречается повсеместно, причём её активно эксплуатируют и различного рода мошенники. Рассмотрим ставшее нарицательным АО на три буквы, которое привлекает вклады населения, якобы куда-то их инвестирует, исправно выплачивает 2% в день и т.д. Что происходит? Проходит день за днём, месяц за месяцем и всё новые и новые факты, донесённые путём рекламы и «сарафанным радио», только повышают уровень доверия к финансовой пирамиде (апостериорная байесовская переоценка в связи с произошедшими событиями!). То есть, в глазах вкладчиков происходит постоянное увеличение вероятности того, что «это серьёзная контора»; при этом вероятность противоположной гипотезы («это очередной лохотрон»), само собой, уменьшается и уменьшается. Дальнейшее, думаю, понятно. Примечательно, что заработанная репутация даёт организаторам время успешно скрыться от Ивана Васильевича, который остался не только без партии болтов, но и без штанов.
К не менее любопытным примерам мы вернёмся чуть позже, а пока на очереди, пожалуй, самый распространенный случай с тремя гипотезами:
Задача 62
Электролампы изготавливаются на трех заводах. 1-ый завод производит 30% общего количества ламп, 2-й – 55%, а 3-й – остальную часть. Продукция 1-го завода содержит 1% бракованных ламп, 2-го – 1,5%, 3-го – 2%. В магазин поступает продукция всех трех заводов. Купленная лампа оказалась с браком. Какова вероятность того, что она произведена 2-м заводом?
Заметьте, что в задачах на формулы Байеса в условии обязательно фигурирует некое произошедшее событие, в данном случае – покупка лампы.
Событий прибавилось, и решение удобнее оформить в «быстром» стиле.
Алгоритм точно такой же: на первом шаге находим вероятность того, что купленная лампа вообще окажется бракованной.
Пользуясь исходными данными, переводим проценты в вероятности:
– вероятности того, что лампа произведена 1-м, 2-м и 3-м заводами соответственно.
Контроль:
Аналогично:
– вероятности изготовления бракованной лампы для соответствующих заводов.
– вероятность того, что купленная лампа окажется с браком.
Шаг второй. Пусть купленная лампа оказалась бракованной (событие произошло)
По формуле Байеса:
– вероятность того, что купленная бракованная лампа изготовлена вторым заводом
Ответ: – отвечаем только на то, о чём спрашивалось в условии!
Почему изначальная вероятность 2-й гипотезы после переоценки увеличилась ? Ведь второй завод производит «средние» по качеству лампы (первый – лучше, третий – хуже). Так почему же возросла апостериорная вероятность, что бракованная лампа именно со 2-го завода? Это объясняется уже не «репутацией», а размером. Так как завод № 2 выпустил самое большое количество ламп (более половины), то логично субъективное завышение оценки по принципу «скорее всего, эта бракованная лампа именно оттуда».
Интересно заметить, что вероятности 1-й и 3-й гипотез, переоценились в ожидаемых направлениях и сравнялись:
Контроль: , что и требовалось проверить.
К слову, о заниженных и завышенных оценках:
Задача 63
В студенческой группе 3 человека имеют высокий уровень подготовки, 19 человек – средний и 3 – низкий. Вероятности успешной сдачи экзамена для данных студентов соответственно равны: 0,95; 0,7 и 0,4. Известно, что некоторый студент сдал экзамен. Какова вероятность того, что:
а) он был подготовлен очень хорошо;
б) был подготовлен средне;
в) был подготовлен плохо.
Проведите вычисления и проанализируйте результаты переоценки гипотез.
Предложенная задача приближена к реальности и особенно правдоподобна для группы студентов-заочников, где преподаватель практически не знает способностей того или иного студента. При этом результат может послужить причиной довольно-таки неожиданных последствий (особенно это касается экзаменов в 1-м семестре). Если плохо подготовленному студенту посчастливилось с билетом, то преподаватель с большой вероятностью сочтёт его хорошо успевающим или даже сильным студентом, что принесёт неплохие дивиденды в будущем (естественно, нужно «поднимать планку» и поддерживать свой имидж). Если же студент 7 дней и 7 ночей учил, «зубрил», повторял, но ему просто не повезло, то дальнейшие события могут развиваться в самом скверном ключе – с многочисленными пересдачами и балансировкой на грани «вылета».
Что и говорить, репутация – это важнейший капитал, не случайно многие корпорации носят имена-фамилии своих отцов-основателей, которые руководили делом 100-200 лет назад и прославились своей безупречной репутацией.
Да, байесовский подход в известной степени субъективен, но… так устроена жизнь!
Закрепим материал заключительным индустриальным примером, в котором я расскажу ещё об одном техническом приёме решения:
Задача 64
Три цеха завода производят однотипные детали, которые поступают на сборку в общий контейнер. Известно, что первый цех производит в 2 раза деталей, чем второй цех, и в 4 раза больше третьего цеха. В первом цехе брак составляет 12%, во втором – 8%, в третьем – 4%. Для контроля из контейнера берется одна деталь. Какова вероятность того, что она окажется бракованной? Какова вероятность того, что извлечённую бракованную деталь выпустил 3-й цех?
…таки Иван Васильевич снова на коне, должен же быть у фильма счастливый конец :)
Решение: в отличие от предыдущих задач здесь в явном виде задан вопрос, который разрешается с помощью формулы полной вероятности. Но с другой стороны, условие немного «зашифровано», и разгадать этот ребус нам поможет школьный навык составлять простейшие уравнения. За «икс» удобно принять наименьшее значение:
Пусть – доля деталей, выпускаемая третьим цехом.
По условию, первый цех производит в 4 раза больше третьего цеха, поэтому доля 1-го цеха составляет . Кроме того, первый цех производит изделий в 2 раза больше, чем второй цех, а значит, доля последнего: .
Составим и решим уравнение:
Таким образом: – вероятности того, что извлечённая из контейнера деталь выпущена 1-м, 2-м и 3-м цехами соответственно.
Контроль: . Кроме того, будет не лишним ещё раз посмотреть на фразу «Известно, что первый цех производит изделий в 2 раза больше второго цеха и в 4 раза больше третьего цеха» и убедиться, что полученные значения вероятностей действительно соответствуют этому условию.
За «икс» изначально можно было принять долю 1-го либо долю 2-го цеха – вероятности выйдёт такими же. Но, так или иначе, самый трудный участок пройден, и решение входит в накатанную колею:
Из условия находим:
– вероятности изготовления бракованной детали для соответствующих цехов.
– вероятность того, что наугад извлеченная из контейнера деталь окажется нестандартной.
Вопрос второй: какова вероятность того, что извлечённую бракованную деталь выпустил 3-й цех? Данный вопрос предполагает, что деталь уже извлечена, и она оказалось бракованной. Переоцениваем гипотезу по формуле Байеса:
– искомая вероятность. Совершенно ожидаемо – ведь третий цех производит не только самую малую долю деталей, но и лидирует по качеству!
Коль скоро в условии нет пунктов «а» и «бэ», то ответ лучше снабдить текстовыми комментариями:
Ответ: – вероятность того, что извлечённая из контейнера деталь окажется бракованной; – вероятность того, что извлечённую бракованную деталь выпустил 3-й цех.
Как видите, задачи на формулу полной вероятности и формулы Байеса достаточно простЫ, и, наверное, по этой причине в них так часто пытаются затруднить условие, о чём я уже упоминал в начале параграфа.
Полную и свежую версию этой книги в pdf-формате ,
а также курсы по другим темам можно найти здесь.
Также вы можете изучить эту тему подробнее – просто, доступно, весело и бесплатно!
Минимизация отходов лесопилки
Содержимое работы - 1 файл
ильн.doc
х1.1*100000+х2.1*400000+х3.1* 20000+х4.1*200000+х5.1*600000 = р
Производственная мощность одного предприятия
13. Как распилить доски
В обработку поступили две партии досок для изготовления комплектов из трех деталей, причем первая партия содержит 50 досок длиной по 6,5 м каждая, вторая содержит 200 досок длиной по 4 м каждая. Каждый комплект состоит из двух деталей по 2 м и одной детали длиной 1,25 м.
Как распилить доски, чтобы получить возможно большее число комплектов?
Х1 – из 6.5(3 по 2 м)
Х2 – из 6.5(2 по 2 м и 2 по 1.25м)
Х3 - из 6.5(5 по 1.25м)
Х4 - из 6.5(1 по 2 м и 3 по 1.25м)
В обработку поступили две партии досок для изготовления комплектов из трех деталей
(300х +400у) ч — время обработки всех изделий на токарных станках:
Учитывая, что фрезерные станки используются максимально, имеем:
200х +100у = 3400
Итак, система ограничений этой задачи есть:
200х + 100у = 3400
Общая прибыль фабрики может быть выражена целевой функцией
Выразим у через x из уравнения 200х + 100у = 3400 и подставим полученное выражение вместо у в неравенства и целевую функцию:
Преобразуем систему ограничений (3):
у =34 - 2х у = 34 — 2х
Очевидно, что F =272 -3х принимает наибольшее значение, если х=16.
Отдельно следует остановиться на случаях использования ЭВМ при решении задач оптимизации. Рассмотрим это на примере решения следующей задачи:
ЧАСТЬ 10 МЕТОДЫ ОПТИМИЗАЦИИ
1. Методом множителей Лагранжа найдите условный экстремум функции , если дано уравнение связи .
2. Составьте математическую модель задачи.
В обработку поступили две партии досок для изготовления комплектов из трех деталей, причем первая партия содержит 50 досок длиной по 6,5 м каждая, вторая содержит 200 досок длиной по 4 м каждая. Комплект состоит из двух деталей по 2 м каждая и одной детали длиной 1,5 м. Как распилить все доски, чтобы получить наибольшее число комплектов?
3. Решите графически задачу: найдите экстремумы функции , если , .
4. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
5. Решите задачу линейного программирования
6. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
7. Найдите решение матричной игры с матрицей .
8. Пусть имеется 5 сотрудников фирмы, которых необходимо распределить для выполнения четырех работ. Известны стоимости назначения каждого из сотрудников на каждую работу. На какую работу следует назначить сотрудников для достижения наименьшей суммарной стоимости?
1. Методом множителей Лагранжа найдите условный экстремум функции , если дано уравнение связи .
2. Составьте математическую модель задачи.
Фирма производит одежду для охотников, туристов и охранных структур. Дополнительно фирма решила изготавливать шапки и подстежки из натурального меха. Затраты на производство этих изделий и запасы сырья представлены в таблице. Спрос на шапки составляет не более 600 шт. в месяц, а подстежек – не более 400 шт. в месяц.
на производство, дм
Оптовая цена, руб./шт.
Определить объемы производства этих изделий, обеспечивающих максимальный доход от продажи.
3. Решите графически задачу: найдите экстремумы функции , если , .
4. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
5. Решите задачу линейного программирования
6. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
7. Найдите решение матричной игры с матрицей .
8. В распоряжении некоторой компании имеется 5 торговых точек и 5 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Объемы продаж каждого продавца в каждой торговой точке даны в таблице. Как следует назначить продавцов по торговым точкам, чтобы достичь максимального объема продаж?
1. Методом множителей Лагранжа найдите условный экстремум функции , если дано уравнение связи .
2. Составьте математическую модель задачи.
Имеется два станка, на которых могут обрабатываться детали трёх видов. Количество деталей каждого вида, обрабатываемых на каждом станке в течение рабочего дня, приведено в таблице.
Полный комплект состоит из двух деталей первого вида, одной детали второго вида и четырёх деталей третьего вида. Какую часть рабочего дня каждый станок должен обрабатывать детали каждого вида с тем, чтобы число комплектов деталей было наибольшим?
3. Решите графически задачу: найдите экстремумы функции , если , .
4. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
5. Решите задачу линейного программирования
6. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
7. Найдите решение матричной игры с матрицей .
8. Диспетчер транспортного предприятия распределяет 5 водителей по 5 автомобилям различного назначения на ближайшую смену. Известны эффективности назначения водителей на автомобили (см. таблицу). Как распределить водителей для получения наибольшей эффективности?
1. Методом множителей Лагранжа найдите условный экстремум функции , если дано уравнение связи .
2. Составьте математическую модель задачи.
Имеются три экскаватора разных марок. С их помощью нужно выполнить три вида земляных работ объёмом в 20 000 м 3 каждый. Время работы экскаваторов одинаково, производительность в м 3 /ч по каждому виду работ приведено в таблице.
Распределить время работы каждого экскаватора так, чтобы задание было выполнено в кратчайший срок.
3. Решите графически задачу: найдите экстремумы функции , если , .
4. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
5. Решите задачу линейного программирования
6. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
7. Найдите решение матричной игры с матрицей .
8. Транспортное предприятие нанимает 4 водителя на четыре из пяти имеющихся у него автомобиля. Известны расходы предприятия при назначении каждого из водителей на каждый автомобиль (см. таблицу). Как распределить водителей для минимизации расходов предприятия?
1. Методом множителей Лагранжа найдите условный экстремум функции , если дано уравнение связи .
2. Составьте математическую модель задачи.
Планируется установление договорных связей между тремя совхозами и тремя торговыми предприятиями по поставке овощей. Заказы торговых предприятий на плановый период и возможности поставщиков, а также расстояния (в км) приведены в таблице.
Определить схему связей, соответствующую минимальному грузообороту (произведение массы перевозимого груза на расстояние перевозки).
3. Решите графически задачу: найдите экстремумы функции , если , .
4. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
5. Решите задачу линейного программирования
6. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
7. Найдите решение матричной игры с матрицей .
8. Диспетчер транспортного предприятия распределяет 5 водителей по 5 автомобилям различного назначения на ближайшую смену. Известны эффективности назначения водителей на автомобили (см. таблицу). Как распределить водителей для получения наибольшей эффективности?
1. Методом множителей Лагранжа найдите условный экстремум функции , если дано уравнение связи .
2. Составьте математическую модель задачи.
Предприятие по переработке лесоматериалов выпускает пиломатериалы и фанеру. Для изготовления 8 м 3 пиломатериалов расходуется 6 м 3 еловых и 13 м 3 пихтовых лесоматериалов. Для производства 100 м 3 фанеры расходуется 6 м 3 еловых и 10 м 3 пихтовых лесоматериалов. Общие запасы сырья – 80 м 3 еловых и 200 м 3 пихтовых лесоматериалов. В соответствии с плановым заданием предприятие должно изготовить не менее 10 м 3 пиломатериалов и 1 100 м 3 фанеры. Прибыль, получаемая от реализации 1 м 3 пиломатериалов – 12 руб., а при реализации 100 м 3 фанеры – 50 руб. Составить план производства, максимизирующий прибыль.
3. Решите графически задачу: найдите экстремумы функции , если , .
4. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
5. Решите задачу линейного программирования
6. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
7. Найдите решение матричной игры с матрицей .
8. Продавец хочет продать 5 подержанных автомобилей. Пять человек предложили цены на каждый из автомобилей (см. таблицу). При каком варианте распределения автомобилей выручка продавца будет наименьшей?
Задача 1
2.1. Организация изготавливает из бруса деревянные оконные блоки. Ставится задача поиска рационального варианта раскроя бруса длиной 700 мм на элементы длиной мм, мм, мм (отходами на разгрузку, распил и т.п. можно пренебречь). Производственная программа по элементам 1-го вида 1200 шт., 2-го вида - 8000 шт., 3-го вида - 750 шт.
2.2. В обработку поступили две партии досок для изготовления комплектов из трех деталей (треугольные каркасы настилов на стройплощадку), причем первая партия содержит 52 доски длиной по 6,5 м каждая, вторая содержит 200 досок длиной по 4 м каждая. Каждый комплект состоит из двух деталей по 2 м каждая и одной детали в 1,25 м.
Ставится задача поиска рационального варианта раскроя поступившего в обработку материала.
^ Задача о смеси
2.3. Металлургическому заводу требуется уголь с содержанием фосфора не более 0,03% и с долей зольных примесей не более 3,25%. Завод закупает три сорта угля А, В, С с известным содержанием примесей. В какой пропорции нужно смешивать исходные продукты А, В, С, чтобы смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену? Содержание примесей и цена исходных продуктов приведены в таблице
2.4. Стандартом предусмотрено, что октановое число автомобильного бензина А-76 должно быть не ниже 76, а содержание серы в нем – не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице
Компонент автомобильного бензина
Октановое число
Содержание серы,%
Ресурсы, т
Себестоимость, ден.ед./т
Требуется определить, сколько тонн каждого компонента следует использовать для получения 1000т автомобильного бензина А-76, чтобы его себестоимость была минимальной.
^ Задача о рационе
В таблице приведены данные, характеризующие содержание (по весу) питательных веществ к каждом из ингредиентов и удельную стоимость каждого ингредиента
Смесь должна содержать (от общего веса смеси):
не менее 0, 8% кальция;
не менее 22% белка;
не более 5% клетчатки.
Требуется определить количество (в кг) каждого из трёх ингредиентов, образующих смесь минимальной стоимости, при соблюдении требований к общему расходу кормовой смеси и её питательности.
Выбор оптимальных проектов для финансирования
2.6. Управляющему банка были представлены 4 проекта, претендующие на получение кредита в банке. Ресурс банка в каждый период, потребности проектов и прибыль по ним приведены в таблице (тыс. долл.).
При выборе проектов следует принять во внимание потребность проектов в объёмах кредитов и ресурс банка для соответствующих периодов.
Какие проекты следует финансировать, если цель состоит в том, чтобы максимизировать прибыль?
Задача о водопроводчике
Водопроводчик получил наряд на установку вентилей на нескольких трубах, проложенных под землей, покрытой тяжелыми квадратными плитами (рис. 1.3). Он может установить механизмы перекрытия в любом месте трубы, но, разумеется, лишь по одному шлюзовому затвору на каждой трубе. Для минимизации трудозатрат водопроводчику надо определить минимальное число плит, которые требуется приподнять, чтобы установить по одному затвору на каждой трубе.
Пронумеруем плиты от 1 до 12. Пусть x i = 0, если выбранное решение состоит в том, чтобы не приподнимать i - ю плиту, x i = 1, если принимается решение приподнять i - ю плиту ( ). Каждой трубе соответствует одно ограничение, которое означает, что для получения к ней доступа необходимо приподнять, по крайней мере, одну из плит.
Математическая модель задачи выглядит следующим образом:
при условиях: . (1.74)
Эта задача попадает в класс так называемых задач о «покрытии множества», для которого характерны разнообразные практические приложения.
Пример 1.11. Стохастические модели
Задача о загрузке судна запасными деталями
Пусть рассматривается три типа запасных деталей, имеющих объемы 1, 2, и 2 единицы. Общий объем склада равен 10 единицам. Штрафные затраты j , возникающие при неудовлетворении потребности, равны соответствен-но 800, 600, и 1300. Будем предполагать, что спрос j на каждую из запасных деталей подчинен пуассоновскому распределению со средними значениями j = (4; 2; 1). Соответственно требуется определить, каким должен быть запас деталей каждого типа, чтобы средние штрафные издержки были минимальными. В математической формулировке мы приходим к следующей модели:
при условиях: xj 0, целые, j = 1, 2, 3;
x1 + 2x2 + 2x3 10,
где xj – запасы деталей j-го типа.
в функции (1.75) представляет собой вероятность случайной величины j, подчиненной закону Пуассона, а j есть ожидаемая средняя потребность в деталях j -го типа: .
Из (1.76) следует, что
Таким образом, можно записать:
Соотношение (1.78) дает возможность без труда вычислить средний спрос на j -ю деталь, возникающий в то время, когда запас их исчерпан, пользуясь таблицами для распределения Пуассона.
Диспетчерская служба имеет следующие минимальные потребности в количестве диспетчеров в различное время суток (табл. 1.6):
Время суток час.
Минимальное число диспетчеров, требуемое
в указанный период
При этом нужно иметь в виду, что период 1 следует сразу же за периодом 6. Каждый диспетчер ежедневно приступает к работе в начале определенного периода и работает восемь часов без перерыва. Требуется составить расписание на каждые сутки таким образом, чтобы обойтись минимальным числом диспетчеров, не нарушая, при этом, сформулированных выше требований.
В обработку поступили две партии досок для изготовления комплектов из трех деталей, причем первая партия содержит 50 досок длиной по 6,5 м, вторая содержит 200 досок длиной 4 м. Каждый комплект состоит из двух деталей по 2 м каждая и одной детали по 1,25 м. Как распилить доски, чтобы получить наибольшее число комплектов?
На заводе предстоит решить, какое количество х1 чистой стали и какое количество х2 металлолома следует использовать для приготовления (из соответствующего сплава) литья для одного из своих заказчиков. Пусть производственные затраты на 1 т стали составляют 3 усл. ед., а затраты на 1 т металлолома 5 усл. ед. (последняя цифра больше предыдущей, т.к. использование металлолома связано с его предварительной очисткой).
Заказ предусматривает поставку не менее 5 т литья. Предположим, что предназначенные для литья запасы чистой стали составляют 4 т, а металлолома – 6 т. Отношение веса металлолома к весу чистой стали в сплаве не должно превышать 7/8.
Производственно-технологические условия таковы, что на процессы плавки и литья может быть отведено не более 18 час., при этом на 1 т стали затрачивается от 2,5 до 3 час., а на 1т металлолома от 1,5 до 2 час.
Цель завода – выполнить заказ с минимальными производственными затратами.
Предприятие выпускает радиоприемники трех различных моделей: модель А, модель В и модель С. Каждое изделие указанных моделей приносит доход в размере 8, 15, 25 единиц стоимости соответственно. Необходимо, чтобы фирма выпускала не менее 100 приемников модели А, 150 приемников модели В и 75 приемников модели С.
Каждая модель характеризуется определенным временем, необходимым для изготовления соответствующих деталей, сборки изделия и его упаковки. Так, в частности, в расчете на 10 приемников модели А требуется 3 ч. для изготовления соответствующих деталей, 4 ч. на сборку и 1 ч. на упаковку. Соответствующие показатели на 10 приемников модели В равняются 3; 5, 5 и 1,5 ч., а на 10 приемников модели С – 5, 8 и 3.
В течение ближайшей недели фирма может израсходовать на производство – 150 ч., на сборку – 200 ч. и на упаковку – 60 ч.
Составить производственный план.
На предприятии требуется произвести раскрой рулона материала шириной 60 см. Мастер сообщил следующие данные о заказах текущей недели:
4. Задача оптимизации производственной программы
Технологический процесс состоит из двух этапов. На первом этапе поступающее сырье перерабатывается в три промежуточных продукта, которые на втором этапе используются для изготовления требуемой конечной продукции.
Выход промежуточных продуктов из одной тонны сырья и расход этих продуктов на производство одной тонны конечной продукции каждого вида указаны в табл.6.3. При этом оптовая цена тонны конечной продукции первого вида - 50 руб, а второго - 60 руб.
Определить производственную программу выпуска, при которой максимизируется цена выпускаемой продукции.
Промежуточный
Выход из 1 т сырья, кг
Расход на 1 т конечного продукта, кг
5. Задача о назначениях
Имеются три бригады А1, А2, А3 , каждая из которых может быть использована на каждом из трех видов работ с производительностью (в условных единицах), заданной в виде табл.6.5:
Производительность по видам работ, у.е.
Требуется так распределить бригады по одной на каждую из работ, чтобы суммарная производительность всех бригад была максимальной.
6. Задача о получении максимальной прибыли
Имеются два изделия А и В, которые должны в процессе производства пройти обработку на четырех станках: 1, 2, 3, 4. Время обработки каждого изделия на каждом из этих станков задается табл.6.5.
Время обработки изделия на станке, ч
Станки 1, 2, 3 и 4 можно использовать соответственно в течение 45,100,300 и 50 часов. Продажная цена изделия А – 6 руб. за единицу, а изделия В – 4 руб.
В каком соотношении следует производить изделия А и В, чтобы получить максимальную прибыль? Решить задачу в предположении, что изделий А требуется не менее 20 штук.
7. Задача об оптимальном раскрое материалов
В обработку поступили две партии досок для изготовления комплектов из трех деталей, причем первая партия содержит 50 досок длиной по 6,5 м каждая, вторая содержит 200 досок по 4 м каждая. Каждый комплект состоит из двух деталей по 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 м.
Как распилить все доски, чтобы получить возможно большее число комплектов?
Вариант 17
Совхоз отвел три земельных массива размерами в 5 000, 8 000, 9 000 га под посевы ржи, пшеницы и кукурузы. Средняя урожайность (в ц на 1 га) по массивам указана в таблице:
За 1 ц ржи совхоз получает 20 т.руб., за 1 ц пшеницы – 25 т.руб., за 1 ц кукурузы – 14 т.руб. Сколько гектаров и на каких массивах совхоз должен отвести под каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1 900 т ржи, 15 800 т пшеницы и 30 000 т кукурузы?
2. Решите графически задачу: найдите экстремумы функции , если , .
3. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
4. Решите задачу линейного программирования
5. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
6. Найдите решение матричной игры с матрицей .
Вариант 18
1. Составьте математическую модель задачи.
Для нарезки заготовок длиной 20, 25 и 30 см используются прутки длиной 75 см. Требуется за смену нарезать следующее количество заготовок: длиной 20 см – 300 шт., 25 см – 270 шт., 30 см – 350 шт. Из одного прутка можно нарезать заготовки различной длины. Требуется определить, какое количество прутков необходимо разрезать каждым из возможных вариантов, чтобы число заготовок соответствовало заданной программе, и чтобы при этом общая длина всех концевых остатков была минимальной?
2. Решите графически задачу: найдите экстремумы функции , если , .
3. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
4. Решите задачу линейного программирования
5. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
6. Найдите решение матричной игры с матрицей .
Вариант 19
1. Составьте математическую модель задачи.
В обработку поступили две партии досок для изготовления комплектов из трех деталей, причем первая партия содержит 50 досок длиной по 6,5 м каждая, вторая содержит 200 досок длиной по 4 м каждая. Комплект состоит из двух деталей по 2 м каждая и одной детали длиной 1,5 м. Как распилить все доски, чтобы получить наибольшее число комплектов?
2. Решите графически задачу: найдите экстремумы функции , если , .
3. Дана задача линейного программирования
а) Найдите все базисные решения системы ограничений. Выберите из них допустимые.
б) Решите данную задачу графически.
в) Решите данную задачу методом искусственного базиса.
4. Решите задачу линейного программирования
5. Решите методом потенциалов транспортную задачу, где – цена перевозки единицы груза из пункта в пункт .
Читайте также: