Применение методов линейного программирования

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



...

Введение 2
Транспортная задача 3
Задача о назначениях 14
Задача СМО 17
Заключение 20
Литература 21

В работе рассматриваются две задачи линейного программирования (транспортная задача и задача о назначениях), а также одна задача, посвященная системе массового обслуживания (СМО).
В упрощенной формулировке транспортная задача – задача о поиске оптимального плана перевозок грузов из пунктов отправления в пункты потребления [1]. Для решения такой задачи в данной работе используется метод потенциалов [2], который позволяет, отправляясь от некоторого начального допустимого решения, получить оптимальное решение за конечное число итераций.
В наиболее общей форме задача о назначениях формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с нео динаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Задача о назначениях является частным случаем транспортной задачи, поэтому, в принципе, для ее решения можно использовать любой алгоритм линейного программирования, однако наиболее эффективным оказывается венгерский метод. Этот метод основан на двух основных идеях:
1. Если из всех элементов строки или столбца матрицы стоимости (затрат) вычесть одно и то же число , общая стоимость работ уменьшится на , а искомое оптимальное решение не изменится
2. Если есть решение нулевой стоимости, то оно оптимально
Наконец, задача СМО – задача рационального выбора структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящие из нее, длительности ожидания и длины очередей. При этом используются методы теории вероятности и математической статистики. В данной работе рассматривается задача многоканальной СМО без ожидания (система с отказами).

2[200]
6
u3=1
6
5[300]
4[0]
5
u4=2
4[100]
6[0]
7
6[200]
u5=-4
0[100]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;2):
0 + 4 > 3; ∆12 = 0 + 4 - 3 = 1
Выбираем максимальную оценку свободной клетки (1;2): 3. Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»:
 
1
2
3
4
Запасы
1
2[100][-]
3[+]
4
5
100
2
2
4
2[200]
6
200
3
6
5[300]
4[0]
5
300
4
4[100][+]
6[0][-]
7
6[200]
300
5
0[100]
100
Потребности
200
300
200
300
 
Цикл приведен в таблице (1,2 → 1,1 → 4,1 → 4,2). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е.
у = min (4, 2) = 0
Прибавляем 0 к объемам грузов, стоящих вплюсовых клетках и вычитаем 0 из xij, стоящих в минусовых клетках. В результате получим новый опорный план:
 
1
2
3
4
Запасы
1
2[100]
3[0]
4
5
100
2
2
4
2[200]
6
200
3
6
5[300]
4[0]
5
300
4
4[100]
6
7
6[200]
300
5
0[100]
100
Потребности
200
300
200
300
 
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0:
u1 + v1 = 2; 0 + v1 = 2; v1 = 2
u4 + v1 = 4; 2 + u4 = 4; u4 = 2
u4 + v4 = 6; 2 + v4 = 6; v4 = 4
u5 + v4 = 0; 4 + u5 = 0; u5 = -4
u1 + v2 = 3; 0 + v2 = 3; v2 = 3
u3 + v2 = 5; 3 + u3 = 5; u3 = 2
u3 + v3 = 4; 2 + v3 = 4; v3 = 2
u2 + v3 = 2; 2 + u2 = 2; u2 = 0
 
v1=2
v2=3
v3=2
v4=4
u1=0
2[100]
3[0]
4
5
u2=0
2
4
2[200]
6
u3=2
6
5[300]
4[0]
5
u4=2
4[100]
6
7
6[200]
u5=-4
0[100]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (3;4):
2 + 4 > 5; ∆34 = 2 + 4 - 5 = 1
Выбираем максимальную оценку свободной клетки (3;4): 5. Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-»:
 
1
2
3
4
Запасы
1
2[100][-]
3[0][+]
4
5
100
2
2
4
2[200]
6
200
3
6
5[300][-]
4[0]
5[+]
300
4
4[100][+]
6
7
6[200][-]
300
5
0[100]
100
Потребности
200
300
200
300
 
Цикл приведен в таблице (3,4 → 3,2 → 1,2 → 1,1 → 4,1 → 4,4). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е.
у = min (1, 1) = 100
Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из xij, стоящих в минусовых клетках. В результате получим новый опорный план:
Таблица №1.2
 
