Упр_3

Упражнения для занятия 3

Линейные целочисленные модели

Контрольные вопросы к разделу

1. Всегда ли стоит вводить целочисленные ограничения, чтобы получить целые решения? Есть ли отрицательные последствия введения таких ограничений? Какие?

2. Что такое логические переменные? В каких задачах их применение необходимо? Приведите 2-3 собственных примера.

3. Объясните, почему постоянные издержки нельзя учесть в простой ЛП-задаче (без целочисленных переменных)? Почему для определения оптимального плана неприемлема бухгалтерская практика "размазывания" постоянных издержек по всей партии выпущенных изделий и определение таким образом "удельных" издержек на единицу продукции?

4. Объясните, каким образом введение целочисленных (точнее, логических) переменных помогает решить проблему постоянных издержек в ЛП- задачах?

Примеры для самостоятельного анализа к разделу

1) Оптимальная загрузка оборудования ткацкого цеха (окончание)

Вернитесь к примеру "Оптимальная загрузка оборудования ткацкого цеха", рассмотренному в предыдущих разделах .

Для всех вариантов произведенных вами расчетов введите теперь целочисленные ограничения на переменные - число станков, выпускающих каждый из видов ткани.

1. Насколько сильно отличается оптимальное решение с целочисленным ограничением на переменные от полученных ранее?

2. Можно ли получить это оптимальное решение простым округлением решения ЛП-задачи? Стоит ли вводить целочисленное ограничение в этой задаче?

2) Минимизация отходов лесопилки (окончание)

Вернитесь к примеру "Минимизация отходов лесопилки", рассмотренному в предыдущих разделах 2 и 3. Так же как и при решении исходной задачи, считайте, что число стандартных кусков не менее заказа (но может быть и больше, т.е. часть кусков заготовлена впрок). Введите целочисленные ограничения.

Насколько сильно отличается оптимальное решение с целочисленным ограничением на переменные от полученных ранее? Стоит ли вводить целочисленное ограничение в этой задаче?

Измените ограничения исходной задачи так, чтобы число стандартных кусков было точно равно заказу (а не больше него). Введите целочисленные ограничения. Существует ли решение? Почему? Что нужно изменить в условиях задачи, чтобы решение существовало? Существенно ли целочисленное ограничение в этом случае?

3) Еще раз о плане кондитерской фабрики (окончание)

Модифицируем условия 3-го акта мини-кейса "На кондитерской фабрике". Будем считать, что постоянные издержки существуют при запуске линии на производство любых конфет и что для любых конфет они равны 100 у.е.

а) Организуйте данные на листе MS- Excel и решите задачу при этих условиях. Сколько видов конфет теперь выгодно выпускать? Насколько уменьшилась прибыль по сравнению с решением исходной задачи (акт 1 мини-кейса), сформулированной в разделе 2.1?

Допустим, что по маркетинговым соображениям вы не можете допустить столь бедного ассортимента и хотите потребовать, чтобы в оптимальный план вошло не менее 3 видов, 4 видов или все 5 видов продукции.

2. Введите в решение соответствующее ограничение и найдите оптимальный план. Как изменяется прибыль при расширении ассортимента продукции? Почему?

3. Всегда ли равенство Y, =1 означает реальное производство продукта? Почему?

Указания

• При организации данных на листе MS-Excel расположите логические переменные Yi, определяющие, производить или нет соответствующий продукт, под строкой переменных Х.

Используйте функцию СУММПРОИЗВ для записи целевой функции. Расположите строку с условиями, связывающими значения Y, и X, подстроками переменных.

• Количество производимых продуктов (точнее, тех, для которых производится настройка линии), очевидно, равно сумме всех Yi.

4) Выбор оптимальных проектов для финансирования

Управляющему банка были представлены предложения о четырех проектах, претендующих на кредиты банка. Проект A должен принести компании прибыль 21 тыс. долл., проект B - 18 тыс. долл., проект С- 16 тыс. долл. и проект D- 17 500 долл. При взвешивании этих предложений следует принять во внимание потребность проектов в наличности и массу доступной наличности для соответствующих периодов.

Доступная наличность банка составляет 22 тыс. долл. в течение периода 1, 25 тыс. долл. - в течение периода 2, 38 тыс. долл. - в течение периода 3 и 30 тыс. долл. - в течение периода 4.

Проект	Потребность в наличности, долл.
	Период 1	Период 2	Период 3	Период 4
А	8 000	8 000	10 000	10 000
В	7 000	9 000	9 000	11 000
С	5 000	7 000	9 000	11 000
D	9 000	8 000	7 000	6 000

Какие проекты следует финансировать и какое количество наличности необходимо в течение каждого периода, если цель состоит в том, чтобы максимизировать прибыль?

Указания

• Введите логические переменные Y_i, равные 1, если проект принимается, и равные 0, если нет.

• Суммарная потребность в наличности в данный период есть сумма произведений Y_i, на столбец финансовых затрат по каждому проекту в данный период.

5) Оптимальный план развития новых программных продуктов

Компания "Корвет" производит программное обеспечение на CD-ROM, которое продается в пакете с драйверами CD-ROM основными производителями компьютерного оборудования. Компания оценивает возможность развития 6 новых программных приложений. В таблице представлена информация о затратах и ожидаемой чистой приведенной прибыли от продажи приложения (с учетом временной стоимости денег).

У "Корвета" 60 программистов. Фирма может выделить 3,5 млн. долл. на развитие новых программных приложений. Каков оптимальный набор приложений, которые следует развивать, если

• ожидается, что клиенты, заинтересованные в приложении 4, будут заинтересованы также в приложении 5, и наоборот? Таким образом, если одно из приложений решено развивать, другое тоже должно быть развито;

• развитие приложения 1 имеет смысл, только если в пакет включено также приложение 2? Таким образом, если решено развивать приложение 1, то и приложение 2 должно быть развито. Однако если решено приложение 1 не развивать, то приложение 2 все же может быть включено в пакет;

• приложения 3 и 6 эксплуатируют одну и ту же тему? Следовательно, если одно из них развивается, то другое определенно нет;

• стремясь обеспечить качество продукции, "Корвет" не склонен развивать более 3 программных продуктов?

Приложение	Ожидаемые затраты на развитие, долл.	Требуемое число программистов	Ожидаемая чистая приведенная прибыль, долл.
1	400 000	6	2 000 000
2	1 100 000	18	3 600 000
3	940 000	20	4 000 000
4	760 000	16	3 000 000
5	1 260 000	28	4 400 000
6	1 800 000	34	6 200 000

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

Указания

• Введите логические переменные Y_i, для каждого из проектов - претендентов на включение в план и выразите через них целевую функцию и ограничения на все ресурсы фирмы.

• Если из каких-либо двух проектов либо оба должны быть приняты, либо оба отвергнуты, то значения Yi у них должны быть одинаковы.

• Если один проект принят (Y_i = 1), а другой при этом должен быть отвергнут (Yk= 0) и наоборот, то их значения Y_i и Yk должны в сумме всегда равняться 1.