Лабораторная работа №2 (часть I) “одноиндексные задачи линейного программирования”

2.1. ЦЕЛЬ РАБОТЫ

Приобретение навыков построения математических моделей одноиндексных задач ЛП и решения их в Microsoft Excel.

2.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Согласно номеру своего варианта выберите условие задачи и постройте ее модель.

2. Найдите оптимальное решение задачи в Excel и продемонстрируйте его преподавателю.

Задача №1. Общую сумму капиталовложений 1200 млрд. руб. необходимо разделить между пятью объектами, потребности которых соответственно 420, 180, 240, 560, 300 млрд. руб., а ожидаемые прибыли 80, 65, 90, 210, 150 млрд. руб. На каждый объект капиталовложения или выделяются в необходимой сумме, или вообще не выделяются. Составить математическую модель задачи целочисленного программирования, заключающей в оптимальном распределении капиталовложений, и найти ее решение.

Решение. Математическая модель задачи:

,

.

Ответ: (0;0;1;1;1), .

Возможны различные варианты данной задачи. Пусть, например, задано дополнительное условие: капиталовложения обязательно вкладываются или в 4-й, или в 5-й объект.

Задача №2. Руководство завода предполагает провести комплекс организационно-технических мероприятий с целью модернизации производства. Мероприятия предполагают затраты производственных, трудовых и финансовых ресурсов.

Мероприятие	Трудовые ресурсы, чел-дней	Финансовые ресурсы, млн. руб.	Производственные площади, м. кв.	Экономический эффект, млн. р.
Закупка станков с ЧПУ	350	400	130	13000
Текущий ремонт	250	90	-	3000
Монтаж транспортного конвейера	100	60	300	8000
Установка рельсового крана	200	300	150	12000
Ввод системы контроля качества	130	-	150	2500
Разработка АСУП	800	500	100	15000

На реализацию всех мероприятий завод может выделить: трудовых ресурсов 1300 чел-дней, финансовых – 1 млрд. руб., производственных площадей – 700 кв. м.

Какие мероприятия следует провести, чтобы общий экономический эффект был максимальным?

1. Каков максимальный экономический эффект от проведения мероприятий (млн. руб.)?

2. Какое количество мероприятий следует провести?

Решение. Делим все показатели на 100, обозначаем мероприятия: закупка станков с ЧПУ – , текущий ремонт - , монтаж транспортного конвейера - , установка рельсового крана - , ввод системы контроля качества - , разработка АСУП - .

Приходим к целочисленной задаче линейного программирования: ,

Ответ:1) 37500 млн. руб., 2) 4.

Задача №3. Предприятие рекламирует свою продукцию с использованием четырех источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5, 7 и 4 усл. ед. в расчете на 1 усл. ед., затраченную на рекламу. На рекламу выделено 50 000 усл. ед. Администрация телевидения не намерена тратить на телевидение более 40%, а на радио и газеты – более 50% от общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль?

Задача №4. Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 1000 изделий первого вида, 2000 изделий второго вида и 2500 изделий третьего вида. Условия спроса на рынке ограничивают число изделий первого вида 2000 единицами, второго – 3000 и третьего – 5000 единицами. Для изготовления изделий используется 4 типа ресурсов. Количество ресурсов, потребляемых для производства одного изделия, общее количество ресурсов и прибыль от реализации одного изделия каждого вида заданы в таблице:

Тип ресурсов	Вид изделия			Всего ресурсов
	1	2	3
1	500	300	1000	25000000
2	1000	200	100	30000000
3	150	300	200	20000000
4	100	200	400	40000000
Прибыль	20	40	50

Как организовать производство, чтобы:

1. обеспечить заказчиков;

2. не допустить затоваривания;

3. получить максимальную прибыль?

Задача №5. В планируемом периоде предприятию необходимо обеспечить производство 300 тыс. однородных новых изделий, которые могут выпускать четыре филиала. Для освоения этого нового вида изделий выделены капитальные вложения в размере 18 млн. руб. Разработанные для каждого филиала проекты освоения нового вида изделия характеризуются величинами удельных капитальных вложений и себестоимостью единицы продукции в соответствии с таблицей:

Показатели	Филиалы предприятия
	1	2	3	4
Себестоимость производства изделия, руб.	83	89	95	98
Удельные капиталовложения, руб.	120	80	90	40

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

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

Задача №6. Фирма «N.Shagas&Co» производит три типа химикатов. На предстоящий месяц эта фирма заключила контракт на поставку следующих количеств трех типов химикатов:

