ТУСУР, исследование операций (лабораторная работа)

Тема лабораторной работы: Моделирование и решение задач линейного программирования общего вида

Лабораторная работа представляется к защите в виде отчета, содержащего постановку и решение задач линейного программирования, указанных в задании на работу.

В отчет включаются следующие пункты:

1) номер варианта и текст задачи;

2) таблица исходных данных;

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

4) математическая задача в числовой форме;

5) методы решения задачи;

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

Цель работы:

1. Построение математической модели реальных ситуаций в виде задачи ЛП.

2. Изучение возможностей пакетов прикладных программ для ЛП.

3. Решение индивидуальной задачи путем построения математической модели и использования пакета.

4. Анализ решений задачи ЛП.

Порядок выполнения работы:

1. Знакомство с пакетом ПП (с помощью Ms Excel, см. п.4).

2. Изучение возможностей ППП, математическое моделирование тестовой задачи.

3. Выполнение индивидуального задания:

a) введение формализованных обозначений задачи,

b) составление математической модели,

c) ввод и решение задачи,

d) анализ оптимального решения на чувствительность к изменениям исходных данных.

Составление подробного отчёта по лабораторной работе, в котором представляется:

– формулировка индивидуального задания,

– математическая модель и пояснение к её построению,

– входная таблица с экрана монитора и выходные таблицы для всех опций программы и содержательные пояснения к ним,

– анализ на пределы (диапазон) изменения запаса одного из дефицитных ресурсов,

– выводы по лабораторной работе.

Выбор варианта лабораторной работы

Выбор варианта лабораторной работы осуществляется по общим правилам с использованием следующей формулы:

V = (N × K) div 100,

где    V — искомый номер варианта,

N — общее количество вариантов, div — целочисленное деление,

при V = 0 выбирается максимальный вариант, K — код варианта.

Варианты заданий

Вариант 1

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

Таблица 3.1 — Исходные данные (вариант 1)

Вариант 2

Предприятие выпускает четыре вида продукции и использует три типа основного оборудования: токарное, фрезерное и шлифовальное. Затраты времени на изготовление единицы продукции для каждого из типов оборудования приведены в таблице 3.2. В ней же указаны общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия данного вида. Определить такой объем выпуска каждого из изделий, при котором общая прибыль от их реализации является максимальной.

Таблица 3.2 — Исходные данные (вариант 2)

Вариант 3

Для перевозок груза на трёх линиях могут быть использованы суда трёх типов. Производительность судов при использовании их на различных линиях характеризуются данными, приведёнными в таблице 3.3. В ней же указаны общее время, в течение которого суда каждого типа находятся в эксплуатации, и минимально необходимые объёмы перевозок на каждой линии. Определить, какие суда, на какой линии и в течение какого времени следует использовать, чтобы обеспечить максимальную загрузку судов с учётом возможного времени их эксплуатации.

Таблица 3.3 — Исходные данные (вариант 3)

Вариант 4

Найти решение, состоящее в определении плана изготовления изделий A, B и C, обеспечивающего максимальный их выпуск, в стоимости, выраженной с учётом ограничений на возможное использование сырья трёх видов. Нормы расхода сырья каждого вида на одно изделие, цена одного изделия соответствующего вида, а также имеющегося сырья приведены в таблице 3.4.

Таблица 3.4 — Исходные данные (вариант 4)

Вариант 5

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

Таблица 3.5 — Исходные данные (вариант 5)

Вариант 6

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

Кроме того, сборка изделий требует выполнения определённых сборочно-наладочных работ. Нормы затрат всех видов на изготовление каждого из изделий приведены в таблице 3.6. В этой же таблице указаны наличный фонд каждого из ресурсов, прибыль от реализации единицы продукции данного вида, а также ограничения на возможный выпуск продукции 2-го и 3-го вида.

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

Таблица 3.6 — Исходные данные (вариант 6)

Вариант 7

Для обогрева помещений используются четыре агрегата, каждый из которых может работать на любом из пяти сортов топлива, имеющегося в количествах 90, 110, 70, 80 и 150 т. Потребность в топливе каждого из агрегатов соответственно равна 80, 120, 140 и 160 т. Теплотворная способность i-ого сорта топлива при использовании его на j-ом агрегате задаётся матрицей

Найти такое распределение топлива между агрегатами, при котором получается максимальное количество теплоты от использования всего топлива.

Вариант 8

Изготовляемый на пяти кирпичных заводах кирпич поступает на шесть строящихся объектов. Ежедневное производство кирпича и потребность в нём указаны в таблице 3.7. В ней же указана цена перевозок 1000 шт. кирпича с каждого из заводов к каждому из объектов.

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

Таблица 3.7 — Исходные данные (вариант 8)

Вариант 9

Для поддержания нормальной жизнедеятельности человеку необходимо потреблять не менее 118 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в 1 кг каждого вида потребляемых продуктов, а также цена 1 кг каждого из этих продуктов приведены в таблице 3.8.

Таблица 3.8 — Исходные данные (вариант 9)

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

Вариант 10

Для перевозок трёх видов продукции предприятие использует два типа технологического оборудования и два вида сырья. Нормы затрат сырья и времени на изготовление одного изделия каждого вида приведены в таблице 3.9.

Таблица 3.9 — Исходные данные (вариант 10)

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

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

Вариант 11

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

