Решение задачи линейного программирования

Фонд оценочных средств

по учебной дисциплине / практике

по дисциплине: Исследование операций и методы оптимизации

Прикладная информатика

Дата ввода – 24 сентября 2011г., протокол № 1

Дата изменения – 03 сентября 2014г., протокол № 1

2014 год

ПАСПОРТ

Фонда оценочных средств

по дисциплине_Исследование операций и методы оптимизации

¹Наименования разделов, тем, модулей соответствует рабочей программе дисциплины.

СОДЕРЖАНИЕ

1. Оценка знаний студентов по решению задач принятия решений…….4

1.1.Составление математической модели задачи принятия решения……......4

1.2. Решение задачи линейного программирования графическим методом..11

1.3. Решение задачи линейного программирования симплекс-методом

или двухфазным симплекс-методом…………………………………………...12

1.4. Решение транспортной задачи методом потенциалов…………………...13

1.5. Решение матричной игры………………………………………………….16

1.6. Оптимизация работы склада………………………………………………17

1.7. Задачи массового обслуживания………………………………………….18

2. Оценка содержания рефератов……………………………………………19

3. Вопросы для зачетов………………………………………………………..18

ОЦЕНКА ЗНАНИЙ СТУДЕНТОВ ПО РЕШЕНИЮ ЗАДАЧ

ПРИНЯТИЯ РЕШЕНИЙ

Составление математической модели задачи принятия решения

Вариант № 1

Фирма «Лесная пилорама» столкнулась с проблемой наиболее рационального использования ресурсов лесоматериалов, имеющихся в одном из принадлежащих этой фирме лесных массивов. В районе данного массива имеется лесопильный завод и фабрика, на которой изготовляется фанера. Таким образом, лесоматериалы можно использовать как для производства пиломатериалов, так и для изготовления фанеры.

Чтобы получить 2,5 м³ коммерчески реализуемых комплектов пиломатериалов, необходимо израсходовать 2,5 м³ еловых и 7,5 м³ пихтовых лесоматериалов. Для приготовления 100 м³ фанеры требуется 5 м³ еловых и 10м³ пихтовых лесоматериалов. Лесной массив содержит 80 м³ еловых и 180 м³ пихтовых лесоматериалов.

Согласно условиям поставок, в течение планируемого периода необходимо произвести, по крайней мере, 10 м³ пиломатериалов и 1200 м³ фанеры. Доход с 1 м³ пиломатериалов составляет 16 долл., а со 100 м³ фанеры - 60 долл.

Вариант № 2

Фирме «Иерихонская сталь» предстоит решить, какое количество x₁ чистой стали и какое количество х₂ металлолома следует использовать для приготовления (из соответствующею сплава) литья для одного, из своих заказчиков. Пусть производственные затраты в расчете на 1т чистой стали равняются 3 усл.ед., а затраты на 1т металлолома - 5 усл.ед. (последняя цифра больше предыдущей, так как использование металлолома сопряжено с его предварительной очисткой). Заказ предусматривает поставку не менее 5т литья; при этом заказчик готов купить и большее количество литья, если фирма "Иерихонская сталь" поставит перед ним такие условия.

Предположим, что запасы чистой стали ограничены и не превышают 4т, a запасы металлолома не превышают 6т. Отношение веса металлолома к весу чистой стали в процессе получения сплава не должно превышать 7 : 8. Производственно-технологические, условия таковы, что на процессы плавки и литья не может быть отведено более 18 ч; при этом на 1т стали уходит 3ч, а на 1 металлолома - 1ч производственного времени.

Вариант № 3

Фирма "Лакомка" выпускает четыре вида пищевых полуфабрикатов: полуфабрикат 1, полуфабрикат 2, полуфабрикат 3 и полуфабрикат 4. Каждый полуфабрикат состоит из ряда ингредиентов (таких, как крахмал, сахар, витамины и т.д.). Пусть индекс i указывает на порядковый номер ингредиента (i=1,2,…I). Обозначим через a_ij количество ингредиента i в одном килограмме полуфабриката j. Предположим, что максимальное количество ингредиента i, которым данная фирма располагает в течение ближайшего месяца, равняется M_i.

