Запуск задачи на решение

Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить".

После запуска на решение задачи ЛП на экране появляется окно "Результаты поиска решения" с одним из сообщений, представленных на рис.

Иногда сообщения, представленные на рис., свидетельствуют не о характере оптимального решения задачи, а о том, что при вводе условий задачи в Excel были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует (см. ниже подразд.1.3.5).

Если при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра "Относительная погрешность" не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.

В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы". Они необходимы при анализе полученного решения на чувствительность (см. ниже подразд.3.3). Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку "OK". После этого в экранной форме появляется оптимальное решение задачи.

1.3.2. Целочисленное программирование

Допустим, что к условию задачи (1.1) добавилось требование целочисленности значений всех переменных. В этом случае описанный выше процесс ввода условия задачи необходимо дополнить следующими шагами.

· В экранной форме укажите, на какие переменные накладывается требование целочисленности (этот шаг делается для наглядности восприятия условия задачи) (рис.1.13).

· В окне "Поиск решения" (меню "Сервис"®"Поиск решения"), нажмите кнопку "Добавить" и в появившемся окне "Добавление ограничений" введите ограничения следующим образом (рис.1.14):

- в поле "Ссылка на ячейку" введите адреса ячеек переменных задачи, то есть $B$3:$E$3;

- в поле ввода знака ограничения установите "целое" ;

- подтвердите ввод ограничения нажатием кнопки " OK" .

1.3.3. Двухиндексные задачи ЛП

Двухиндексные задачи ЛП вводятся и решаются в Excel аналогично одноиндексным задачам. Специфика ввода условия двухиндексной задачи ЛП состоит лишь в удобстве матричного задания переменных задачи и коэффициентов ЦФ.

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

Исходные данные транспортной задачи

Тарифы, руб./шт.	1-й магазин	2-й магазин	3-й магазин	Запасы, шт.
1-й склад
2-й склад
3-й склад
4-й склад
Потребности, шт.

Целевая функция и ограничения данной задачи имеют вид

Экранные формы, задание переменных, целевой функции, ограничений и граничных условий двухиндексной задачи (1.5) и ее решение представлены на рис. и в табл.

Формулы экранной формы задачи

Объект математической модели	Выражение в Excel
Переменные задачи	C3:E6
Формула в целевой ячейке F15	=СУММПРОИЗВ(C3:E6;C12:E15)
Ограничения по строкам в ячейках F3, F4, F5, F6	=СУММ(C3:E3) =СУММ(C4:E4) =СУММ(C5:E5) =СУММ(C6:E6)
Ограничения по столбцам в ячейках С7, D7, E7	=СУММ(C3:C6) =СУММ(D3:D6) =СУММ(E3:E6)
Суммарные запасы и потребности в ячейках H8, G9	=СУММ(H3:H6) =СУММ(C9:E9)

1.3.4. Задачи с булевыми переменными

Частным случаем задач с целочисленными переменными являются задачи, в результате решения которых искомые переменные могут принимать только одно из двух значений: 0 или 1. Такие переменные в честь предложившего их английского математика Джорджа Буля называют булевыми. На рис. представлена экранная форма с решением некоторой двухиндексной задачи с булевыми переменными.

Помимо задания требования целочисленности (см. подразд.1.3.2) при вводе условия задач с булевыми переменными необходимо:

· для наглядности восприятия ввести в экранную форму слово "булевы" в качестве характеристики переменных;

· в окне "Поиск решения" добавить граничные условия, имеющие смысл ограничения значений переменных по их единичной верхней границе.

Вид окна "Поиск решения" для задачи с булевыми переменными.

1.3. ВАРИАНТЫ

Используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту (табл.).

Варианты задач к лабораторной работе №1

№ варианта	Математическая модель

№ варианта	Математическая модель

№ варианта	Математическая модель

ЛАБОРАТОРНАЯ РАБОТА №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. Руководство завода предполагает провести комплекс организационно-технических мероприятий с целью модернизации производства. Мероприятия предполагают затраты производственных, трудовых и финансовых ресурсов.

Мероприятие	Трудовые ресурсы, чел-дней	Финансовые ресурсы, млн. руб.	Производственные площади, м. кв.	Экономический эффект, млн. р.
Закупка станков с ЧПУ
Текущий ремонт			-
Монтаж транспортного конвейера
Установка рельсового крана
Ввод системы контроля качества		-
Разработка АСУП

На реализацию всех мероприятий завод может выделить: трудовых ресурсов 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)получить максимальную прибыль?

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

Показатели	Филиалы предприятия
Себестоимость производства изделия, руб.
Удельные капиталовложения, руб.

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

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

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

Тип химикатов	Продажи по контракту, кг

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сорт виски	Наличие, л/день	Стоимость 1 л
Ирландское
Шотландское
Канадское

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

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

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

Тип удобрения	Процентное содержание активных ингредиентов	Цена тыс. руб./т
Нитраты	Фосфаты	Поташ
Цена, тыс. руб./т

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

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

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

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

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

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

	Рейс	Отправление	Прибытие			Рейс	Отправление	Прибытие
Из Москвы в Вильнюс		6.00	8.00		Из Вильнюса в Москву		7.00	9.00
	8.00	10.00			10.00	12.00
	12.00	14.00			13.00	15.00
	15.00	17.00			16.00	18.00
	19.00	21.00			21.00	23.00
	23.00	1.00			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-м городе. Управляющие переменные определяются по формуле .

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

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

ЛАБОРАТОРНАЯ РАБОТА №2 (ЧАСТЬ II) “АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОДНОИНДЕКСНЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ”

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

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

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

1. Для задачи, решенной в лабораторной работе №2 (часть I), получите в Excel все типы отчетов по результатам поиска решения, необходимые для анализа чувствительности.

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

3. Результаты анализа задачи на чувствительность внесите в общий отчет по лабораторной работе №2.

ЛАБОРАТОРНАЯ РАБОТА №3 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СТАНДАРТНАЯ ТРАНСПОРТНАЯ ЗАДАЧА”

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

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

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

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

2. Постройте модель задачи, включая транспортную таблицу.

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

4.3. ВАРИАНТЫ

Дата добавления: 2014-12-27