1
2
3
4
Запасы
1
2
3[100]
4
5
100
2
2
4
2[200]
6
200
3
6
5[200]
4[0]
5[100]
300
4
4[200]
6
7
6[100]
300
5
0[100]
100
Потребности
200
300
200
300
 
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0:
u1 + v2 = 3; 0 + v2 = 3; v2 = 3
u3 + v2 = 5; 3 + u3 = 5; u3 = 2
u3 + v3 = 4; 2 + v3 = 4; v3 = 2
u2 + v3 = 2; 2 + u2 = 2; u2 = 0
u3 + v4 = 5; 2 + v4 = 5; v4 = 3
u4 + v4 = 6; 3 + u4 = 6; u4 = 3
u4 + v1 = 4; 3 + v1 = 4; v1 = 1
u5 + v4 = 0; 3 + u5 = 0; u5 = -3
 
v1=1
v2=3
v3=2
v4=3
u1=0
2
3[100]
4
5
u2=0
2
4
2[200]
6
u3=2
6
5[200]
4[0]
5[100]
u4=3
4[200]
6
7
6[100]
u5=-3
0[100]
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят:
F = 3·100 + 2·200 + 5·200 + 5·100 + 4·200 + 6·100 + 0·100 = 3600
Анализ оптимального плана
С 1-го склада необходимо весь объем напитков (100 л) направить во 2-й магазин.
Со 2-го склада необходимо весь объем напитков (200 л) направить в 3-й магазин.
С 3-го склада необходимо 200 л направить во 2-й магазин и 100 л направить в 4-й магазин.
С 4-го склада необходимо 200 л направить в 1-й магазин и 100 л направить в 4-й магазин.
Потребность 4-го магазина остается неудовлетворенной на 100 л.
Мы решили транспортную задачу без учета каких-либо дополнительных требований. Рассмотрим теперь следующие ограничения.
(а) Объем напитков, поставляемый в третий супермаркет с третьего склада не должен превышать 100 л. Как видно, найденный план перевозок, представленный в табл.№1.2, и по которому в 3-й магазин с 3-го склада не приходит ничего, удовлетворяет этому условию.
(б) Объем продукции, поставляемый во второй магазин с четвертого склада должен быть не менее 100 л. Как видно, найденный план перевозок, представленный в табл.№1.2, не удовлетворяет этому условию. В табл.№1.3 представлен план перевозок (самый первый план, который мы нашли), который удовлетворяет этому условию. Минимальные затраты составят:
F = 2·100 + 2·100 + 2·100 + 5·200 + 4·100 + 6·100 + 6·200 + 0·100 = 3800
Таблица №1.3
 
1
2
3
4
Запасы
1
2[100]
3
4
5
100
2
2[100]
4
2[100]
6
200
3
6
5[200]
4[100]
5
300
4
4
6[100]
7
6[200]
300
5
0[100]
100
Потребности
200
300
200
300
 
Задача №2
Дано:
Таблица №2.1
7
10
8
11
7
15
12
1
2
5
6
10
18
4
8
11
9
2
16
3
6
5
2
5
14
3
10
5
8
7
6
7
13
8
14
6
8
17
10
11
9
5
15
18
5
9
12
6
10
Поскольку в условии задачи не указан тип оптимальности, будем решать задачу на минимум. Решение ищем, используя венгерский метод.
Проводим редукцию матрицы по строкам. В каждой строке исходной матрицы ищем минимальный элемент и отнимаем его от всех элементов строки:
3
1
4
8
5
7
1
4
5
9
17
3
1
6
9
7
14
1
4
2
3
3
12
1
8
3
2
2
1
1
7
2
8
6
1
3
12
5
6
4
5
10
13
4
7
1
5
5
Затем такую же операцию редукции проводим по столбцам, получая в итоге полностью редуцированную матрицу:
3
1
4
7
5
1
4
5
9
16
3
6
9
7
14
4
3
3
12
1
7
3
2
1
1
7
1
8
1
3
12
5
6
3
10
13