Доход, получаемый с одного килограмма полуфабриката j, обозначим через p_j. Через x_j обозначим число килограммов полуфабриката j, произведенного фирмой "Лакомка" в течение ближайшего месяца. Пусть за этот период должно быть произведено не менее 100000 килограммов полуфабриката 1, 125000 килограммов полуфабриката 2, 30000 килограммов полуфабриката 3 и 500000 килограммов полуфабриката 4.

Требуется построить оптимальный план выпуска перечисленной выше продукции.

Вариант № 4

Фирмой «Супертранзистор» выпускаются радиоприемники трех различных моделей: модель А, модель В и модель С. Каждое изделие указанных моделей приносит доход в размере 8, 15 и 25 соответственно. Необходимо, чтобы фирма выпускала за неделю не менее 100 приемников модели А, 150 моделей приемников модели В и 75 приемников модели С.

Каждая модель характеризуется определенным временем, необходимым для изготовления соответствующих деталей, сборки изделия и его упаковки. Так, в частности, в расчете на 10 приемников модели А требуется 3ч для изготовления соответствующих деталей, 4ч на сборку и 1ч на упаковку. Соответствующие показатели в расчете на 10 приемников модели В равняются 3.5, 5 и 1.5ч, а на 10 приемников модели С - 5, 8 и 3. В течение ближайшей недели фирма может израсходовать на производство радиодеталей 150 ч, на сборку 200 ч и на упаковку 60ч.

Для решения задачи производственного планирования требуется построить соответствующую модель.

Вариант № 5

Управляющий фирмы "Свежие нефтепродукты" пытается определить оптимальное распределение имеющейся в его распоряжении сырой нефти (различного сорта) по двум возможным технологическим процессам составления смесей. Технологический процесс 1 характеризуется следующими показателями: из одной единицы объема сырой нефти А и трех единиц объема сырой нефти В получается пять единиц объема бензина Х и две единицы объема бензина Y.

Технологический процесс 2 характеризуется другими показателями: из четырех единиц объема сырой нефти А и двух единиц объема сырой нефти В получается три единицы объема бензина Х и восемь единиц объема бензина Y. Объемы продукции, выпускаемой при реализации технологических процессов 1 и 2, обозначим соответственно через х₁ и x₂.

Максимальное количество запасов сырой нефти А равняется 100 единицам объема, а сырой нефти В - 150 единицам объема. По условиям поставок требуется произвести не менее 200 единиц объема бензина Х и 75 единиц объема бензина Y. Доходы с единицы объема продукции, получаемой с помощью технологических процессов 1 и 2, составляют p₁ и р₂ соответственно.

Вариант № 6

Авиакомпания "Небесный грузовик", обслуживающая периферийные районы страны, располагает 8 самолетами типа 1, 15 самолетами типа 2, 12 самолетами типа 3, которые она может использовать для выполнения рейсов в течение ближайших суток. Грузоподъемность (в тысячах тонн) известна: 45 для самолетов типа 1, 7 для самолетов типа 2, 4 для самолетов типа 3.

Авиакомпания обслуживает города А и В. Городу А требуется тоннаж в 20000 т, а городу В - в 30000 т. Избыточный тоннаж не оплачивается. Каждый самолет в течение дня может выполнить только один рейс.

Расходы, связанные с перелетом самолетов по маршруту "Центральный аэродром - пункт назначения", указаны в приведенной ниже таблице:

Обозначим через x_i (i = 1, 2, 3) число самолетов i-го Типа, отправленных в город А, а через y_j (j = 1, 2, 3) число самолетов j-го типа, отправленных в город В. Построить модель оптимальных перевозок.