Таблица 3.10 — Исходные данные (вариант 11)

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

Вариант 12

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

Таблица 3.11 — Исходные данные (вариант 12)

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

Определить план производства продукции мебельной фабрикой, согласно которому прибыль от её реализации является максимальной. Используя пакет PER, найти решение задачи, а также провести послеоптимизационный анализ полученного решения.

Вариант 13

Из трёх видов сырья необходимо составить смесь, в состав которой должно входить не менее 26 ед. химического вещества A, 30 ед. — вещества B и 24 ед. — вещества C. Количество единиц химического вещества, содержащегося в 1 кг сырья каждого вида, указано в таблице 3.12. В ней же приведена цена 1 кг сырья каждого вида.

Составить смесь, содержащую не менее необходимого количества данного вида и имеющую минимальную стоимость.

Таблица 3.12 — Исходные данные (вариант 13)

Вариант 14

Стальные прутья длиной 110 см необходимо разрезать на заготовки длиной 45, 35 и 50 см. Требуемое количество заготовок данного вида составляет соответственно 40, 30 и 20 шт. Возможные варианты разреза и величина отходов при каждом из них приведены в таблице 3.13.

Таблица 3.13 — Исходные данные (вариант 14)

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

Как изменится модель и решение задачи, если из заготовок выпускаются комплекты: 2 заготовки по 45 см, 3 заготовки по 35 см, 1 заготовка по 50 см.

Максимизируется число комплектов. Число прутьев, которое имеется, взять из решения первоначальной задачи. Как при этом изменятся отходы?

Вариант 15

Министерству необходимо составить план развития каждого из m предприятий, выпускающих однородную продукцию. Число возможных вариантов развития i-го предприятия различно и равно n_i. Реализация j-го варианта развития i-го предприятия (j = 1,n) требует капитальных затрат, равных K_ij, и обеспечивает выпуск продукции в объеме b_ij единиц. При этом экономический эффект от капитальных вложений на развитие i-го предприятия по j-му варианту равен c_ij. Учитывая, что необходимо выпустить продукции в количестве B единиц и что общая величина капиталовложений ограничена и равна K, составить такой план развития предприятий, при котором экономический эффект от реализации выбранных вариантов развития предприятий является максимальным.

K = 10  B = 40

Как изменится решение, если К и В уменьшатся на 20 %.

Вариант 16

В аэропорту для перевозки пассажиров по n маршрутам может быть использовано m типов самолётов. Вместимость самолёта i-го типа равна a_i человек, а количество пассажиров, перевозимых по j-му маршруту за сезон, составляет b_i человек. Затраты, связанные с использованием самолёта i-го типа на j-ом маршруте, составляет c_ij руб.

Определить, сколько самолётов данного типа и на каком из маршрутов следует использовать, чтобы удовлетворить потребности в перевозках при наименьших общих затратах.

a₁ = 100  a₂ = 150  a₃ = 200

b₁ = 10 т  b₂ = 20 т  b₃ = 8 т  b₄ = 30 т

Подсчитать количество самолетов каждого типа в оптимальном решении. Как изменится решение, если самолетов 2-го типа есть только 100, а 3-го типа меньше 100.

Вариант 17

Пароход может быть использован для перевозки 11 наименований груза, масса, объём и цена единицы каждого из которых приведены в таблице 3.14.

Таблица 3.14 — Исходные данные (вариант 17)

На пароход может быть погружено не более 800 т груза общим объёмом, не превышающим 600 м³. Определить, сколько единиц каждого груза следует поместить на пароход так, чтобы общая стоимость размещённого груза была максимальной. Как изменится решение, если количество единиц каждого груза ограничено величинами соответственно: 2; 1; 4; 2; 2; 3; 4; 4; 4; 3; 3?

Вариант 18

Из листового проката нужно выкроить заготовки четырёх видов. Один лист длиной 184 см можно разрезать на заготовки длиной 45, 50, 65 и 85 см. Всего заготовок каждого вида необходимо соответственно 90, 96, 88 и 56 шт. Способы разреза одного листа на заготовки и величина отходов при каждом способе приведены в таблице 3.15.

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

Таблица 3.15 — Исходные данные (вариант 18)

Вариант 19

Имеются одинаковые заготовки, которые могут быть раскроены тремя способами. Из имеющихся заготовок нужно получить не менее 10 деталей 1-го типоразмера, не менее 8-ми деталей 2-го типоразмера и не менее 10-ти деталей 3-го типоразмера. Способы раскроя определяются матрицей вида:

Здесь a_ij — количество деталей типоразмера i, получаемое из одной заготовки путём её раскроя способом j.

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

Фирма предполагает продавать выкроенные детали по ценам $4, $6 и $2,5 соответственно для 1-го, 2-го и 3-го типоразмера. При этом потери от процедуры раскроя оцениваются величиной $0,3 на условную единицу отходов. Оптимизируйте процесс раскроя, исходя из соображений получения максимальной прибыли.

Вариант 20

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

Таблица 3.16 — Исходные данные (вариант 20)

Предполагается, что каждый утверждённый проект будет реализован за трёхлетний период.

Требуется выбрать совокупность проектов, которой соответствует максимум суммарной прибыли. Как изменится максимум суммарной прибыли, если максимальный объем капиталовложений уменьшать от 25 до 0 или увеличивать от 25 до бесконечности? Построить график.