Оглавление
Задача №1 2
Задача №2 3
Задача №3 9
Задача №4 13
Задача №5 15
Список литературы 16
Задача №1
Нефтеперерабатывающая установка может работать в двух различных режимах. При работе в первом режиме из одной тонны нефти производится 300 кг темных и 10*76*760 кг светлых нефтепродуктов; при работе во втором режиме - 700 кг темных и 200 кг светлых нефтепродуктов. Ежедневно на этой установке необходимо производить 2*76=152 т темных и 76 т светлых нефтепродуктов. Это плановое задание необходимо ежедневно выполнять, расходуя минимальное количество нефти.
Вопросы:
1. Сколько тонн нефти следует ежедневно перерабатывать в первом режиме?
2. Сколько тонн нефти следует ежедневно перерабатывать во втором режиме?
3. Каков минимальный ежедневный расход нефти?
Решение: Составим модель решения для использования в решении задачи надстройки Excel Поиск решения.
Целевую ячейку установим на сумме переработанных нефтепродуктов на 1 первом х1 и 2 - х2 режимах. Тогда целевая ячейка равна х1 + х2>min.
Ограничением будет служить следующие уравнения
300х1 +700 х2=152000
700х1 +200 х2=76000
То есть необходимая производственная программа выполняется на двух режимах.
В результате выполнения операции Поиск решения получаем следующие ответы на вопросы.
Следует ежедневно перерабатывать в первом режиме 48,3 тонн нефти.
Следует ежедневно перерабатывать во втором режиме 136,4 тонн нефти.
Минимальный ежедневный расход нефти при этом 244,7 тонн.
Задача №2
Компания контролирует три фабрики F1, F2, F3, способные производить f1, f2, f3 тыс. изделий еженедельно. Она заключила с четырьмя заказчиками C1, C2, C3, C4, которым требуется еженедельно с1, с2, с3, с4 тыс. изделий. Стоимости производства и транспортировки 1 тыс. изделий заказчика с фабрикой приведены в таблице.
Определите минимизирующую общую стоимость объема производства и распределение для каждой из фабрик.
Таблица 1
Фабрики
Заказчики
Мощности поставок
C1
C2
C3
C4
F1
76
85
60
55
f1 =20
F2
50
71
45
70
f2 =30
F3
65
80
75
66
f3 =50
Нужды потребителей
с1 =10
с2 =20
с3 =40
с4 =30
Предложение равно спросу 100
Потребности новых районов застройки города 10 +20+40+30= 100, в то время как мощности поставок составляют 20+30+50= 100
Следовательно, это задача замкнутая.
Рассмотрим закрытую транспортную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения.
Транспортная задача как задача линейного программирования может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения этого класса задач разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:
* нахождение исходного опорного решения;
* проверка этого решения на оптимальность;
* переход от одного опорного решения к другому.
Рассмотрим один из них - метод минимального тарифа (элемента). Согласно этому методу, мощности распределяются в первую очередь в те клетки, в которых находится минимальное расстояние. Далее загрузка распределяются в незанятые клетки с наименьшими затратами с учетом оставшихся мощностей и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все емкости не будут заняты, а потребители не будут удовлетворены.
Таблица исходной транспортной задачи имеет следующий вид.
Фабрики
Заказчики
Мощности поставок
C1
C2
C3
C4
F1
76
85
60
55
f1 =20
F2
50
71
45
70
f2 =30
F3
65
80
75
66
f3 =50
Нужды потребителей
с1 =10
с2 =20
с3 =40
с4 =30
Предложение равно спросу 100
bij
1
2
3
4
aij
10
20
40
30
1
20
76
85
60
55
20
2
30
50
71
45
70
30
3
50
65
80
75
66
10
20
10
10
Число занятых клеток в таблице равно 6, 4+3-1=6, т. е. условие невырожденности выполнено. Получим исходное опорное решение, которое запишем в виде матрицы:
Общие затраты при исходном опорном решении составляет С= 55*20 + 45*30 + 65*10 +80*20 +75*10+66*10 = 6110 усл. ед.
Проверка решения на оптимальность
Найденное исходное опорное решение проверяется на оптимальность методом потенциалов.
Числа vj и ui называют потенциалами. В распределительную таблицу добавляют строку v и столбец u. Потенциалы находят из равенства ui + vj = cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например, u1 = 0, тогда остальные потенциалы определяются однозначно.
bij
1
2
3
4
ui
aij
10
20
40
30
1
20
76
85
60
55
0
20
2
30
50
71
45
70
-19
30
3
50
65
80
75
66
11
10
20
10
10
vj
54
69
64
55
Полагаем u1 = 0, запишем это значение в последнем столбце первой строки таблицы. Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (1, 1), для нее выполняется условие u1 + v1 =4. Отсюда при u1 = 0 получаем, что v1 = 76, это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которых один из потенциалов известен.