Вариант № 7

Авиакомпании "'Ночной полет" необходимо решить, какое количество топлива для реактивных самолетов следует закупить у фирм поставщиков, если число последних равно трем и имеют место следующие требования и ограничения:

Заправка самолетов производится регулярно в четырех аэропортах.

Нефтяные компании констатируют следующие возможности поставки топлива в течение ближайшего месяца: а) 2500000 л - нефтяная компания 1; б) 5000000 л - нефтяная компания 2; в) 6000000 л - нефтяная компания 3.

Авиакомпании требуется следующее количество топлива: а) 1000000 л в аэропорту 1; б) 2000000 л в аэропорту 2; в) 3000000 л в аэропорту 3; г) 4000000 л в аэропорту 4.

Стоимости 1л реактивного топлива с учетом расходов, связанных с доставкой, имеют значения, приведенные в следующей таблице:

Построить модель оптимизации управляющего решения.

Вариант № 8

Фирма "Нитроткань" производит определенного типа мелкие детали для промышленных изделий и продает их через своих посредников-оптовиков по фиксированной поставочной цене 2,50 долл. за штуку. Число посредников-оптовиков равняется пяти. Коммерческие прогнозы указывают на то, что объем месячных поставок, составит: посреднику 1 - 3000 штук, посреднику 2 - 3000 штук, посреднику 3 - 10 000 штук, посреднику 4 - 5000 штук, посреднику 5 - 4000 штук.

Фирма располагает следующими производственными мощностями: завод 1 - 5000 деталей в месяц, завод 2 - 10000 деталей в месяц, завод 3 - 12500 деталей в месяц. Себестоимость одной детали, изготовленной на заводе 1, равняется 1 долл., на заводе 2 -0,90 долл., на заводе 3 - 0,80 долл.

Транспортные расходы (в долларах), связанные с доставкой одной детали в точки оптовой продажи, приведены ниже:

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

Вариант № 9

Полицейская служба имеет следующие минимальные потребности в количестве полицейских в различное время суток:

При этом нужно иметь в виду, что период 1 следует сразу же за периодом 6.

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

Вариант № 10

Авиакомпании "Перманентный рейс" требуется определить, сколько стюардесс следует принять на работу в течение шести месяцев при условии, если каждая из них, прежде чем приступить к самостоятельному выполнению обязанностей стюардессы, должна пройти предварительную подготовку. Потребности в количестве стюардессо-часов (с.-ч.) летного времени известны: в январе требуется 8000 с.-ч.. в феврале - 9000, в марте - 8000, в апреле - 10000, в мае - 9000, в июне - 12 000 с.-ч.

Подготовка стюардессы к выполнению своих обязанностей на регулярных авиалиниях занимает один месяц. Следовательно, прием на работу должен, по крайней мере, на один месяц опережать ввод стюардессы в строй. Кроме того, каждая обучаемая стюардесса должна в течение месяца, отведенного на ее подготовку, пройти 100-часовую практику непосредственно во время полетов. Таким образом, за счет каждой обучаемой стюардессы в течение месяца освобождается 100 ч. рабочего времени, отведенного для уже обученных стюардесс.

Каждая полностью обученная стюардесса в течение месяца может иметь налет до 150 ч. Авиакомпания "Перманентный рейс" в начале января уже имеет 60 опытных стюардесс. Если ресурсы стюардессо-часов (летного времени) превышают месячные потребности авиакомпании, то стюардессы работают в режиме налета менее 150 ч в месяц. При этом ни одну из них не снимают с работы. Установлено также, что приблизительно 10% обученных стюардесс увольняются по собственному желанию, по семейным или другим причинам. Опытная стюардесса обходится авиакомпании в 800 долл., а обучаемая - в 400 долл. в месяц.

Вариант № 11

Фирма "Комфорт" производит холодильники, газовые плиты и кухонные раковины. В наступающем году ожидается следующий уровень сбыта:

Фирма разрабатывает производственный план, который был бы в состоянии удовлетворить указанный спрос. Кроме того, фирмой принято решение в конце каждого квартала иметь запасы в размере 1000 единиц каждого вида продукции. В начале первого квартала запасы отсутствуют.

В течение квартала фирма может израсходовать не более 8000 "приведенных часов" (п. ч.) рабочего времени. На изготовление холодильника требуется 0,5 п.ч., газовой плиты - 2 п.ч., а кухонной раковины - 1,5 п.ч. В четвертом квартале холодильники не могут изготовляться, так как фирма планирует произвести в это время частичное переоборудование предприятия в связи с введением в действие новой конвейерной линии.

Допустим, что хранение каждой единицы продукции на складе в течение квартала обходится фирме в 5 усл.ед. Фирма разрабатывает производственный план с учетом поквартальных лимитов производственного времени, ориентируясь при этом на полное удовлетворение спроса. Она стремится также к минимизации издержек, связанных с хранением продукции на складе.

Вариант № 12

Фирма "Всякая всячина", выпускающая лезвия для бритв, объявила о переходе к производству совершенно новых лезвий улучшенного качества. Реакция потребителей на проведенную фирмой рекламную кампанию оказалась вполне удовлетворительной. Фирма имеет два предприятия и три оптовых склада, размещенных в различных географических пунктах. Лезвия на склады доставляются по железной дороге партиями. Выпуск лезвий в течение одного месяца на предприятиях 1 и 2 составляет S₁=100 и S₂⁼200 соответственно. Возможности сбыта на складах 1, 2 и 3 в течение этого месяца равны соответственно D₁=150, D₂⁼200 и D₃=250. Как видно, возможный сбыт, т.е. спрос, значительно превышает поставки, вследствие чего часть потребностей останется неудовлетворенной.

Предположим, что транспортные расходы на доставку одного вагона лезвий с предприятия i на склад j равны t_ij и что доход от сбыта этого вагона на складе j равен р_j. (Фирма может продавать свои лезвия по различным ценам в различных пунктах страны).

Постройте транспортную модель с целевой функцией, тождественной прибыли.

Вариант № 13

Фирма "С дальним прицелом" должна выполнять обязательства по поставке D₁, D₂,...,D_n единиц своей продукции в течение периодов 1, 2, ..., соответственно. При условии односменной работы объем продукции фирмы в течение периода t составляет m_t единиц. При этом прямые затраты на производство одной единицы равны p_t. Пользуясь сверхурочными, фирма может выпустить дополнительно e_t единиц при прямых затратах qt на единицу, где q_t>p_t. Поскольку обязательства по поставкам меняются в значительных пределах, руководство фирмы полагает, что в отдельные периоды может потребоваться создание запасов с целью удовлетворения спроса в последующие периоды. Затраты на хранение единицы запаса к концу периода t составляют h_t денежных единиц. Постройте транспортную модель, позволяющую найти программу производства и хранения минимальной стоимости.

Вариант № 14

Фирма «Микродеталь» является владельцем мелкосерийного металлообрабатывающего завода. Дневной портфель заказов включает n деталей, каждая из которых может обрабатываться на n различных станках. Пусть t_ij-общая продолжительность обработки детали i на станке j (включая время наладки станка). Постройте оптимизационную модель, минимизирующую общую продолжительность выполнения всех заказов.

Вариант № 15

Требуется составить расписание занятий на факультете. В частности, нужно назначить n преподавателей в n групп. Ранее студенты заполнили анкеты с оценками преподавателей, И поэтому известно, в какой степени студентам нравятся преподаватели, которые вели у них занятия. (В некоторых случаях преподаватель никогда не проводил занятий в какой-либо группе, и поэтому приходится оценить, насколько этот преподаватель понравится студентам этой группы. В других случаях преподаватель не хочет или не может вести, занятия в конкретной группе, так что следует исключить возможность назначения этого преподавателя в данную группу).

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

