Q Задача об аренде оборудования: постановка задачи и методы решения

СЫКТЫВКАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Математический факультет

Кафедра геометрии, алгебры и математической статистики

q Задания к контрольной работе для студентов заочного обучения

q Методические указания к контрольным заданиям

Q Пример решения транспортной задачи

Q Задача об аренде оборудования: постановка задачи и методы решения

Сыктывкар 2010

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

Даются варианты контрольного задания для студентов заочного отделения финансово-экономического факультета и факультета управления.

Составитель: доцент кафедры ГАМС А.А.Холопов

С О Д Е Р Ж А Н И Е

1. КОНТРОЛЬНЫЕ ЗАДАНИЯ........................................... 4

Задание 1. Задача о выпуске продукции при ограниченных ресурсах. 5

Задание 2. Классическая транспортная задача......................... 7

Задание 3. Задача об аренде оборудования.................................. 11

2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ ЗАДАНИЙ 18

Задача о выпуске продукции при ограниченных ресурсах... 18

Классическая транспортная задача......................................... 19

Задача об аренде оборудования.................................................. 19

3. ПРИМЕР РЕШЕНИЯ КЛАССИЧЕСКОЙ ТРАНСПОРТНОЙ ЗАДАЧИ 20

4. ЗАДАЧА ОБ АРЕНДЕ ОБОРУДОВАНИЯ................................ 29

Планы аренды. Постановка задачи........................................... 29

Сетевая модель задачи и ее решение......................................... 29

Табличный метод решения задачи.............................................. 31

Рекомендуемый библиографический список 33

ПРИЛОЖЕНИЕ. Бесконтурные сети...................... ... 34

КОНТРОЛЬНЫЕ ЗАДАНИЯ

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

Две последние цифры № зачетной книжки, студ. Билета	Вариант	Две последние цифры № зачетной книжки, студ. Билета	Вариант
01, 31, 61, 91 02, 32, 62, 92 03, 33, 63, 93 04, 34, 64, 94 05, 35, 65, 95 06, 36, 66, 96 07, 37, 67, 97 08, 38, 68, 98 09, 39, 69, 99 10, 40, 70, 100 11, 41, 71 12, 42, 72 13, 43, 73 14, 44, 74 15, 45, 75		16, 46, 76 17, 47, 77 18, 48, 78 19, 49, 79 20, 50, 80 21, 51, 81 22, 52, 82 23, 53, 83 24, 54, 84 25, 55, 85 26, 56, 86 27, 57, 87 28, 58, 88 29, 59, 89 30, 60, 90

На титульном листе контрольной работы необходимо указать фамилию, имя, отчество, номер группы, специальность, номер зачетной книжки (студенческого билета), номер варианта. В разделе 2 даются методические указания по выполнению заданий 1– 3 и рекомендации по оформлению решений. В разделе 3 дается пример решения классической транспортной задачи (задание 2). В разделе 4 дается необходимый теоретический материал для выполнения задания 3 – задачи об аренде оборудования и дается пример решения.

Задание 1. Задача о выпуске продукции при ограниченных ресурсах.

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

Записать задачу в виде задачи линейного программирования и решить ее графическим методом. Дать экономическую интерпретацию полученного решения.

Вариант

Вариант

Задание 2. Классическая транспортная задача.

Имеются три пункта , , поставки однородного груза и четыре пункта , , , потребления этого груза. На пунктах находится груз соответственно в количестве , и тонн. В пункты , , , требуется доставить соответственно , , , тонн груза. Цены перевозок (стоимости провоза единицы груза) в условных единицах между пунктами поставки и пунктами потребления приведены в следующей матрице-таблице C:

Пункты поставки	Пункты потребления

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

Изобразить оптимальный план перевозок в виде графа (без фиктивных потребителей и складов !).

Вариант 01

Вариант 02

Вариант 03

Вариант 04

Вариант 05

Вариант 06

Вариант 07

Вариант 08

Вариант 09

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15

Вариант 16

Вариант 17

Вариант 18

Вариант 19

Вариант 20

Вариант 21

Вариант 22

Вариант 23

Вариант 24

Вариант 25

Вариант 26

Вариант 27

Вариант 28

Вариант 29

Вариант 30

Задание 3. Задача об аренде оборудования.

Рассматривается дискретная задача об аренде оборудования на 6 месяцев. Стоимости аренды от начала i-го месяца до начала j-го месяца в условных единицах даны в таблице. (Постановку задачи об аренде оборудования и методы ее решения смотри ниже в разделе 3). Требуется найти все оптимальные планы аренды методом потенциалов или на сетевой модели или табличным способом.

Вариант 1

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 2

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 3

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 4

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 5

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 6

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 7

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 8

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 9

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 10

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 11

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 12

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 13

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 14

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 15

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 16

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 17

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 18

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 19

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 20

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 21

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 22

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 23

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 24

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 25

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 26

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 27

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 28

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 29

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

Вариант 30

Cij	j=2	j=3	j=4	j=5	j=6	j=7
i=1
i=2	–
i=3	–	–
i=4	–	–	–
i=5	–	–	–	–
i=6	–	–	–	–	–

ПРИМЕР РЕШЕНИЯ КЛАССИЧЕСКОЙ ТРАНСПОРТНОЙ ЗАДАЧИ.

Замечание.Это пример решения транспортной задачи одним студентом – заочником. Решение излишне подробное.Достаточно было изображать по одной таблице с потенциалами на каждом шаге.

Кроме того, при изображении оптимального графа перевозок фиктивного потребителя (№ 5) изображать не нужно было, а нужно было указать остатки товара у 3-го склада (остаток равен 145) А.А.Холопов

Исходные данные (запасы, потребности и цены)

Поставщик	Потребитель	Запасы
В1	В2	В3	В4
A1
A2
A3
Потребность

Транспортная задача является открытой, так как запас груза больше потребностей на 145 единиц. Приведем задачу к закрытому типу - введем фиктивного потребителя B₅.

Находим начальный базисный план (он содержит 3+5 –1=7 заполненных клеток).

План найден методом минимальной стоимости.

Начальный план

Поставщик	Потребитель	Запасы
В1	В2	В3	В4	В5
A1
A2
A3
Потребность

Стоимость перевозок = 14*146+…+ 39*195 = 17870.

Решаем задачу методом потенциалов.

Й этап.

Полагая потенциал U₁ = 0, определяем остальные потенциалы из соотношения

,

просматривая все занятые клетки.

Потенциалы:

Определяем значения оценок, для всех свободных клеток:

.

Значения оценок

	В1	В2	В3	В4	В5
A1
A2		-7			-10
A3					-15

Выделенные оценки не являются оптимальными, а именно:

Наиболее неоптимальной оценкой, из этих двух, является оценка , т.к. максимальная по модулю оценка.

Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".

План грузоперевозок

Наши рекомендации

Поставщик	Потребитель	Потенциалы Ui
В1	В2	В3	В4	В5
A1