Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Пример 1.2.






Шаг 1. Постановка задачи. Вы стали обладателем 27 одинаковых по размеру и внешнему виду бриллиантов. В сертификате указано, что один из них весит на незначительную величину меньше, чем остальные. Вес камней неизвестен. Желая отбраковать неполноценный камень, Вы попросили ювелира произвести взвешивание бриллиантов. Каждое определение веса на высокоточных весах стоит 100 рублей. Требуется минимизировать затраты на данную процедуру.

Приступим к процедуре расчета:
Шаг 1. Экономический смысл задачи – найти фальшивый бриллиант с минимальными расходами на взвешивание. Отсюда цель операции: определение минимального числа взвешиваний, достаточного для выявления подделки.

Число взвешиваний связано как с количеством исследуемых бриллиантов, так и с порядком разделения их на части для поочередного взвешивания. Поскольку мы имеем дело с чашечными весами, взвешивание должно производиться путем раскладки различных количеств по чашкам весов. Если при равных количествах камней на обеих чашах весы уравновешиваются, значит, подделка находится среди тех камней, которые исключены из взвешивания. Если же груз на одной из чашек оказался легче, чем на другой, значит, там и находится фальшивый камень. Самый простой способ поиска – уложить на одну чашу какой-нибудь из камней, а на другую поочередно класть остальные 26 бриллиантов. Это потребует максимального числа взвешиваний – 26-ти.

 

Нас, однако, интересует не максимум, а минимум. Поэтому такой перебор (его в исследовании операции называют сплошным или «слепым») нас явно не устраивает. Следует искать способ более рационального выбора, ведущего к уменьшению количества взвешиваний. Таким образом, достижение поставленной цели зависит от выбора такого разделения камней при взвешивании, при котором количество взвешиваний окажется минимальным. Основным показателем, от которого зависит достижение поставленной цели, является минимум количества взвешиваний, приводящей к решению задачи – определению подделки с минимальными расходами.

Математическая модель задачи должна связать минимальное количество взвешиваний с общим количеством камней и количеством камней в каждой группе при их разделении.

Подобная модель может быть построена с помощью одного из методов оптимизации – линейного программирования, устанавливающего правила направленного, т.е. рационального, перебора вариантов.

В данной задаче суть направленного перебора в том, что если разделить камни на три одинаковые части так, чтобы 2 части содержали одинаковое количество камней, а третья оставшиеся и с одинаковым количеством две из них разложить по чашкам весов, то всего за одно взвешивание можно определить, в какой из трех частей находится фальшивый бриллиант. Затем та часть, где обнаружена подделка, снова делится на три части, снова производится взвешивание, и так до тех пор, пока в последней тройке не окажется три камня или меньше. Теперь уже взвешивание однозначно укажет на то, какой камень поддельный. Такой направленный перебор резко сократит необходимое количество взвешиваний. В данном примере их потребуется произвести всего три.

Шаг 2.

2.1. Обозначим через х – число взвешиваний – управляемая переменная.

Все остальные переменные: число камней, стоимость одного взвешивания и т.д. – неуправляемые переменные.

 

2.2 Цель операции – минимизация расходов на взвешивание, следовательно,

стоимость x взвешиваний- f(x)=100 x → min (1.4.)

2.3. Построение ограничений. Для решения задачи в общем виде обозначим через N – число взвешиваемых предметов (в примере N=27).

Согласно постановке задачи, если , то очевидно, что число взвешиваний x=k, т.е. ограничение имеет вид:

(1.5.),

x =1, 2, …- целое (1.6.)

Если - ; > 0, (например 80= ),

то представим N в виде 3 слагаемых:

и следовательно ограничение будет иметь вид:

< , (1.5.’)

Окончательно модель данной задачи имеет вид:

f(x) = 100x→ min (1.5.),

(1.6.)

x =1, 2, …- целое

Шаг 3. Решение модели.

Шаги 4, 5, 6. Например, при N=27, , т.е. минимальное количество взвешиваний равно 3 и стоимость 3 взвешиваний равна 300 рублям.

Если N=50, то х > , 56, т.е. х=4.

Действительно:

1 взвешивание: 50=27+27+27-1=27+27+26, если вес 1-й и 2-й части разный, то фальшивый бриллиант находится в меньшей по весу кучке, т.е. дальше необходимо 3 взвешивания (), т.е. общее число взвешивания равно 4. В противоположном случае, фальшивый бриллиант находится среди 26 не взвешенных камней.

2 взвешивание: 26=9+9+8, если фальшивый бриллиант находится среди 9 камней, то для его определения понадобится еще 2 взвешивания, т.е. общее

 

число взвешиваний опять равно 4. Если фальшивый бриллиант находится среди 8 камней, то переходим к 3 взвешиванию.

3 взвешивание: 8=3+3+2, рассуждая аналогично, убеждаемся, что в любом случае число взвешиваний равно 4, что и подтверждает адекватность построенной модели.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.