Вариант № 16

Фирма имеет запасы продуктов, качество которых ухудшается при хранении, причем ухудшенное качество оценивается недельными периодами хранения. Предположим, что текущие запасы фирмы составляют четыре единицы, занумерованные индексами i = 1,2, 3, 4, срок хранения обозначается символом A_i. Фирма заключила следующий контракт на продажу этих продуктов. Одна партия должна быть поставлена через t₁ недель с начала отсчета, другая - через t₂ недель, третья - через t₃ недель и четвертая - через t₄ недель. Доход, получаемый фирмой за каждую партию, является функцией продолжительности хранения с момента поставки. Эта функция обозначается R(A), где А - соответствующая продолжительность хранения.

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

Вариант № 17

Отдел стипендий и оказания материальной помощи студентам одного из университетов готовит предложения относительно назначения стипендий на следующий год. В качестве будущих стипендиатов выбрано n студентов, причем студенту i предполагается назначить стипендию не менее M_i долл., i == 1, 2,..., n. В распоряжении отдела имеется s различных стипендий. Стипендия j дает стипендиату а_j, долл. Отдел может оказаться вынужденным назначить отдельным студентам по несколько стипендий, чтобы они получали не менее чем по M_i долл., но руководство отдела не имеет права уменьшить размер каждой стипендии ниже фиксированной суммы а_j,. Если стипендия j на рассматриваемый год вообще не назначается, то к величине a_j, прибавляются проценты, и эта стипендия может быть назначена в увеличенном размере в следующем году. Постройте модель назначения стипендий, максимизирующую сумму сэкономленных денег при условии, что каждый студент получит, по крайней мере, M_i долл.

Вариант № 18

Администрация штата объявила торги на n строительных подрядов для n фирм. Ни с одной фирмой не заключается более одного контракта. По политическим соображениям чиновники администрации стремятся не заключать более N крупных контрактов с фирмами, расположенными за пределами штата. Обозначим через 1, 2,..., s крупные контракты, а через 1,2,..., t - фирмы, расположенные за пределами штата. Целью является минимизация общих затрат при указанном условии.

Вариант № 19

Фирма снабжает своими изделиями сеть небольших ресторанов, отпускающих обеды на дом. Фирма стремится обеспечить каждому владельцу такого домового ресторана достаточную прибыль. Рассматривается возможность размещения n новых точек подобного типа в крупном микрорайоне. По имеющейся оценке, размещение ресторана в пункте j обеспечит получение приемлемого дохода R_j при условии, что в радиусе 5 миль от него аналогичная торговая точка отсутствует. Примем d_ij = 1, если пункты i и j размещения домовых ресторанов находятся в пределах радиуса 5 миль, и d_ij=0 в противном случае. Фирма рассчитала все возможные d_ij и стремится выбрать схему размещения новых домовых ресторанов, обеспечивающую максимизацию общего дохода.

Вариант № 20

Задача о доставке грузов (задача о покрытии). Фирма "Автопегас" должна доставить грузы пяти своим клиентам в течение рассматриваемого дня. Клиенту А нужно доставить груз весом в 1 единицу, клиенту В - в 2 единицы, клиенту С - в 3 единицы, клиенту D - в 5 единиц и клиенту Е - в 8 единиц. Фирма располагает четырьмя автомашинами грузоподъемностью: машина 1 - 2 единиц, машина 2 - 6 единиц, машина 3 - 8 единиц, машина 4 - 8 единиц Стоимость эксплуатации автомашины j составляет c_j. Предположим, что одна машина не может доставлять груз обоим клиентам А и С, аналогично одна машина не может использоваться для доставки груза обоим клиентам B и D. Постройте модель для определения такого назначения автомашин для доставки всех грузив, при котором минимизируются суммарные затраты.

Решение задачи линейного программирования