Тип химикатов	Продажи по контракту, кг
1	2000
2	3500
3	1800

Производство фирмы ограничено наличием времени на обработку химикатов в двух химических реакторах. Каждый вид химикатов должен быть обработан сначала в реакторе 1, а затем в реакторе 2. в следующей таблице приведен фонд рабочего времени в часах, имеющихся у каждого реактора в следующем месяце, а также время на обработку 1 кг каждого химиката в каждом реакторе (ч/кг).

	Химикаты			Возможности реактора, ч
	1	2	3
Реактор 1	0,05	0,04	0,01	200
Реактор 2	0,02	0,06	0,03	150

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

Химикаты	Затраты на производство, тыс. р./кг	Затраты на покупку, тыс. р./кг
1	2,50	2,80
2	1,75	2,50
3	2,90	3,25

Цель фирмы состоит в том, чтобы выполнить заказ клиента с минимальными издержками. Это позволит ей максимизировать прибыль. Другими словами, фирма должна принять решение: сколько и каких продуктов надо производить у себя, а сколько – купить на стороне.

Задача №7. чулочно-носочная фирма производит и продает два вида товаров. Фирма получает прибыль в размере 12 тыс. руб. от производства продажи каждой единицы товара 1 и в размере 4 тыс. руб. от производства и продажи каждой единицы товара 2. фирма состоит из трех подразделений. Затраты труда (чел-дни) а производство этих товаров в каждом из подразделений указаны в таблице:

Подразделение	Трудозатраты, чел-дней на 1 шт.
	Товар 1	Товар 2
1	1	2
2	1	3
3	2	3

Руководство рассчитало, что в следующем месяце фирма будет располагать следующими возможностями обеспечения производства трудозатратами: 800 чел-дней в подразделении 1, 600 – в подразделении 2, 2000 – в подразделении 3. Какую максимальную прибыль может получить фирма?

Задача №8. В аптеке продается 7 наименований поливитаминов. Каждое наименование содержит витамины трех различных типов. Цены на витамины различны. Необходимо пройти профилактический курс, в течение которого с минимальными суммарными затратами получить 100 единиц витамина А, 80 – витамина С и 120 единиц витамина В₆.необходимое количество поливитаминов покупается одновременно.

Витамины	Содержание витаминов, ед./г							Всего необходимо
	Р1	Р2	Р3	Р4	Р5	Р6	Р7
А	5	0	2	0	3	1	2	100
С	3	1	5	0	2	0	1	80
В6	1	2	3	1	2	0	6	120
Цена за 1 г, тыс. руб.	4	1	5	6	3,5	7	4

1. Какое общее количество поливитаминов следует принять (г)?

2. Какое количество поливитамина Р₁ следует принять (г)?

3. Каковы минимальные затраты на профилактический курс (тыс. руб.)?

Задача №9. «Южная алкогольная компания» импортирует смеси трех сортов виски – ирландского, шотландского, канадского. Смешивают их согласно рецептам, устанавливающим максимум или минимум процентного содержания ирландского и канадского виски в каждой смеси. Компания стремится к получению максимальной прибыли ежедневно.

Инструкция по составлению смесей

Смесь	Спецификация	Цена за 1 л смеси, тыс. руб
«Старый Джек»	Не меньше, чем 60% ирландского Не больше, чем 20% канадского	68
«Специальное»	Не больше, чем 60% канадского Не меньше, чем 15% ирландского	57
«Юный Френзи»	Не больше, чем 50% канадского	45

Запасы трех основных видов виски и их стоимость показаны ниже:

Сорт виски	Наличие, л/день	Стоимость 1 л
Ирландское	2000	70
Шотландское	2500	50
Канадское	1200	40

1. Сколько ежедневно следует производить смеси «Старый Джек»?

2. Какова максимальная прибыль в день?

Задача №10. мощности завода по производству удобрений позволяют произвести в текущем месяце 1000 т нитратов, 1800 т фосфатов и 1200 т поташа. В результате смешения этих активных ингредиентов с инертными, запасы которых не ограничены, могут получены три типа удобрений. В таблице указано содержание активных ингредиентов (нитратов, фосфатов и поташа) в смеси.

Тип удобрения	Процентное содержание активных ингредиентов			Цена тыс. руб./т
	Нитраты	Фосфаты	Поташ
1	5	10	5	40
2	5	10	10	50
3	10	10	10	60
Цена, тыс. руб./т	160	40	100

Цена инертных ингредиентов составляет 5 тыс. руб.

