С17 Оптимизация целочисленной последовательности

С17 Задачи на оптимальный выбор

Примеры задач целочисленной оптимизации

Максимум дискретной последоватедьности

1а)Г- владелец 2 заводов в разных гор. На заводах производят одинаковые товары, но на з-де, во 2м городе, используют более совершенное оборудование. если рабочие на заводе, в 1гор, трудятся сумм   час в неделю, то за эту неделю они произведут  3t ед товара; если раб на зав, во 2 гор, трудятся суммарно   час в нед, то за эту неделю они производят 4t  ед товара. За каждый час работы (на каждом из заводов) Г платит раб 500 р,. Г готов выделить 5 000 000 р в неделю на оплату труда рабочих. Какое наибольшее количество единиц товара можно произвести за неделю на этих 2 заводах? 

Пусть раб на 1 заводе трудились  час, тогда они произ 3x ед товара. а раб на 2 заводе труд ились часов, тогда они произвели 4y ед товара. Получим

при

1сп)

Где max при

2сп )

1б)Фирма владеет 2 заводами в разных городах На заводах одинаковые товары и технологии. Если рабочие трудятся суммарно   час в нед то за эту неделю производят t-ед товара За каждый час работы на 1 зав платят 400р в 1 гор и 500р во 2 гор. На оплату труда выделено 1 890 000 р и все деньги д б выплачены. Какое мах кол товара м б выпущено? Ответ 105

Реш Пусть раб на 1 зав трудились  час, произвели х ед товара а на 2 зав - час и произвели

У ед.,тогда при или

1сп) ) или

где мах при

ищем целое реш. Замена перем

перебором нах

4). На участке н провести водопровод длиной 167 м. есть трубы длиной 5 м и 7 м. Сколько брать тех и других труб, чтобы сделать наи кол соед (трубы не резать)?

Реш:, кол 7м труб обозн х, а 5–м – у. Тогда 7х – длина 7-м труб, 5у – длина 5-м труб.

получ неопр ур 7х + 5у = 167 кот н реш в целых числах. Выр, напр, у через х, получ Т к х, у Є Z, то методом перебора легко найти пары зн х и у, кот удов урав 7х + 5у = 167. Если то х не явл целым числом.

Если 2х – 2 =0, то х = 1, у =32. Если 2х – 2 =10, то х =6, у = 25.

Если 2х – 2 =20, то х = 11, у = 18. Если 2х – 2 =30, то х = 16, у = 11.

Если 2х – 2 =40, то х = 21, у = 4. Если 2х – 2 =50, то х = 26 и 7 ∙26 = 182 167.

полу пары решений: (1; 32), (6; 25), (11; 18), (16; 11), (21; 4).Из этих реш наиб выг последнее, т.е. х = 21, у = 4. Вывод: Надо взять 21 трубу длиной по 7 м и 4 трубы длиной по 5 м.

Тип задач на продажу ценных бумаг и наибольшей прибыли в конце периода

 Общий вид таких задач стоимость ценных бумаг к концу i-периода описывается функцией (в реальных задачах ЕГЭ 2 типа : и ). В какой-то момент k бумаги продаются ,деньги кладутся в банк под дивиденты p за период, 2 типа формулировок:

1)по известным и процентной ставке p надо получить максимальный доход к концу n-периода – рассчитать моемент продажи бумаг

2) по известным и моменту к продажи найти неизвестную процентную ставку p (как правило, ответ получается в виде интервала )

Рассмотрим общий подход

А) Если продажа в конце периода i то доход в конце периода n

В этом случае удобно решать без производных. Найдем разность

Предполагая что при i=k ряд P(i) имеет локальный максимум запишем его условия

что эквивалентно (1)

Откуда применяя метод интервалов и формулу корней квадратного уравнения

или (2)

Для задач 1 типа может оказаться Это означает что бумаги не надо продавать

Для задач 2 типа из (1) при известном к получим интервал

Б)

Условие локального максимума

или

Для обоих типов зависимостей получается единственное решение k

Обратим внимание, что в случае линейной зависимости стоимости ценных бумаг от периода при выполнении условия из (3) получается ,что выгоднее их сразу продать

Это иллюстрируют диаграммы ниже

Примеры из ЕГЭ

509025

Решение

Продать бумагу следует в течение 8-го года.

516802 Пф владеет ценными бумагами, которые стоят   тыс. руб в конце года  В конце любого года пф может продать и положить деньги на счёт в банке, при этом в конце каждого следующего года сумма на счёте будет увеличена в  (1+r) раз. Пф хочет продать ценные бумаги в конце такого года, чтобы в конце 25 г сумма на его счёте была наибольшей. Расчёты показали, что для этого ценн бумаги надо продать строго в конце 21 г. При каких положительных  r это возможно?

Способ1 (по формуле)

Способ 2 (с производной)

Если пф продаст ценные бумаги в конце года k, то в конце 25 г на его счёте будет  тыс. руб.

Найдем производную полученного выражения:

Приравняем производную нулю откуда

Это единственная точка ,причем производная положительна при   и отрицательна при    Следовательно S(k)    возрастает на   и убывает на   Из условия известно, что продав бумаги н в конце 21 г, следовательно, доход, полученный при продаже бумаг в конце 21 г, больше чем доход, который мог бы получить фонд при продаже бумаг в конце 20-го г и в конце 22 г. Из выясненного выше характера монотонности функции S(k)  можно заключить, что выполнение неравенств 

  и   гарантирует что  для всех значений k, отличных от 21. А значит, необходимо и достаточно найти решение системы неравенств:

Прим. В решении нельзя ограничиться только решением неравенств (*). Из того, что доход при продаже бумаг в конце 21 г больше, чем доход при их продаже в конце 20 и 22 г не следует, что этот доход больше, чем при продаже в любой др год, а именно это огов в усл. но м обойт без произв.Например, рассмотрим разность предполагаемых доходов от продажи ценных бумаг в конце года к+1 и года :

1 множитель 0, 2й может менять значения. Положительность произведения значит, что

доход фонда при продаже в в конце года k, меньше дохода при их продаже в следующем году. Отрицательность значит, что   доход, фонда при, продаже ц б в конце года k, больше дохода, который мог получить при продаже в следующем году.

Пусть   Так как   квадратный трёхчлен имеет единственный корень на положительной полуоси, и потому если для некоторого натурального  k выполнено нер-во  то для любого выполненл нер-во 

Из этого следует что если доход при продаже акций в какой-то год оказ менее выгоден, чем доход при их продаже в преды год, то и во все после годы продавать акции будет менее выгодно.Поск ценные бумаги надо продавать строго в конце 21г, то одновременно выполняются нер=ва 

 и   т е  и   

Значит,   и   откуда 

2)В начале года за участие в инвестировании проекта фирме был выделен пакет ценных бумаг на 15 лет К концу каждого к-го года владения ценных бумаг их стоимость увеличивается и равна усл лен ед. В конце к-го года после очередного увеличения стоимости цб фирма имеет возмож-ность продать весь пакет, а вырученную сумму вложить в банк и тогда в конце следующего года вложения увеличатся в (1+р) раз Расчеты показали что к концу 15г сумма будет наибольшей только в случае продажи пакета к концу 8-го года При каких р0 это возможно?

Решение (по формуле(3)