Затраты смешения, упаковки и продажи составляют 15 тыс. руб. для каждого типа удобрений. Существует соглашение о поставке 6000 т удобрений типа 1.

1. Сколько удобрений типа 3 следует производить (т)?

2. Какова максимальная прибыль (тыс. руб.) ?

Задача №11. На складах А₁, А₂, А₃ хранится 100, 200, 120 единиц одного и того же груза соответственно. Требуется доставить его потребителям в количестве соответственно 190, 120, 60 и 50 единиц. Стоимости перевозки единицы груза со складов потребителям даны в матрице . Составить план перевозок, обеспечивающий минимальную стоимость перевозок.

Задача №12. Самолеты компании Аэрофлот летают между Москвой и Вильнюсом. Полеты беспосадочные. График движения показан в таблице:

	Рейс	Отправление	Прибытие			Рейс	Отправление	Прибытие
Из Москвы в Вильнюс	110	6.00	8.00		Из Вильнюса в Москву	310	7.00	9.00
	120	8.00	10.00			320	10.00	12.00
	130	12.00	14.00			330	13.00	15.00
	140	15.00	17.00			340	16.00	18.00
	150	19.00	21.00			350	21.00	23.00
	160	23.00	1.00			360	0.00	2.00

Рейсы могут обслуживаться российскими или литовскими экипажами. Какие экипажи должны обслуживать рейсы, чтобы общее время пребывания экипажей в аэропортах за границей было минимальным (следует учитывать только то время, которое экипаж проводит в аэропорту чужой страны)?

1. Верно ли, что рейс 310 должен обслуживаться российским экипажем?

2. Верно ли, что рейс 150 должен обслуживаться литовским экипажем?

3. Какое минимальное общее время пребывания экипажей в аэропортах за границей (ч)?

Задача №13. Институт получил гранты на выполнение четырех исследовательских проектов. Выходные результаты первого проекта являются входными данными для второго проекта, выходные результаты второго проекта – это входные данные для третьего проекта, результаты третьего проекта используются для работы над четвертым проектом. В качестве научных руководителей проектов рассматриваются кандидатуры четырех ученых, обладающих различным опытом и способностями. Каждый ученый оценил время, необходимое ему для реализации проекта. Матрица времен приведена ниже: . В i-й строке j-ом столбце матрицы Т стоит время на выполнение i-м ученым j-го проекта. Продолжительность времени задана в месяцах. Требуется выбрать научного руководителя для выполнения каждого проекта так, чтобы суммарное время выполнения всех проектов было минимальным.

Задача №14. Оптимальное исследование рынка. Группе, исследующей рынок пылесосов фирмы «Мой-до-дыр», требуется получить данные из пяти районов орловской области. В ее распоряжении имеется 5 дней, и она предполагает провести по одному дню в каждом районе, проведя по опросов, , . Вероятность успешного опроса в каждом районе задается матрицей . Элемент матрицы Р_ij характеризует вероятность успешного опроса в течение i-го дня в j-м месте, . Определить время проведения опросов, при котором общее число опросов максимально.

Замечание. Сведем данную задачу к задаче о назначениях. Введем величину , показывающую число успешных опросов в течение i-го дня в j-м месте.

Математическая модель задачи имеет следующий вид:

Функция R характеризует суммарное число опросов. Его нужно максимизировать. Первое и второе ограничения соответствуют тому, что в течение одного дня можно находиться только в одном месте.

Задача 15. Торговая фирма «Жалюзи на дом» продает товары в 4-х городах – Орле, Курске, Туле и Белгороде, покупательная способность жителей которых оценивается в усл. ед. . Для реализации товаров фирма располагает 4-мя торговыми агентами, каждого из которых она направляет в один из городов. Профессиональный уровень агентов различен. Доля реализуемых i-м торговым агентом покупательных способностей составляет .как следует распределить торговых агентов по городам, чтобы фирма получила максимальную выручку от продажи товаров?

Замечание. Оптимальное решение этой проблемы может быть найдено с помощью задачи о назначениях. В качестве кандидатов выступают торговые агенты, в качестве работ – города. Введем величину , характеризующую величину покупательных способностей, реализуемых i-м торговым агентом в j-м городе. Управляющие переменные определяются по формуле .

Математическая модель задачи имеет следующий вид:

Первое и второе ограничения формализуют соответственно условия о том, что в каждый город направляется один торговый агент, и один торговый агент не может работать в двух городах. Целевая функция С – это сумма реализованных покупательных способностей всеми торговыми агентами во всех городах. Она должна быть максимальна.