close

Вход

Забыли?

вход по аккаунту

?

577.Аснина Н.Г. Исследование операций и методы оптимизации

код для вставкиСкачать
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Воронежский государственный архитектурно-строительный университет»
Н.Г. Аснина
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И МЕТОДЫ
ОПТИМИЗАЦИИ
Практикум
2-е издание, переработанное и дополненное
Рекомендовано редакционо-издательским советом
Воронежского государственного архитектурно-строительного университета
в качестве учебного пособия для студентов, обучающихся по направлению 230700
«Прикладная информатика»
Воронеж 2012
1
УДК 519.863(073)
ББК 65.050 я7
А90
Аснина, Н.Г.
А90
Исследование операций и методы оптимизации : практикум
/ Н.Г. Аснина; Воронежский ГАСУ. - 2 изд., перераб. и доп.Воронеж, 2012. - 68с.
ISBN
Изложен краткий теоретический материал по следующим разделам линейного программирования: графическое решение ЗЛП, каноническая форма
ЗЛП, базисное решение, симплекс-метод, двойственность в ЗЛП, транспортная
задача; и теории расписаний: задача о назначениях, системы конвейерного типа
с двумя и более приборами.
Приведены основные алгоритмы решения задач в указанных разделах.
Разобраны типовые примеры применения алгоритмов. Представлены контрольные задания для самостоятельного выполнения по каждой теме.
Предназначено для студентов 3 курса дневного отделения, обучающихся
по направлению 230700 «Прикладная информатика».
Ил. 45. Табл. 37. Библиогр.: 9 назв.
УДК 519.863(073)
ББК 65.050 я7
Рецензенты: кафедра менеджмента и мировой экономики Воронежского
филиала Российского государственного торговоэкономического университета;
З.А. Шабунина, канд. физ.-мат. наук, доцент кафедры вычислительной математики и прикладных информационных технологий Воронежского государственного университета
© Аснина Н.Г., 2012
© Воронежский ГАСУ, 2012
ISBN 978-5-89040-389-6
2
Введение
Курс «Исследование операций и методы оптимизации» является важной
составляющей экономико-математического образования студентов, обучающихся по направлению «Прикладная информатика».
Данный практикум является переработанным и дополненным изданием
практикума по курсу «Оптимизационные задачи в экономике» в соответствии с
требованиями Федерального государственного образовательного стандарта
третьего поколения к дисциплине «Исследование операций и методы оптимизации».
Круг вопросов, рассматриваемых в предлагаемом практикуме, включает в
себя раскрытие понятий и методов математического моделирования социальноэкономических систем и процессов. Рассматриваются задачи линейной оптимизации, а также решение дискретных задач, в том числе NP- трудных. Подробно,
на примере конкретного задания по каждой теме, описана последовательность
проведения расчётов, представлены алгоритмы решения.
Предлагаемый практикум состоит из пяти разделов. Первый раздел посвящен постановке задачи линейного программирования, графическому методу
ее решения, а так же основным понятиям ЛП, во втором разделе разобран симплекс-метод и симплекс-метод с искусственным базисом решения ЗЛП, третий
раздел посвящен двойственности в задачах ЛП, четвертый - транспортной задаче. В пятом разделе разбираются основные понятия теории расписаний, рассматриваются методы решения задачи о назначениях, а так же системы конвейерного типа с двумя, тремя и более приборами. В начале каждого тематического раздела даны необходимые теоретические сведения, закладывающие основы
знаний по принципам решения задач, и типовые примеры. Затем идут задания
для самостоятельной работы в виде лабораторных работ.
После изучения на практических занятиях каждого метода, студент должен выполнить индивидуальную лабораторную работу, используя соответствующий алгоритм и представить отчет.
Такая структура глав поддерживает методику преподавания, выстраивая
логику изучения каждой темы курса в строго определенном порядке: провед ение лекционных занятий с осуществлением контроля усваемости материала и
закреплением полученных знаний путем выполнения аналитических заданий.
В результате изучения данного курса студенты должны знать основные
математические методы, применяемые при решении экономических задач,
уметь разрабатывать алгоритмы и пользоваться ими при реализации соответствующих методов.
3
1. Общая постановка задачи линейного программирования.
Графическое решение ЗЛП. Каноническая форма.
Базисное решение
1.1. Основные определения
Задачей линейного программирования (ЗЛП) называется задача вида
a11 x1
a12 x 2
...a1n x n
( )b1 ;
a 21 x1
a 22 x 2
...a 2 n x n
( )b2 ;
.............................................
a m1 x1 a m 2 x 2 ...a m n x n ( )bm ;
xj
(1.1.2)
0, ( j 1, n)
f ( x)
c1 x1
c2 x2
(1.1.1)
...c n x n
min
(max)
(1.1.3)
Система неравенств (1.1.1) называется системой ограничений задачи.
Неравенства (1.1.2) – условие не отрицательности переменных. Функция
(1.1.3) – функция цели (целевая функция).
x1
Вектор x
x2

xn
, удовлетворяющий неравенствам (1.1.1) и (1.1.2), называ-
ется планом задачи линейного программирования или допустимым вектором,
или допустимым решением.
Множество всех допустимых векторов x будем обозначать буквой G и
называть допустимым множеством или множеством планов.
Вектор x* G называется оптимальным решением или оптимальным планом, если для всех x G : f ( x* ) f ( x) ( f ( x* ) f ( x) ).
Если оптимальное решение может быть найдено, то задача называется
разрешимой, если же оптимального решения не существует, то задача называется неразрешимой.
Причины, по которым не может быть найдено оптимальное решение:
1. Функция f (x) на допустимом множестве G неограниченна. Эта задача
называется неразрешимой из-за неограниченности целевой функции.
2. Допустимое множество G пусто ( G
), то есть не существует допустимых решений.
Такая задача называется несовместимой.
4
1.2. Графический метод решения задачи линейного программирования
Если задача линейного программирования имеет две переменные x1 и x2,
то ее можно решить графически.
Решение задачи происходит в два этапа.
На первом этапе необходимо на плоскости изобразить допустимое множество, а на втором найти оптимальную точку, если она существует, в противном случае убедиться в неразрешимости задачи.
Этап 1. Построение допустимого множества
Каждое неравенство в рассматриваемой задаче представляет собой полуплоскость, а допустимое множество – пресечение этих полуплоскостей. Если
неравенства в задаче заменить уравнениями, то получим уравнения прямой.
Каждую прямую можно построить по двум точкам. Для того чтобы выделить
необходимую полуплоскость, надо взять точку, не лежащую на прямой, и подставить ее координаты в левую часть неравенства. Если неравенство выполнено, то выбираем полуплоскость, содержащую данную точку, в противном случае - другую полуплоскость.
Так как в ограничениях присутствуют ограничения неотрицательности
переменных, то рассматриваем только первый координатный угол.
Если правая часть не равна нулю, то в качестве пробной точки удобнее
всего выбрать начало координат (0,0).
Алгоритм выполнения первого этапа
Шаг 1: Выделение первого координатного угла.
Шаг 2: i 1 .
Шаг 3: i-е неравенство записывается как уравнение.
Шаг 4: Полагаем, x11 0, x12 находим из уравнения.
Шаг 5: Полагаем, x 22
Шаг 6: Через точку x1
0, x12 находим из уравнения.
x11
x12
x12
и x2
x22
проводится прямая.
Шаг 7: В левую часть неравенства подставляется точка с координатами
(0,0) . Если неравенство выполнено, то выбирается полуплоскость, содержащая
начало координат, в противном случае - противоположная полуплоскость.
Шаг 8: Если i m , то i i 1 , переходим к Шагу 3, иначе Шаг 9.
Шаг 9: Допустимое множество получено. Если оно пустое ( G
), то
выписывается ответ: «Задача несовместна», иначе переход к Этапу 2.
Этап 2: Поиск оптимальной точки
Рассмотрим градиент функции f (x) . Так как функция f (x) линейна, то
ее градиент есть постоянный вектор с координатами Grad ( f )
5
c1
c2
.
Известно, что движение в направлении градиента увеличивает значение
функции.
Прямая, перпендикулярная вектору-градиенту, называется линией уровня,
так как значения функции f (x) в любой точке этой прямой одинаковы.
Алгоритм выполнения второго этапа
Шаг 1: Строится вектор градиент Grad ( f ) c1 , c2 Ò .
Шаг 2: Кладется линейка перпендикулярно вектору–градиенту.
Шаг 3: Линейка сдвигается параллельно самой себе по направлению вектора-градиента, пока хотя бы одна точка соответствующей прямой принадлежит допустимому множеству.
Шаг 4: Если при любом положении линейки перпендикулярно векторуградиенту имеются точки допустимого множества, то выписывается ответ: «Задача неразрешима из-за неограниченности целевой функции» и переход к Шагу
10. Иначе Шаг 5.
Шаг 5: Находится последняя точка допустимого множества, лежащая на
соответствующей линии уровня.
Шаг 6: Если эта точка неединственная, то выбирается точка, которая является пересечением двух прямых, ограничивающих допустимое множество.
Шаг 7: Выписывается система двух уравнений с двумя неизвестными.
Шаг 8: Из системы уравнений находится оптимальная точка x* ( x1* , x2* ) .
Шаг 9: Находится оптимальное значение целевой функции
*
f ( x ) c1 x1* c2 x2* .
Шаг 10. Конец.
Пример 1.1. Решить задачу линейного программирования графически.
(1.2.1)
2 x1 3x2 18 ,
(1.2.2)
x1 3x2 9 ,
(1.2.3)
2x1 x2 10 ,
x1
0,
x2
0,
f ( x)
4 x1
2 x2
max .
Решение. Строим допустимое множество в соответствии с первым этапом
алгоритма. В результате получаем ограниченную многогранную область (рис. 1.1).
6
x2
(3)
5
2
A( 6,2)
gra
(2)
x1
d
(1)
-10
-10
Рис. 1.1
В табл. 1.1 заданы точки, по которым строятся прямые (1.2.1)-(1.2.3).
(1.4.1)
x1
x2
0
6
(1.4.2)
9
0
0
3
-9
0
Таблица 1.1
(1.4.3)
0
5
-10
0
В качестве пробной кочки выбираем начало координат (0, 0).
Для (1.2.1) 2 0 3 0 18 . (Верно: выбирается полуплоскость, содержащая
начало координат.)
Для (1.2.2) 0 3 0 9 . (Верно: выбирается полуплоскость, содержащая
начало координат.)
Для (1.2.3) 2 0 0 10 . (Верно: выбирается полуплоскость, содержащая,
начало координат.)
На Этапе 2 находим Grad ( f )
4
.
2
Сдвигаясь по линии уровня в направлении вектора-градиента, получаем
оптимальную точку А, находим ее координаты. Так как она является точкой пересечения прямых (1.2.1) и (1.2.3), то решаем систему уравнений:
2 x1 3x2
2 x1
x2
18,
10,
x1
6,
x2
2.
Таким образом, оптимальной точкой x является точка x
6
.
2
Находим оптимальное значение целевой функции, подставляя значение
x в функцию:
f (x ) 24 4 28 .
Пример 1.2. Решить графически следующую задачу:
3x1 2 x2 11 ,
7
2 x1 x2 2 ,
x1 3x2 0 ,
x1 0, x2 0 ,
f ( x) 2 x1 4 x2 max .
Решение. Построение допустимого множества выполняется так же, как и в
предыдущей задаче (рис. 1.2). В результате получаем неограниченную многогранную область.
Рис. 1.2
На втором этапе решения параллельным перемещением по линиям уровня
в направлении вектора-градиента устанавливаем, что такое перемещение можно
производить неограниченно. Следовательно, целевая функция неограниченна
сверху, т.е. f (x) max
, а сама задача линейного программирования неразрешима из-за неограниченности целевой функции. Заметим, что если при тех же
исходных данных требовалось бы целевую функцию минимизировать, то полу*
(3,1) с f ( x)*min 10 .
чили бы оптимальное решение в точке xmin
Пример 1.3. Решить задачу
(1.2.4)
x1 x2 3,
(1.2.5)
x1 2x2 3,
x1
f ( x)
0, x2
x1 x2
0,
max .
Решение. Допустимое множество в данной задаче имеет вид (рис. 1.3).
Рис. 1.3
Из рисунка видно, что допустимое множество неограниченно, однако оптимальное решение существует, им является луч, выходящий из точки x1max . Линии
8
уровня целевой функции параллельны прямой x1 x2 3 , соответствующей
первому ограничению. При перемещении линии уровня в направлении вектораградиента получаем, что линия уровня с максимально возможным значением целевой функции совпадает с прямой: x1 x2 3 . Таким образом, целевая функция достигает своего максимального значения f ( x)*max
3 во всех точках луча,
(0, 3) . Задача имеет бесчисленное множество реше-
выходящего из точки x1max
ний.
Для того чтобы выписать решение в общем виде, возьмем на луче еще одну
2
точку xmax
(1, 4) . Уравнение луча записывается следующим образом:
*
2
xmax
(1 ) x1max
xmax
,
[0, ) .
Таким образом, любое решение данной задачи записывается в виде
*
xmax ( ,3
),
[0, ) .
Лабораторная работа №1
Решить задачу линейного программирования графически.
a11x1 a12 x2 b1 ,
a21x1 a22 x2 b2 ,
a31x1 a32 x2 b3 ,
x1 0, x2 0 ,
f ( x) c1 x1 c2 x2
max .
В табл. 1.2 представлены варианты возможных ограничений и целевых
функций.
Таблица 1.2
№
1
2
3
4
5
6
7
8
9
10
Ограничения
2 x1 3x2 18
x1 3x2 9
2x1 x2 10
x1
x2
2
№
1
2
3
4
Целевая функция
f ( x) 4 x1
f ( x) 3x1
f ( x) 2 x1
f ( x) 5x1
4 x1 3x2 12
4 x1 3x2 12
x1 2 x2 6
2 x1
x2
8
2 x1 x2 4
x1 2 x2 6
Общее ограничение
x1, 2
0
В табл.1.3 приведены варианты заданий.
9
2 x2
x2
5x2
2 x2
Таблица 1.3
Номер
варианта
1
2
3
4
5
6
7
8
9
10
Ограничения
1, 2, 5
1, 2, 8
1, 4, 5
1, 2, 4
1, 5, 10
2, 3, 4
2, 3, 6
1, 4, 8
1, 3, 6
2, 4, 8
Целевая
функция
1
2
3
4
1
2
3
4
1
2
Номер
варианта
11
12
13
14
15
16
17
18
19
20
Ограничения
2, 5, 8
2, 4, 5
1, 4, 5
1, 4, 6
2, 3, 4
3, 4, 6
1, 6, 10
6, 7, 8
4, 5, 7
1, 4, 6
Целевая
функция
3
4
1
2
3
4
1
2
3
4
1.3. Каноническая форма задачи линейного программирования.
Приведение к канонической форме
Задача линейного программирования называется задачей в канонической
форме, если она имеет вид
Ax b ,
b 0,
x 0,
f ( x) c T x max .
Приведение к канонической форме:
1. Если bi 0 , то соответствующее ограничение умножается на (-1). При
этом если соответствующее ограничение – неравенство, то знак неравенства
меняется на противоположный.
2. Если
~
f ( x) ñT x min ,
то функция заменяется на следующую:
~
f ( x)
f ( x)
ñT x max .
3. Если имеется неравенство
aiT x bi ,
то оно заменяется уравнением
aiT x xiä bi , при xiд 0 и сiд 0 .
Если имеется неравенство
aiT x bi ,
то оно заменяется уравнением
aiT x xiä bi , при xiд 0 и сiд 0 .
Переменная xiд называется дополнительной переменной и показывает, на
сколько левая часть неравенства отличается от правой.
Пример 1.3. Привести ЗЛП к каноническому виду.
10
2 x1
x2
3x3
x1
x2
x3
2 x1 3x2
4 x4
x4
x3
x4
x j 0, j 1,4 ,
~
f ( x) 5 x1 x2 x3 7 x4
3,
1,
2,
min .
1.Устранение неотрицательных чисел в правой части:
2 x1 x2 3x3 4 x4 3 ,
x1 x2 x3 x4 1,
2 x1 3x2 x3 x4 2 ,
x j 0, j 1,4 ,
~
f ( x) 5 x1 x2 x3 7 x4
min .
2. Изменение целевой функции:
2 x1 x2 3x3 4 x4 3 ,
x1 x2 x3 x4 1,
2 x1 3x2 x3 x4 2 ,
x j 0, j 1,4 ,
f ( x)
5 x1 x2 x3 7 x4
max .
3,4. Замена неравенств в ограничениях равенствами:
2 x1 x2 3x3 4 x4 x1ä 3 ,
x1 x2 x3 x4 1,
2 x1 3x2 x3 x4 x3д 2 ,
x j 0, j 1,4 ,
x1д 0, x3д 0 ,
f ( x)
5 x1 x2 x3 7 x4
max .
Это окончательный вид ЗЛП.
Заметим, что в соответствующем примере есть первая и третья дополнительные переменные. Для удобства номер дополнительной переменной соответствует номеру строки, в которой она присутствует.
В дальнейшем почти всегда ЗЛП будут рассматриваться только в канонической форме.
1.4. Базисное решение ЗЛП
Рассмотрим ЗЛП в каноническом виде.
Ax b,
x 0,
f ( x)
(1.4.1)
max , где
cT x
11
Am n , m n .
Будем считать, что rang( A) m , то есть матрица А имеет m линейно независимых столбцов. Допустимое решение x ( x1 , x2 , ... , xm ,0,0) , x G называется базисным решением или опорным планом, если положительным значениям xi соответствуют линейно независимые столбцы матрицы А.
Базисное решение имеет не больше, чем m положительных компонент.
Если число положительных компонент равно m, то решение называется невырожденным, и соответствующие столбцы матрицы А образуют базис в m-мерном пространстве. Если число положительных компонент меньше m, то решение называется вырожденным. Тогда, чтобы получить базис, к тем столбцам, которые соответствуют положительным компонентам, надо добавить столбцы с нулевыми
компонентами.
Сформулируем без доказательства.
Утверждение 1: Если ЗЛП разрешима, то для нахождения оптимального
решения достаточно перебрать только базисные решения, число которых конечно и не превосходит Сnm .
Рассмотрим сначала способ перестроения базисного решения системы
Ax b без условия неотрицательности.
Пусть матрица А имеет вид
~
A E| A ,
где Е – единичная матрица.
Обозначим через I B множество номеров единичных столбцов матрицы А
и через I A~ множество остальных номеров столбцов. Вектор X представим в виде x
xB
x A~
в виде cT
, где xB
( xi ), i
I B и x A~
( xi ), i
I A~ . Вектор c T представим
(cBT , cTA~ ) . Тогда система примет вид
xB
Если положить x A~
~
Ax A~
b.
0 , то получим базисное решение x
b
.
0
Будем получать новое базисное решение, заменяя один из базисных
столбцов на столбец, ранее принадлежащий I A~ . Это можно сделать с помощью
алгоритма Жордана-Гаусса.
Пусть выбрано k I A~ (номер столбца, который будет вводиться в базис)
и alk - направляющий элемент.
Шаг 1: l-строка делится на направляющий элемент.
В новой итерации эта строка будет иметь номер k.
akjí ali / alk
l ,
í
xk xl / alk
,
12
0.
alk
Шаг 2:
Для i
k
aijí
aij
í
i
xi
x
Шаг 3:
I
I
í
~
A
í
B
,
aik .
aik
j
{k} ,
( I B \{l})
( I A~\{k})
{l} .
1.5. Перестроение базисного решения ЗЛП
Алгоритм Жордана-Гаусса не учитывает условия неотрицательности переменных. Для того чтобы это условие было учтено, надо выбирать k, а также
alk так, чтобы условие неотрицательности сохранилось.
Так как ЗЛП рассматривается в канонической форме, то начальное базисное решение x
b
- неотрицательно.
0
Заметим, что если столбец Ak 0 , то его нельзя вводить в базис, так как
при любом выборе направляющего элемента alk xkí xl / alk 0 , поэтому для введения в базис необходимо выбирать столбец Ak , такой, что существует àik 0 .
Кроме того, как следует из алгоритма Жордана-Гаусса, для i k
í
таким образом, чтобы выxi xi aik . Следовательно, необходимо выбрать
полнилось условие: xi aik 0 для всех i k .
0.
Если aik 0 , то xií 0 для любого
Если aik 0 , то существует максимальное , при котором xií 0 . Его
можно найти по правилу
min ( xi / a ik ) xl / a lk .
aik 0
Алгоритм перестроения базисного решения ЗЛП
Пусть определен столбец с номером k, подлежащий введению в базис.
Шаг 1: Определить l (номер выводимого столбца) по правилу
min ( xi / aik ) xl / alk .
aik 0
Шаг 2: Переход к алгоритму Жордана-Гаусса.
Шаг 3: Вычислить значение целевой функции по формуле f ( x) cBT xB .
Из рассмотренного выше алгоритма следует, что перебрав с его помощью
все базисные решения можно найти оптимальную точку.
Пример 1.4. Дана ЗЛП в канонической форме. Требуется найти оптимальное решение с помощью перебора базисных решений.
2 x1
x2
x3
x1
x2
2 x3
xi
0, i 1,5 ,
13
x4
3;
x5
5;
f ( x)
5 x1
2 x2
x3
2 x4
x5
max .
Решение. Оформим решение задачи в виде таблицы (табл. 1.4.). В первом
столбце поместим текущие базисные переменные, во втором - их коэффициенты в
целевой функции, в третьем - базисные координаты текущей точки x B . Далее переписываем элементы матрицы aij , помещая над каждым столбцом коэффициент
соответствующей переменной в целевой функции. Последний столбец предназначается для определения значения . В последней строке под x B записывается
значение целевой функции, остальные клетки этой строки пока не заполнены.
Таблица 1.4
5
2
-1
-2
1
A1
A2
A3
A4
A5
3
2
1
-1
1
0
3
5
1
1
2
0
1
5
B
cB
xB
x4
x5
-2
1
f (x)
x2
x5
3
2
1
-1
1
0
1
2
-1
0
3
-1
1
5
3
1
0
2
1
0
1
1
3
0
1
1
2
1
0
1
5
0
x2
2
x3
-1
f (x)
11
3
20
3
11
x3
-1
5
x3
x1
x5
5
-1
f (x)
48
1
f (x)
2
2
27
2
11
5
7
5
3
2
-2
x1
(0,0,0,3,5)
f ( x1 )
x2
1
(0,3,0,0,2)
f (x2 ) 8
8
x4
f (x)
x1
˅
-1
2
f (x)
Базисное решение
3
7
5
5
1
3
2
2
1
2
3
3
2
1
3
x3
(0,11 , 2 ,0,0)
3 3
f ( x 3 ) 20
3
x4
(0,0, 5 ,11 ,0)
2 2
4
27
f (x )
2
x5
(11 ,0, 7 ,0,0)
5
5
5
f ( x ) 48
5
3
2
2
11
5
5
˅
1
0
3
1
5
2
5
1
1
5
1
2
5
5
˅
5
2
1
1
0
1
1
2
2
1
5
2
2
1
2
1
11
14
2
0
x6
1
( 3 ,0,0,0, 7 )
2
2
6
f ( x ) 11
x
6
Перебраны все базисные точки, и оптимальной точкой является
( 3 ,0,0,0, 7 ) со значением f ( x 6 ) 11 .
2
2
Лабораторная работа № 2
Дана ЗЛП:
x1
2 x2
bx1
x2
2 x1
cx2
x3
x1
x4
2,
2 x4
4 x3
12,
2 x4
6,
0, i 1,4 ,
xi
f ( x)
x3
x2
x3
ax4
max .
В табл. 1.5. приведены варианты значений параметров a, b, c.
1
2
3
4
5
a
2
3
4
7
8
b
3
1
2
2
3
c
-1
1
-1
3
4
6
7
8
9
10
a
5
4
6
2
5
b
2
3
1
2
3
c
3
6
5
2
7
11
12
13
14
15
a
2
3
5
7
6
b
1
3
2
1
3
c
2
4
-1
5
8
16
17
18
19
20
Таблица 1.5
a
b
c
3
3
1
4
1
2
3
1
0
4
1
3
5
2
6
Необходимо выполнить следующие задания:
1. Привести ЗЛП к канонической форме.
2. С помощью алгоритма перестроения базисного решения ЗЛП найти
четыре различных базисных решения и выбрать среди них наилучшее.
2. Симплекс-метод
Как было показано выше, с помощью перебора базисных решений можно
получить оптимальное решение, если задача разрешима.
Заметим, что число базисных решений хотя и конечно, однако может
быть весьма большим, при больших размерах задачи. Поэтому если имеется некоторая базисная точка, то хотелось бы знать:
1. Не является ли она оптимальной и если это так, то просмотр остальных
точек не целесообразен;
2. Не является ли задача неразрешимой из-за неограниченности целевой
функции. В этом случае просмотр остальных точек также не целесообразен;
3. Если точка неоптимальная, то нельзя ли определить вектор-столбец,
подлежащий введению в базис, такой, что значение целевой функции будет обязательно больше предыдущего.
15
2.1. Основная теорема линейного программирования
Будем называть
(cBT A j
j
(2.1.1)
cj)
оценкой вектора A j .
Теорема: Пусть имеется базисное решение ЗЛП xáàç
xB
0
b
со значением
целевой функции f ( xáàç) cBT xB cBT b и для всех j найдены оценки j (cBT A j c j ) .
Тогда:
1. Если имеется j 0 для любых j, то базисное решение оптимально;
2. Если существует k 0 , то существует бесчисленное множество допустимых решений x G , для которых f ( x) f ( xáàç) . При этом
2а. Если столбец Ak 0 , то задача неразрешима из-за неограниченности
целевой функции;
2б. Если имеется aik 0 , то существует новое базисное решение, значение целевой функции на котором больше, чем на исходном , то есть
n
f ( xáàç
) f ( xáàç) .
Замечание: Теорема справедлива, если базисное решение не вырождено,
то есть b 0 .
На основе этой теоремы строится метод решения ЗЛП, называемый симплекс-методом, который фактически является методом перестроения базисного
решения с учетом оценок небазисных столбцов.
2.2. Алгоритм симплекс метода
Пусть имеется базисное решение xáàç
xB
b
0
со значением целевой
функции f ( x) cBT xB .
Шаг 1: Вычислить оценки по формуле
c j aij
j
c j при всех j.
i IB
j j 0 , то выписывается оптимальное решение задачи.
Шаг 2: Если для
Конец.
Иначе Шаг 3.
Шаг 3: Выбирается k 0 .
Шаг 4: Просматривается столбец Ak , если Ak 0 , то выписывается от-
вет:
16
«Задача не разрешима из-за неограниченности целевой функции».
Конец.
Иначе Шаг 5.
Шаг 5: Алгоритм перестроения базисных решений ЗЛП.
Шаг 6: Переход к Шагу 1.
Пример 2.1. Решить задачу
f ( x)
x1
x2
x1
x2
x1
x2
2 x1
x3
1,
x4
1,
x5
2,
xi
0, i 1,5 ,
x2
3x3
2 x4
max .
x5
Решение. Оформление задачи происходит аналогично предыдущему примеру (табл. 2.1).
В последней строке, ранее не заполненной, вписываются оценки и f ( xB ) ,
которые вычисляются по формуле f ( x) (cB , xB ) .
Таблица 2.1
2
-1
3
-2
1
B
cB
xB
x3
x4
x5
3
-2
1
j
3
2
1
x3
x1
x5
j
A1
A2
A3
A4
A5
1
1
2
-1
1
1
1
-1
1
1
0
0
0
1
0
0
0
1
3
-6
7
0
0
0
2
1
1
9
0
1
0
0
0
-1
2
1
1
0
0
0
1
1
-1
6
0
0
1
0
Поскольку на первой итерации
min
1 2
,
1 1
0 , в базис вводится вектор
1
1, то есть в качестве направляющего элемента выбирается
как на второй итерации все
x * (1,0,2,0,1) . Поскольку на небазисных векторах
единственно.
Пример 2.2. Решить задачу
x1
A1 .
a21 . Так
0 , то конец, получена оптимальная точка
j
x1
1
2
x2
x3
x2
x1 3x2
xi
x4
1,
x5
x3
0, i 1,6 ,
17
1,
x6
2,
j
0 , то решение в задаче
f ( x)
2 x1
x2
x3
3 x4
2 x5
max .
x6
Решение. Оформление задачи происходит аналогично предыдущему примеру (табл. 2.2).
Таблица 2.2
2
-1
1
3
-2
1
B
cB
A1
-1
1
1
-6
0
1
0
0
A3
-1
0
1
-3
-1
0
1
-3
A2
1
-1
-3
3
0
-1
-2
-3
1
1
2
3
j
3
2
x4
2
1
x1
1
1
x6
9
j
На второй итерации получаем, что оценка
ложительных элементов.
Ответ: целевая функция неограниченна.
x4
x5
x6
3
-2
1
xB
A5
0
1
0
0
1
1
-1
6
A4
1
0
0
0
1
0
0
0
2
A6
0
0
1
0
0
0
1
0
1
2
0 , но в столбце А2 нет по-
Лабораторная работа № 3
Решить симплекс-методом ЗЛП из лабораторной работы № 2.
2.3. Симплекс-метод с искусственным базисом
Вернемся к алгоритму симплекс-метода и заметим, что его применение
возможно только при наличии начального базисного решения. Однако его
можно получить, только если матрица А имеет вид A ( E / Aˆ ) . В этом случае
ЗЛП представляется в виде
xB
Aˆ x A
b,
xB
0, x A
0,
f ( x) c BT x B
c TA x A
max
и имеется базисное решение с базисными компонентами xB b .
Рассмотрим задачу.
Ax b,
x 0,
f ( x)
(2.3.1)
T
c x
max,
где матрица А не имеет единичных столбцов или их число меньше числа строк
матрицы.
В этом случае нет возможности найти начальное базисное решение, более
того задача (2.3.1) может оказаться несовместной.
18
Поэтому задача решается в два этапа. На первом этапе отыскивается
начальное базисное решение, а на втором – решается исходная задача с помощью алгоритма симплекс-метода.
Задача первого этапа:
Ax Ez b ,
(2.3.2)
x 0, z 0 ,
fˆ ( x, z )
zi
max .
Переменные z i называются искусственными переменными.
Утверждение 1: Задача (2.3.2) разрешима.
Утверждение 2: Если при решении задачи (2.3.2) получено оптимальное
решение x0 ( x 0 , z 0 )T и fˆ ( x 0 , z 0 ) 0 , то точка x 0 ( x10 ,..., xn0 ) является допустимым решением задачи (2.3.1).
Утверждение 3: Если оптимальное значение целевой функции
fˆ ( x 0 , z 0 ) 0 , то допустимое множество задачи (2.3.1) пусто.
На основе утверждений 1-3 и строится алгоритм симплекс-метода с искусственным базисом.
Алгоритм симплекс-метода с искусственным базисом
Шаг 0: Приведение к канонической форме.
Шаг 1: Запись всех исходных данных в таблицу.
Шаг 2: Просмотреть столбцы матрицы A и отыскать единичные столбцы
с единицами в разных позициях. Соответствующие переменные занести в гр афу-базис.
Шаг 3: Просматривается базисный столбец, если он заполнен, то переход
к алгоритму симплекс-метода.
Конец.
Иначе Этап 1.
Этап 1
Шаг 1: Свободные места в базисном столбце заполняются переменными
z i с номерами соответствующими номерам строк.
Шаг 2: Целевые коэффициенты при переменных xi полагаются равными
нулю ( ci 0 ).
Целевые коэффициенты при z i полагаются равными минус единице.
Шаг 3: Переход к алгоритму симплекс-метода.
Шаг 4: Если fˆ ( x ) опт 0 , то выписывается ответ: Задача несовместна.
Конец.
Иначе переход к Этапу 2.
Этап 2
19
Шаг 1: Для всех переменных xi целевые коэффициенты полагаются равными сi .
Шаг 2: Переход к алгоритму симплекс-метода.
Конец.
Замечание 1: Единичные столбцы, соответствующие переменным z i , в
таблицу не заносятся.
Пример 2.3. Решить задачу:
2 x1
x2
2 x1
x2
x1
x2
f ( x)
x1
x3
x4
x5
3,
x4
1
x5
2
1,
2
x 4 x5 8,
3
x1 0 ,
x2 x3 3x5
max .
x3
1.Занесём все данные задачи в табл. 2.3.
Таблица 2.3
B
cв
xв
1
-1
1
0
-3
A1
A2
A3
A4
A5
3
-2
1
0
1
-1
1
8
2
-1
-1
1
1
-1
-1
2
⁄3
- 1 ⁄2
1
2. Просматриваем табл. 2.3 и отыскиваем единичные столбцы для введения их в базис.
В таблице таких столбцов нет, поэтому в графу В заносят три искусственные переменные, а в графу cв - коэффициент (-1) (табл. 2.4).
Таблица 2.4
B
cв
xв
-1
3
z1
-1
1
z2
-1
8
z3
3. Вычисляем значения
числяем оценки по формуле
0
0
0
0
0
A1
A2
A3
A4
A5
-2
2
-1
1
-1
1
0
1
-1
1
-1
2
⁄3
-1
- 1 ⁄2
1
Ө
целевой функции по формуле f ( x)
ci Aij c j (табл. 2.5).
j
20
ci xi . Вы-
Таблица 2.5
B
cв
xв
0
0
0
0
0
z1
z2
z3
-1
-1
-1
3
1
8
-12
-2
2
-1
1
A1
A2
A3
A4
A5
1
-1
1
-1
0
1
-1
-1
1
-1
2
⁄3
2
- ⁄3
Ө
-1
- 1 ⁄2
1
1
⁄2
4. Так как ∆4<0, то x4 можно ввести в базис.
Вычисляем θ по формуле
min
aik 0
xi
aik
.
Минимальному значению θ будет соответствовать место направляющего
элемента в столбце x4.
Полностью все Шаги перестроения базисного решения представлены в
табл. 2.6.
Таблица 2.6
B
cв
xв
z1
z2
z3
-1
-1
-1
3
1
8
-12
B
cв
xв
x4
z2
z3
0
-1
-1
x4
z2
x1
0
-1
0
x4
x3
x1
0
0
0
3
4
6
-10
39
4
18
-4
63
4
30
0
0
A1
-2
2
-1
1
0
A2
1
-1
1
-1
0
A3
0
1
-1
-1
0
A4
1
-1
2
⁄3
2
- ⁄3
0
A1
-2
0
1
⁄3
1
- ⁄3
0
0
1
0
0
0
1
0
0
A2
1
0
1
⁄3
1
- ⁄3
3
0
1
0
3
0
1
0
0
A3
0
1
-1
0
-6
1
-3
-1
0
1
0
0
0
A4
1
0
0
0
1
0
0
0
1
0
0
0
0
A5
Ө
-1
- 1 ⁄2
1
1
⁄2
Окончание табл. 2.6
0
A5
-1
- 3 ⁄2
5
⁄3
1
- ⁄6
9
- 3 ⁄2
5
3
⁄2
0
- 3 ⁄2
1
⁄2
0
Ө
18
4
-
Так как все оценки i 0 и fˆ ( x, z) 0 , то первый этап закончен и переходим ко второму этапу.
В верхнюю строку вновь заносим коэффициент c j и в столбец
cв - коэффициенты c i при базисных переменных (табл. 2.7).
Таблица 2.7
21
B
cв
xв
x4
x3
x1
0
1
1
63
4
30
34
1
А1
0
0
1
0
-1
А2
3
0
1
2
1
А3
0
1
0
0
0
А4
1
0
0
0
-3
А5
0
- 3 ⁄2
1
⁄2
2
Так как все оценки больше или равны нулю, следовательно, получено оптимальное решение:
x * (30, 0, 4, 63, 0) ,
f ( x* ) 34 .
Лабораторная работа №4
Дана ЗЛП
2 x1
x2
2 x1
x2
x3
x1
x2
x3
xj
f ( x)
x1
x4
x4
x5
b
a
x5
1
x4 x5
c 1
0, j 1,5 ,
8
b 1
c
x2
x3 3x5
max .
В табл. 2.8 приведены значения параметров a, b, c.
Номер
варианта
a
b
c
Номер
варианта
a
b
c
Номер
варианта
a
b
c
1
2
3
4
5
1
2
3
4
5
1
1
1
1
2
2
2
2
2
2
6
7
8
9
10
6
7
2
4
6
2
2
1
1
1
2
2
3
3
3
11
12
13
14
15
2
4
6
3
6
2
2
2
1
1
3
3
3
4
4
Таблица 2.8
Номер
a b c
варианта
16
17
18
19
20
3
6
3
6
3
2
2
3
3
4
4
4
4
4
4
1. Привести ЗЛП к канонической форме.
2. Решить ЗЛП с помощью симплекс-метода с искусственным базисом.
3. Найти оптимальное решение и вычислить значение целевой функции.
3. Двойственность в ЗЛП
3.1. Основные понятия и определения
Рассмотрим ЗЛП в канонической форме:
Ax b,
x 0,
f ( x)
(3.1.1)
cT x
22
max,
и ЗЛП в симметричной форме:
Ax b,
x 0,
f ( x)
b
cT x
max,
(3.1.2)
0.
Заметим, что если в канонической форме b 0 , то при записи ЗЛП в симметричной форме условие неотрицательности правых частей не требуется.
Определение 1: Задача
y T A cT ,
g ( y)
yT b
min
(3.1.3)
называется задачей двойственной к задаче (3.1.1).
Определение 2. Задача
yT A
y
cT ,
(3.1.4)
0,
g ( y)
yT b
min
называется двойственной к ЗЛП в симметричной форме.
Заметим, что у задачи двойственной к задаче в канонической форме
условие неотрицательности переменных отсутствует, в то время как для задачи
двойственной к задаче в симметричной форме условие неотрицательности переменных обязательно.
Как следует из вида двойственных задач (3.1.3) и (3.1.4):
1. Количество переменных двойственной задачи совпадает с количеством ограничений исходной задачи;
2. Количество ограничений двойственной задачи совпадает с количеством переменных исходной задачи;
3. Каждому ограничению исходной задачи соответствует переменная
двойственной задачи;
4. Количество переменных исходной задачи соответствует ограничение
двойственной задачи;
5. Матрица ограничений двойственной задачи является транспонированной по отношению к матрице ограничений исходной задачи;
6. Ограничения двойственной задачи являются неравенствами типа
«больше или равно»;
7. Целевые коэффициенты исходной задачи являются правыми частями
ограничений двойственной задачи;
8. Правые части ограничений исходной задачи являются целевыми коэффициентами двойственной задачи;
9. Если в исходной задаче отыскивается максимум целевой функции, то в
двойственной – минимум;
10. Двойственная задача к двойственной задаче совпадает с исходной.
23
Исходя из вышесказанного можно сформулировать правило построения
двойственной задачи.
Так как по определению двойственные задачи могут задаваться только к
задачам в канонической или симметричной форме, то если вид исходной задачи
имеет отклонения от указанных форм, например имеется неравенство типа
«больше или равно» или целевая функция, стремящаяся к минимуму - такую
задачу нужно привести к виду, описанному ранее, а именно: ограничение типа
«больше или равно» заменяется на «меньше или равно» и целевая функция,
стремящаяся к минимуму, заменяется функцией, стремящейся к максимуму.
Таким образом, алгоритм построения двойственной задачи состоит из
двух этапов. На первом этапе задача приводится к виду, соответствующему
(3.1.1) или (3.1.2), а на втором этапе строится двойственная задача.
Алгоритм построения двойственной задачи
Этап 1
Шаг 1: Просматриваются ограничения задачи и если среди ограничений
имеются ограничения типа больше или равно, то коэффициенты умножаются
на минус единицу и знак неравенства изменяется на противоположный.
Шаг 2: Рассматривается целевая функция. Если в исходной задаче требуется найти ее минимум, то все коэффициенты умножаются на минус единицу, а
функцию переориентируют на максимум.
Этап 2
Шаг 1: Каждому ограничению исходной задачи приписывается y i , номер
которого соответствует номеру ограничения.
Шаг 2: Выписываются в столбик все переменные исходной задачи.
Шаг 3: К каждой переменной x j приписывается ограничение двойственной задачи вида ( y, Aj ) c j ( ( y, A j )
m
yi aij
).
i 1
Шаг 4: Если ограничение с номером i исходной задачи является неравенством, то в двойственной задаче записывается ограничение вида yi 0 .
Замечание 1. Если i-е ограничение является неравенством, то условие неотрицательности на соответствующую двойственную переменную не накладывается.
Шаг 5: Выписывается целевая функция двойственной задачи
g ( y)
( y , b)
min .
3x1
2 x2
x3
x4
5,
x1
3x 2
x3
2 x4
4,
x1
2 x2
x3
3x 4
6,
Пример 3.1. Дана ЗЛП:
xj
(3.1.5)
(3.1.6)
(3.1.7)
j 1,4 ,
0,
fˆ ( x) 5 x1 3x2
24
4 x3
min .
Этап 1. Ограничение задачи (3.1.6) является ограничением типа «больше
или равно», и в соответствии с алгоритмом его необходимо заменить ограничением «меньше или равно».
Целевая функция ориентирована на минимум, в соответствии с алгоритмом ее необходимо заменить функцией, ориентированной на максимум.
Окончательный вид задачи, для которой будем строить двойственную,
следующий:
(3.1.5)
3x1 2 x2 x3 x4 5
(3.1.6`)
x1 3x2 x3 2 x4
4
(3.1.7)
x1 2 x2 x3 3x4 6
x j 0, j 1,4 ,
f ( x)
5 x1 3x2 4 x3
max .
Этап 2. Каждому ограничению приписываем двойственную переменную y i :
y1 3x1 2 x2 x3 x4 5 ,
y 2 x1 3x2 x3 2 x4 4 ,
y3 x1 2 x2 x3 3x4 6 ,
x j 0, j 1,4 ,
f ( x)
5 x1 3x2 4 x3
max .
Выписываются все переменные двойственной задачи и к ним припис ываются ограничения двойственной:
x1 3 y1 y2 y3 5 ,
2 y1 3 y2 2 y3
3,
x2
x3 y1 y2 y3 0 ,
x4 y1 2 y2 2 y3 4 ,
В соответствии с алгоритмом условие типа yi 0 накладывается на
первую и вторую двойственные переменные: y1 0, y2 0.
Целевая функция двойственной задачи имеет вид
g ( y) 5 y1 4 y2 6 y3
min .
Окончательный вид двойственной задачи следующий:
3 y1 y2 y3
5,
2 y1 3 y2 2 y3
3,
y1 y2 y3 0 ,
y1 2 y2 2 y3 4 ,
y1 0, y2 0 ,
g ( y) 5 y1 4 y2 6 y3
min .
25
3.2. Леммы и теоремы двойственности
~
Лемма 1. Пусть G - допустимое множество исходной задачи и G - допустимое множество двойственной задачи. Тогда для всех x G и y G~ выполняется следующее неравенство:
f ( x) g ( y ) .
Лемма 2. Если одна из задач двойственной пары неразрешима из-за неограниченности целевой функции, то другая несовместна.
~
Лемма 3. Если G
иG
, то обе задачи разрешимы.
~
*
*
Лемма 4. Пусть x G и y G таковы, что
f ( x* ) g ( y * ) ,
тогда x* и y * - оптимальные решения исходной и двойственной задач соответственно.
Первая теорема двойственности. Если одна из задач двойственной пары разрешима, то разрешима и другая задача. При этом значение целевой
функции на оптимальных решениях исходной и двойственной задач совпадают:
f ( x* ) g ( y * ) ,
где x* и y * - оптимальные решения исходной и двойственной задач соответственно.
~
Вторая теорема двойственности. Пусть G
иG
. Для того чтобы
~
*
*
x G и y G были оптимальными решениями исходной и двойственной задач
соответственно, необходимо и достаточно выполнение следующих условий:
(3.2.8)
( y * )T ( Ax * b) 0 ,
* T
T
*
(3.2.9)
(( y ) A c ) x 0 .
Следствие из второй теоремы двойственности. Пусть x* и y * - оптимальные решения исходной и двойственной задач соответственно. Тогда, если
на оптимальном решении исходной задачи какое-либо ограничение выполняется как строгое неравенство, то соответствующая двойственная переменная равна нулю.
Если оптимальная переменная исходной задачи больше нуля, то соответствующее двойственное ограничение на оптимальном решении выполняется
как строгое равенство.
Используя следствие ко второй теореме двойственности, можно, имея
оптимальное решение исходной задачи, найти оптимальное решение двойственной задачи.
Рассмотрим пример, используя условие и решение примера 1.1.
Алгоритм решения двойственной задачи
Шаг 1. Выписывается двойственная задача (см. алгоритм построения
двойственной задачи).
Шаг 2. Просматриваются переменные исходной задачи.
26
Если переменные строго больше нуля, то соответствующее ограничение дво йственной задачи записывается как равенство.
Шаг 3. Значения переменных исходной задачи подставляются поочередно
в левую часть каждого ограничения этой задачи. Полученное значение сравнивается с правой частью, если получено строгое неравенство, то соответствующая переменная двойственной задачи полагается равной нулю.
Шаг 4. Решается полученная система линейных уравнений относительно
двойственных переменных y i . Решение этой системы есть оптимальное решение двойственной задачи.
Шаг 5. Вычисляется значение целевой функции g ( y * ) . Оно должно получиться равным f ( y * ) .
Замечание. Может оказаться, что в оптимальной точке исходной задачи
переменных не две, а три прямые. Тогда система уравнений для решения дво йственной задачи будет иметь переменных больше, чем ограничений. Это означает, что двойственная задача имеет не единственное решение.
Пример 3.2. Дана ЗЛП и ее оптимальное решение:
(3.2.10)
2 x1 3x2 18 ,
(3.2.11)
x1 3x2 9 ,
(3.2.12)
2x1 x2 10 ,
x1
0,
x2
0,
f ( x)
6
,
2
x
2x2
max ,
f (x )
24 4
4x1
28 .
Требуется записать двойственную задачу и найти ее решение.
Решение. Выпишем исходную задачу и припишем к ее ограничениям слева двойственные переменные:
y1
y2
y3
Двойственная задача:
x1
x2
2x1 3x2 18 ,
x1 3x2 9 ,
2x1 x2 10 .
x1 0,
x2 0,
f ( x) 4x1 2x2
max .
2 y1
y2
2 y3
4,
3 y1
3 y2
y3
2,
y1, 2,3
g ( y ) 18 y1
27
0,
9 y 2 10 y3 .
Замечание. Если в исходной задаче какое-либо ограничение типа «больше или равно», то его необходимо поменять на знак типа «меньше или равно» и
только после этого выписывать двойственную задачу.
Так как x1* 6 0 и x2* 2 0 , следовательно, оба ограничения двойственной задачи записываются как строгие равенства:
2 y1 y2 2 y3 4 ,
3 y1 3 y2 y3 2 .
Подставим x* поочередно в каждое из неравенств исходной задачи:
2 6 3 2 18 18 ,
1 6 3 2 0 9 , следовательно, y2
2 6 2 10 10 .
0,
Таким образом, для нахождения оптимального решения двойственной задачи имеем систему
То есть y
*
2 y1
y2
2 y3
4,
y1
1,
3 y1
3 y2
y3
2,
y2
0,
y2
0,
y3
1.
1
0 .
1
Вычислим значение целевой функции g ( y * ) 18 1 9 0 10 1 28 , из чего
следует g ( y * ) f ( x* ) .
Лабораторная работа № 5
Используя данные, полученные в ходе выполнения своего варианта из
лабораторной работы № 1, выполнить следующие задания:
1. Выписать двойственную задачу,
2. Найти ее решение.
4. Транспортная задача
4.1. Математическая модель транспортной задачи
Вербальная модель
Имеется m поставщиков некоторого продукта. Ai ( i 1, m ) – количество
продукта у i-го поставщика.
Имеется n потребителей этого продукта. Bj ( j 1, n ) – потребность j-го
потребителя.
сij – затраты на перевозку единицы продукта (1т, 1кг, 1 банка и т.д.) от
i-го поставщика к j-му потребителю.
28
Требуется составить план перевозки продукции от поставщиков к потребителям так, чтобы суммарные затраты на перевозку были минимальными
(имеется в виду, что перевозки осуществляет одна фирма).
Предполагается выполнение условия баланса:
m
n
Bj ,
Ai
i 1
j 1
то есть суммарное наличие продукта у всех поставщиков равно суммарной потребности всех потребителей.
Математическая модель
Пусть xij 0 – количество продукции, которое перевозят от i-го поставщика к j–му потребителю.
Так как есть условие баланса
m
n
Bj ,
Ai
i 1
(4.1.1)
j 1
то возникают ограничения:
1) от каждого поставщика должна быть вывезена вся продукция
n
xij
Ai , i 1, m .
(4.1.2)
j 1
2) каждый потребитель должен быть удовлетворен, т.е. должно быть перевезено столько продукции, сколько нужно, ни больше, ни меньше.
m
xij
Bj , j
1, n .
(4.1.3)
i 1
Целевая функция будет выглядеть следующим образом:
m
n
i 1
j 1
cij xij
min .
(4.1.4)
Как видно из математической модели, транспортная задача представляет
собой ЗЛП в канонической форме, имеющую ( n m ) ограничений и ( n m )
переменных. То есть транспортная задача даже при небольшом количестве поставщиков и потребителей оказывается достаточно громоздкой и ее решение с
помощью обычного симплекс-метода хотя и возможно, но требует значительных информационных и временных ресурсов. Однако, с учетом специфики с истемы ограничений, формулы симплекс-метода значительно упрощаются. Модифицированный с учетом структуры матрицы симплекс-метод называется методом потенциалов и будет рассматриваться позже.
Транспортная задача задается таблицей размера ( (m 1) (n 1) ), где в
первом блоке матрицы размером ( m n ) выписывается матрица коэффициентов целевой функции C cij . Справа выписывается столбец со значениями Ai ,
а внизу - B j (рис. 4.1).
29
j
i
1
…
j
…
n
Ai
с11
ñ1 j
ñ1n
A1
с i1
сij
сin
Ai
m
с m1
сmj
сmn
Am
Bj
B1
Bj
Bn
1

i

Рис. 4.1
Допустимое решение X {xij }, также заносится в матрицу размером
( m n ). При этом i-я строка соответствует i-му ограничению (4.1.2), а j-й столбец – j-му ограничению (4.1.3), откуда следует, что сумма элементов i-й строки
матрицы X равна Аi , сумма всех элементов j-го столбца равна B j (рис. 4.2).
j
i
1

i

m
x11
j … n
x1 j
x1n A1
xi1
xij
xm1
x mj
Bj
Рис. 4.2
1
B1
…
xin
Ai
x mn Am
Bn
Теорема. Для того чтобы транспортная задача была разрешима, необходимо и достаточно выполнение условия баланса.
Замечание. К задаче вида (4.1.1)-(4.1.4) могут сводиться и другие вербальные модели, возможно не имеющие никакого отношения к перевозкам.
Однако всегда ЗЛП (4.1.1)-(4.1.4) называется транспортной задачей.
От обычной ЗЛП в канонической форме транспортная задача отличается
тем, что в ней ищется минимум функции, а не максимум. Однако нет необходимости заменять ее функцией поиска максимума, так как если есть поиск минимума, то процесс решения не меняется, но при этом критерием оптимальности являются неположительные оценки, то есть ij 0 .
Так как транспортная задача является ЗЛП в канонической форме, причем
в ней не существует единичного столбца, то при решении этой задачи должно
быть два этапа:
1. Построение начального базисного решения,
2. Решение транспортной задачи.
Для ЗЛП на первом этапе необходимо вводить искусственные переменные и решать задачу с помощью симплекс-метода с искусственным базисом.
Достоинством транспортной задачи является то, что ее начальное базисное р ешение может быть построено без использования искусственных переменных.
30
4.2. Построение начального базисного решения
Начальное базисное решение строится в соответствии со следующей достаточно простой идей. Выбирается произвольная клетка xij таблицы Х и в нее
заносятся максимально возможный по значению элемент. Так как каждое
xij Ai и xij B j , то максимально возможное значение xij min( Ai , B j ) .
Допустимое решение заносится в матрицу Х, в которой будет заполнено
( m n 1) клеток, так как ранг матрицы C равен ( m n 1).
При этом должны выполняться условия:
1. Сумма по строкам равна Ai,
2. Сумма по столбцам равна Bj.
Алгоритм построения начального базисного решения
Шаг 0. k=0.
Шаг 1. Выбирается произвольная свободная клетка (i, j).
Шаг 2. Вычисляется xij min( Ai , B j ) .
B j xij .
Шаг 3. Если xij Ai , то i-я строка вычеркивается, а B íîâ
j
Шаг 4. Иначе вычеркивается j-й столбец, а Aiíîâ Ai xij .
Шаг 5. k k 1 .
Шаг 6: Если k m n 1 , то
Конец.
Иначе переход к Шагу 1.
В алгоритме построения базисного решения не задается способ выбора
клетки (i, j) для заполнения. Мы предлагаем два наиболее распространенных
метода заполнения клеток при построении начального базисного решения:
1. Метод северо-западного угла. (В этом случае для заполнения выбирается левая верхняя клетка.)
2. В методе северо-западного угла не учитывается стоимость перевозок
вследствие чего полученное базисное решение может быть далеким от оптимального. Поэтому при заполнении клеток можно предложить в первую оч ередь заполнять клетки с наименьшей стоимостью перевозок. Этот метод наз ывается методом минимального элемента.
Пример 4.1. Имеется транспортная задача (рис. 4.3).
Ai
Bj
5
3
2
1
8
4
6
4
2
10
3
2
5
3
7
1
4
3
4
11
2
3
1
5
9
7
8
10
20
Рис. 4.3
1. Используем при выборе клеток для заполнения метод северо-западного
угла (рис. 4.4).
31
7
1
7
7
3
7
8
1
10
7
0 11 9 20 9
8 10 7 11 9
1 3 0
Рис. 4.4
Невычеркнутых элементов осталось 8, так как ранг матрицы равен 8, то есть
матица размера 5×4. 5+4–1=8 (m+n–1).
Ñ (x) 5 7 3 1 6 7 4 3 5 7 3 0 4 11 5 9 216 .
2. Метод минимального элемента (рис. 4.5).
7
7
7
8
8
Ñ (x)
10
10
2
1
1 9
2
7 11 9
4
3
Рис. 4.5
7 1 1 4 7 2 1 3 9 1 8 1 1 2 2 4
8 1
10 1
20 12
73 .
Видно, что значение целевой функции на допустимом решении, полученном с помощью метода минимального элемента, лучше по сравнению с другими вариантами. То есть метод минимального элемента – хороший способ
нахождения субоптимального решения (решения, близкого к оптимальному).
Однако, поскольку этот метод является эвристическим, не следует надеяться, что с его помощью всегда будет получено хорошее решение.
Задание 1. Придумать пример транспортной задачи, при решении которой использование метода минимального элемента даст допустимое решение со
значением целевой функции большим, чем при решении той же задачи с использованием метода северо-западного угла.
Задание 2. Придумать собственный подход к выбору клеток для заполнения и обосновать его целесообразность.
Замечание. При построении начального базисного решения на каждом
Шаге вычеркивается либо строка, либо столбец, а на последнем Шаге остается
не вычеркнутой и заполняется ровно одна клетка, таким образом общее количество заполненных клеток (m+n–1). Так как число базисных компонент в транспортной задаче равно (m+n–1), то можно предположить, что мы получили базисное решение.
32
4.3. Метод потенциалов
Симплекс-метод, используемый для решения транспортной задачи, называется методом потенциалов.
Основные этапы симплекс-метода:
Этап 1. Вычисление оценок. Проверка решения на оптимальность. Если
решение оптимальное, то конец. Иначе переход к этапу 2.
Этап 2. Перестроение базисного решения. Переход к этапу 1.
Рассмотрим подробно каждый из этапов применительно к транспортной
задаче.
Этап 1. Вычисление оценок и проверка решения на оптимальность
Наша задача ориентирована на min, поэтому нужно учесть критерий оптимальности ij 0 .
Оценки можно вычислять, используя двойственную задачу, а именно выписываются ограничения двойственной задачи, базисные ограничения запис ываются как равенства и из полученной системы находится псевдорешение
двойственной задачи. Найденные значения двойственных переменных подставляются в небазисные ограничения двойственной задачи, в которых правые ч асти перенесены влево со знаком минус. Полученные значения и есть оценки.
Переходим к вычислению оценок для транспортной задачи. Выпишем
ограничения задачи двойственной к транспортной. Обозначим через U i двойственные переменные к первому блоку ограничений транспортной задачи и ч ерез V j - ко второму блоку ограничений:
n
xij
Ui
Ai , где i 1, m ,
j 1
m
Vj
xij
Bj ,
где j
1, n ,
i 1
xij
cij xij
0.
min .
Двойственное ограничение при переменной xij будет следующим:
U i V j Cij .
xij
Двойственные переменные могут быть как положительными, так и отрицательными, так как транспортная задача записана в канонической форме. Следуя теории симплекс-метода, двойственное ограничение соответствующее
xij баз , запишем как равенство
xij áàç
Ui
Vj
Cij ( xij
Из этой системы найдем U i , V j .
33
баз
из матрицы Х).
Так как количество ограничений равно (m+n–1), а количество переменных равно (m+n), будем полагать, что всегда U1 = 0 и тогда
U i Cij V j ,
V j Cij U i .
Вычисляем для всех небазисных (i, j) оценки ij по формуле
U i V j Cij .
ij
Алгоритм выполнения этапа 1
Шаг 1. Для всех xij базисных записывается уравнение U i V j Ci. j .
Шаг 2. U1 = 0,
Шаг 3. Вычисление остальных потенциалов U i , V j по формулам:
Ui
Cij V j ,
Vj
Cij U i .
Шаг 4. Для всех (i, j) небазисных вычисляются оценки
U i V j Cij .
ij
Шаг 5. Если все ij 0 , то вычисляется
ij
:
cij xij .
Ñ ( x)
Конец.
Иначе переход к Этапу 2.
Этап 2. Перестроение базисного решения
Пусть существует i0 j0 0 , как следует из теории симплекс-метода, если
переменную xi0 j0 сделать базисной, то значение целевой функции уменьшится.
Посмотрим, как получить значение xi0 j0
при отсутствии обычной
симплекс-таблицы. Так как сумма элементов в каждой строке и в каждом
столбце в матрице допустимого решения Х должна сохраняться, то если какойто элемент строки увеличивается, очевидно, что значение некоторого другого
элемента в этой же стоке должно быть уменьшено, а некоторое значение в
столбце, в котором значение элемента уменьшено, должно быть увеличено и
так далее.
Поскольку в строке матрицы может быть несколько ненулевых элементов, то при увеличении одного из них не всегда понятно, какой именно нужно
уменьшить, то же самое относится и к столбцу.
Эти элементы можно определить с помощью правила вычеркивания.
4.4. Правило вычеркивания
Пусть задана транспортная таблица, в которой выделены некоторые элементы. Просматриваются строки и вычёркиваются те, которые содержат не бо-
34
лее одного выделенного элемента, затем просматриваются столбцы и вычёркиваются те, которые содержат не более одного выделенного элемента и т.д. Процесс вычеркивания завершается в двух случаях:
1. Все элементы вычеркнуты.
2. В каждой из невычеркнутых строк и столбцов содержатся не менее
двух выделенных элементов.
Имеют место следующие утверждения.
Утверждение 1. Столбцы Pij , соответствующие вычеркнутым элементам, линейно независимы.
Утверждение 2. Допустимое решение транспортной задачи, построенное
с помощью метода северо-западного угла или метода минимального элемента,
является базисным.
Алгоритм перестроения базисного решения
Шаг 1. Выбираем i0 j0 0 .
Шаг 2. Полагаем xi0 j0
.
Шаг 3. К транспортной таблице, со всеми выделенными базисными xij и
добавленными к ним , применяется правило вычеркивания. Оставшиеся невычеркнутыми элементы образуют цикл.
Шаг 4. При движении по циклу от расставляются знаки минус и плюс
поочередно.
Шаг 5. Полагаем
min xij .
Шаг 6. Перестраивается базисное решение по формулам
xi0 j0
,
xij нов
xij
,
xij нов
xij
,
xijнов xij
для невычеркнутых элементов.
Шаг 7. Один из элементов, помеченный знаком минус, который после
преобразования стал или был равным нулю, исключается из базиса.
Шаг 8. Переход к Этапу 1.
Замечание. Если после преобразования образовалось два или несколько
xij 0 , то можно убрать любой из этих элементов, однако, так как мы ищем
минимальное значение целевой функции, исключить можно тот элемент, которому соответствует максимальное значение сij .
Утверждение 3. Если в транспортной задаче все Ai и B j являются целыми числами,
то любое допустимое базисное решение также целое.
Пример 4.2. Имеем транспортную задачу (рис. 4.6).
35
Ai
5
3
2
1
8
Bj
4
6
4
2
10
3
2
5
3
7
1
4
3
4
11
2
3
1
5
9
7
8
10
20
Рис. 4.6
Матрица Х – начальное базисное решение, найденное с помощью произвольного выбора xij (рис. 4.7).
Ai
7
7
(1)
7
(2)
1
2
10
2
6
9
8
6
20
10 6
(5)
10
10
(6)
8
8
(3)
8(4)
Bj
1
4
11
4
(7)
7
(8)
Рис. 4.7
Вычислим потенциалы:
U1+ V4 =1,
U3+ V5 = 1,
U2+ V3 = 2,
U4+ V2 = 2,
U2+ V5 = 3,
U4+ V4 = 4,
U3+ V1 = 2,
U4+ V5= 5,
U1 = 0,
U2 = 1,
U3 = -1,
U4 = 3,
Занесем полученные результаты в таблицу (рис. 4.8)
Vj
Ui
0
1
-1
3
3
-1
1
1
2
7
7
8
10
Рис. 4.8
36
4
1
2
6
V1 = 3,
V2 = -1,
V3 = 1,
V4 = 1,
V5 = 2.
Для небазисных мест
оптимальность), (рис. 4.9)
Ui
ij
Cij (вычисление оценок и проверка на
Vj
Vj
3
-1
1
1
0
-2
-5
-2
7
1
-1
1
8
-6
-6
7
-5
10
1
2
Ui
3
5
0
6
-3
4
1
2
6
Рис. 4.9
Для введения в базис выбираем клетку (4;1) так как
4;1
5
0 (решение
неоптимальное) и поставим x4;1
.
Определяем цикл, связывающий с базисными элементами, по правилу
вычеркивания.
min xij 6 (рис. 4.10).
Расставим знаки при элементах цикла.
(1)
7
7
1 (5)
82+
10
4 6(2)
(3)
(4)
Рис. 4.10
Продолжаем перестраивать базисное решение (рис. 4.11 – 4.14).
Vj
Ui
-2
-1
-4
1
7
-3
0
-7
-5
-7
6
1
-1
7
3
1-
4
2-
-1
-5
2
8+
3
6+
10
-4
4-
Рис. 4.11
7
7
26+
4-
10
1
Рис. 4.12
37
-5
18+
-5
Vj
Ui
-2
-1
-1
1
-3
0
-7
-5
-4
7
-5
3
-2
-4
7
1
-3
-1
-2
4
1-
3
7+
10
-1
2
3-
9
-5
Рис. 4.13
7
1
7
-
1
7+
9
-
10
3
1
Рис. 4.14
Новое базисное решение и новые оценки представлены на рис. 4.15.
Vj
-2
0
3
2
3
-7
-2
-2
8
-1
-1
1
-1
7
1
1
2
-3
-1
9
-3
Ui
-5
-4
-4
7
-3
-4
10
-1
Рис. 4.15
Все оценки ij 0 , значит, решение оптимальное.
Вычисляем значение целевой функции:
C (x) 7 1 1 4 7 2 1 3 9 1 8 1 1 2 2 4 73 .
4.5. Транспортные задачи, имеющие усложнения в постановке
Транспортная задача с запретами (в транспортной задаче запрещены
некоторые маршруты перевозок)
Довольно часто в транспортных задачах может оказаться, что между некоторыми поставщиками и потребителями отсутствуют коммуникации.
38
Обозначим через J i множество номеров потребителей, которые связаны
коммуникациями с i-м поставщиком со стоимостью перевозок сij , а через I j –
множество номеров поставщиков, которые связаны коммуникациями с j-м потребителем со стоимостью перевозок сij , тогда математическая модель примет
вид
xij Ai , i 1, m ,
j Ji
xij
B j , j 1, n ,
i Ij
0,
xij
min .
xij ñij
i I j j Ji
Заметим, что в этом случае, даже при выполнении условия баланса, задача может оказаться несовместной.
Такая задача после некоторых преобразований сводится к обычной
транспортной задаче.
Полагаем сij М (М – большое число), где i I j и j J i , полученная
задача решается методом потенциалов
Если в оптимальном решении xij 0 , там где сij М , то исходная задача несовместна.
Если при всех сij М все xij 0 , то найдено решение исходной задачи.
Несбалансированные транспортные задачи
Рассмотрим случай, когда в транспортной задаче условие баланса не выполнено, то есть суммарное наличие продукции больше суммарной потребности либо ,наоборот, спрос превышает предложение.
Так как условие баланса является необходимым и достаточным для существования решения транспортной задачи, то несбалансированную задачу нео бходимо свести к сбалансированной.
Рассмотрим оба случая:
а) Пусть
m
n
Ai
i 1
B j , то есть предложение превышает спрос.
j 1
В этом случае, очевидно, не вся продукция от поставщиков будет отправлена потребителям, поэтому математическая модель примет вид
n
xij
Ai , i 1, m ,
xij
Bj , j
j 1
m
i 1
0,
xij
39
1, n ,
m
n
min .
xij ñij
i 1 j 1
б) Пусть
m
n
Ai
i 1
B j , то есть спрос превышает предложение.
j 1
Математическая модель:
n
xij
Ai , i 1, m ,
xij
Bj , j
j 1
m
1, n ,
i 1
0,
xij
m
n
min .
xij ñij
i 1 j 1
Рассмотрим способ сведения несбалансированных задач а) и б) к сбалансированным.
Для случая а) введём дополнительную переменную xi (n 1) – количество
продукции, которая осталась на складе i-го поставщика, то есть не вывезенная к
потребителям продукция. Получим
n
xij
xi ( n
Ai ,
1)
j 1
m
xij
B j , j 1, n ,
i 1
m
m
xi ( n
n
Ai
1)
i 1
i 1
ci (n
Bj
B( n 1) ,
j 1
0
1)
или
n 1
Ai , i 1, m ,
xij
j 1
m
xij
Bj , j
1, (n 1) ,
i 1
m
n
xij ñij
min .
i 1 j 1
Таким образом, к таблице исходных данных надо добавить (n 1) -й
столбец с целевыми коэффициентами, равными нулю, и
m
B( n
n
Ai
1)
i 1
Bj .
j 1
Для случая б) введём дополнительную переменную x( m
продукции, которое недодали j-му потребителю.
40
1) j
– количество
m
xij
x( m
1, n ,
Bj , j
1) j
i 1
n
Ai , i 1, m ,
xij
j 1
n
n
x( m 1) j
m
Bj
j 1
A( m 1) ,
Ai
j 1
i 1
c( m
0
1) j
или
m 1
xij
1, n ,
Bj , j
i 1
n
Ai , i 1, (m 1) ,
xij
j 1
m
n
min .
xij ñij
i 1 j 1
К таблице исходных данных добавляется (m 1) строка с целевыми коn
эффициентами, равными нулю, и A( m 1)
m
Ai .
Bj
j 1
i 1
Далее решается сбалансированная транспортная задача с помощью метода потенциалов. После решения добавленный столбец или строка отбрасываются.
Пример 4.2. Пусть задана следующая транспортная задача (рис. 4.16):
Ai
.
5 4
3 1
2 20
3 6
2 4
3 8
2 4
5 3
1 7
1 2
3 4
5 10
Bj 12 9 8 5
6
Рис. 4.16
4
Задача несбалансированна, так как
5
Ai
45
Bj
i 1
40 . Поэтому необ-
j 1
ходимо добавить столбец с целевыми коэффициентами, равными нулю, и
B6 45 40 5 (рис. 4.17).
Bj
5
3
2
1
4
6
4
2
3
2
5
3
1
4
3
4
2
3
1
5
0
0
0
0
12
9
8
5
6
5
Рис. 4.17
41
Ai
20
8
7
10
Задача решается методом потенциалов (рис. 4.18).
Vj
3
4
3
1
2
0
Ui
0
-1
-1
-2
-2
-1
2
9
-3
-1
0
0
5
1
5
8
-4
-2
-1
-3
-3
5
-1
-2
-5
-5
-2
10
Рис. 4.18
Окончательный вид оптимального решения после исключения последнего столбца следующий (рис. 4.19):
9
Bj
2
10
12
0
8
5
1
5
Ai
20
8
7
10
9
8 5 6
Рис. 4.19
Из рис. 4.19 видим, что у первого поставщика осталось пять единиц невывезенной продукции.
Вычисляем значение целевой функции:
.
C (x) 9
Пример 4.5.2. Имеем несбалансированную транспортную задачу (рис. 4.20).
Ai
Bj
5
3
2
1
12
4
6
4
2
15
3
2
5
3
10
1
4
3
4
8
2
3
1
5
5
Ai
45
Рис. 4.20
Задача несбалансированна, так как
4
i 1
20
8
7
10
5
Bj
50 . Добавляем стро-
j 1
ку с целевыми коэффициентами, равными нулю, и A5 50 45 5 . Получаем
следующую задачу (рис. 4.21):
Ai
5 4 3
1 2 20
3 6 2
4 3 8
2 4 5
3 1 7
1 2 3
4 5 10
0 0 0
0 0 5
Bj 12 15 10 8 5
Рис. 4.21
Задача решается методом потенциалов (рис. 4.22).
42
Vj
3
4
3
1
2
-
10
2
8
0
-
-
8
-
-
2
-
-
-
5
10
0
-
-
-
0
5
0
-
-
Ui
0
-1
-1
-2
-3
Рис. 4.22
Так как все оценки отрицательны, то решение оптимально. Окончательный вид оптимального решения после исключения последней строки следующий (рис. 4.23):
Ai
10
Bj
2
8
2
10
12 15 10
8
0
5
8
20
8
7
10
5
Рис. 4.23
Потребность второго потребителя не удовлетворена на пять единиц. Оптимальное значение целевой функции
C (x) 10
2
8
89 .
0
Лабораторная работа № 6
Даны матрица С размером (4×5), количество продуктов i-го поставщика
Аi и потребность потребителя B j (рис. 4.24).
Ai
5
3
2
1
Bj
4
6
4
2
3
2
5
3
1
4
3
4
2
3
1
5
Рис. 4.24
Составить план перевозки продукции от поставщиков к потребителям
так, чтобы суммарные затраты на перевозку были минимальными, для чего выполнить следующие задания:
43
1. Сбалансировать задачу.
2. Найти начальное допустимое решение методом:
а) северо-западного угла,
б) минимального элемента.
3. Допустимое решение, найденное методом минимального элемента,
проверить на оптимальность.
4. Если решение в (3) неоптимальное, то найти оптимальное решение с
помощью метода потенциалов.
5. Если в (3) доказана оптимальность, то найти оптимальное решение методом потенциалов, начиная с допустимого решения, найденного методом северо-западного угла.
6. Для оптимального решения найти значение целевой функции.
Значения Ai и B j для различных вариантов приведены в табл. 4.1
Таблица 4.1
Номер
варианта
A1
A2
A3
A4
B1
B2
B3
B4
B5
1
15
9
7
11
12
8
10
9
6
2
16
8
8
10
15
9
7
6
8
3
21
13
12
9
14
11
10
8
7
4
20
10
8
13
13
10
7
9
8
5
18
12
10
12
16
13
9
8
10
6
19
11
9
10
17
12
10
8
7
7
17
8
16
15
15
10
13
9
12
8
22
10
11
9
18
11
12
8
7
9
14
8
7
13
9
10
6
7
8
10
17
10
11
16
14
9
13
6
10
11
11
9
15
7
12
8
10
9
6
12
8
16
8
10
15
9
6
7
8
13
21
12
13
9
11
14
10
8
7
14
10
8
20
13
13
10
9
7
8
15
18
12
10
12
13
10
9
8
16
16
11
19
9
10
17
10
12
8
7
17
17
8
15
16
10
15
12
9
13
18
11
10
9
22
18
11
12
8
7
19
14
7
8
13
9
10
7
6
8
20
16
11
10
17
14
9
10
6
13
44
5. Теория расписаний
5.1. Общие положения
В теории расписаний основное внимание уделяется вопросам оптимального распределения и упорядочения конечного множества требований, обслуживаемых детерминированными системами с одним или несколькими приборами, при различных предположениях относительно характера их обслуживания.
В качестве «приборов» могут фигурировать станки, железнодорожные
пути, учебные помещения, компьютеры и тому подобное. В качестве «требований» – обрабатываемые детали, поезда, группы студентов, программы и тому
подобное. Поскольку природа «приборов» и «требований» для нас безразлична,
пронумеруем их числами 1,2,..., Ì и 1,2,..., n соответственно и в дальнейшем будем говорить об обслуживании требований множества N {1,2,...,n} системой,
состоящей из М приборов: 1,2,..., Ì .
Обычно каждому требованию i N сопоставляется некоторое множество Ì (i ) {1,2,..., M } приборов, каждый из которых может или должен обслуживать это требование. Если каждое требование i может быть обслужено любым прибором L M (i ) , то обслуживающая система называется одностадийной
(с одним или несколькими параллельными приборами).
В многостадийных системах процесс обслуживания требования i включает
li стадий. При этом каждому требованию i N и каждой стадии j (1 j li ) его
обслуживания сопоставляется некоторое множество M (ji ) M (i ) приборов. Требование i на стадии j может быть обслужено любым из приборов L M (ij ) , но не
более чем одним одновременно. В любом случае предполагается, что каждый
прибор одновременно может обслуживать не более одного требования.
Процесс функционирования обслуживающей системы может быть описан
путем задания расписания (календарного плана, временного графика и т.п.), то
есть некоторой совокупности указаний относительно того, какие именно требования какими именно приборами обслуживаются в каждый момент времени.
Обычно предполагается, что каждое требование не может одновременно обслуживаться двумя и более приборами и каждый прибор не может одновременно обслуживать более одного требования.
В теории расписаний рассматриваются различные критерии оптимальности расписания, среди которых наиболее распространенным является критерий
минимизации длины, то есть минимизации общего времени обслуживания всех
требований, вторым по распространению является критерий минимизации среднего времени обслуживания требований.
Среди задач теории расписаний можно выделить полиномиально разрешимые и NP-трудные. Для каждой полиномиально разрешимой задачи суще45
ствует алгоритм, трудоемкость которого (число выполняемых элементарных
операций, время решения) ограничена сверху некоторым полиномом от длины
записи исходной информационной задачи. Для NP-трудных задач такие алгоритмы не известны.
Если многостадийная система состоит из М последовательных приборов
и с одинаковым их порядком прохождения для всех требований, то такая с истема называется системой конвейерного типа.
В системе конвейерного типа номер прибора, как правило, совпадает с
номером стадии. В зарубежной литературе она известна под названием flow
shop.
Заметим, что в конвейерной системе, для того чтобы задать расписание,
нужно задать очередность обслуживания требований, то есть если имеется N
требований, которые должны быть обслужены, то расписание можно задать в
виде перестановки из N элементов:
(i1 , i2 , i j ,..., iN ) ,
где i j – номер требования стоящего в расписании на месте j.
5.2. Задача о назначениях
5.2.1. Постановка задачи
Вербальная модель
Пусть имеется n – приборов (станков) и n – требований (деталей). Каждое
требование может обслуживаться (каждая деталь может обрабатываться) на
любом из приборов.
t ij – длительность обслуживания i-го требования на приборе j.
Требуется распределить все требования по приборам так, чтобы на каждый прибор попало ровно одно требование и чтобы среднее время обслуживания было минимальным.
Математическая модель
Введем
xij {0,1}
(5.2.1)
xij 1 , если i-е требование обслуживается j-м прибором;
xij 0 , если i-е требование не обслуживается.
Ограничения:
n
xij
1, i 1, n ,
(5.2.2)
j 1
каждое требование обслуживается ровно одним прибором.
n
xij
1,
j
1, n ,
i 1
каждый прибор обслуживает ровно одно требование.
Целевая функция имеет вид
46
(5.2.3)
m
1
n
f ( x)
n
tij xij
min .
i 1 j 1
Замечание. Так как коэффициент 1 не влияет на положение оптимальn
ной точки, то целевую функцию можно заменить на функцию
m
n
c( x)
min ,
cij xij
(5.2.4)
i 1 j 1
где cij
tij .
5.2.2. Способ задания задачи о назначениях и ее анализ
Как видно из математической модели (5.2.1)-(5.2.4), задача о назначениях
является транспортной задачей с квадратной матрицей C (cij ) , в которой для
всех i и j, ai b j 1 , поэтому, чтобы задать задачу о назначениях, достаточно
только задать квадратную матрицу С.
Заметим, что задача о назначениях является транспортной задачей, если
ограничение (5.2.2) заменить ограничением xij 0 . Возникает вопрос, если исправленную задачу решить методом потенциалов, то будет ли решение удовлетворять ограничению (5.2.2).
Однако известно, что транспортная задача с целыми правыми частями
имеет целочисленное решение. Правые части задачи о назначениях равны единице, то есть целым числам, значит, и все xij также целые числа, при этом из
(5.2.2)-(5.2.3) следует, что все xij 1 , следовательно, они могут принимать значения только ноль и единица.
Отсюда любое допустимое решение задачи о назначениях может быть
представлено в виде квадратной матрицы Х, в которой в каждом столбце и каждой строке имеется по одной единице. Все остальные элементы матрицы равны
нулю. Например, матрица Х может иметь вид (рис. 5.1).
1
Х=
1
1
1
Рис. 5.1
То есть матрица Х имеет ровно n ненулевых элементов. Если решать задачу методом потенциалов, то базисное решение х должно иметь (2n-1) базисную компоненту, и так как число единиц равно n, то базисное решение должно быть дополнено (n-1) нулем. Отсюда следует, что базисное решение является сильно
вырожденным, а это является существенной помехой для использования метода
потенциалов ( часто будет равно нулю). Поэтому для решения задачи о
назначениях может быть предложен другой метод, существенно использующий
47
тот факт, что ненулевые компоненты решения равны единице. В этом случае
матрицу Х можно вообще не задавать, а на матрице С пометить (крышкой) элементы, которым соответствуют единичные компоненты матрицы Х. Тогда значение целевой функции будет равно
C ( x)
cij .
Рассмотрим свойства матрицы С.
Свойство 1. Если из всех элементов одной строки или одного столбца
матрицы С вычесть одно и то же число а , то оптимальное решение новой задачи будет совпадать с оптимальным решением исходной задачи, а оптимальное
значение целевой функции новой задачи уменьшится по сравнению с оптимальным значением целевой функции исходной задачи на величину а :
C í ( x* ) C ( x* ) à .
Свойство 2. Без ограничения общности мы можем считать, что cij 0 .
Свойство 3. Пусть все cij
0 и существуют cij
0 , тогда, если удается
найти допустимое решение x* такое, что все x ij* 1 соответствуют cij 0 , то
полученное допустимое решение оптимально.
Определение 1. Пусть все элементы матрицы С больше или равны нулю и
существуют cij 0 . Нули матрицы С называются независимыми, если они стоят в разных строках и столбцах матрицы С.
Так как любое допустимое решение задачи о назначениях имеет n единиц, стоящих в разных строках и столбцах, то, как следует из Свойства 3, для
того, чтобы могло быть найдено оптимальное решение задачи о назначениях,
надо, чтобы матрица С имела n независимых нулей. Отсюда следует, что для
нахождения оптимального решения необходимо воспользовавшись свойством
1, путем вычитания из строк и столбцов некоторых чисел, получить новую матрицу С, имеющую n независимых нулей. Этот метод называется Венгерским
методом.
5.2.3. Венгерский метод
Венгерский метод состоит из четырех этапов:
Этап 1. Приведение матрицы.
Этап 2. Подсчет k – числа независимых нулей.
Этап 3. Преобразование матрицы С с целью получения новых нулей.
Этап 4. Поиск независимых нулей и получение оптимального решения.
Блок-схема последовательности выполнения этапов Венгерского метода
приведена на рис. 5.2
48
Начало
Этап 1
Этап 2
нет
да
Этап 3
Этап 4
k=n
Конец
Рис.5.2. Блок-схема выполнения этапов Венгерского метода
Рассмотрим каждый этап подробно.
Этап 1. Приведение матрицы
Определение 2. Матрица С называется приведенной, если она имеет в
каждой строке и в каждом столбце, по крайней мере, один ноль.
Матрица С легко приводится с помощью первого свойства, то есть вычитанием из строк и столбцов минимального элемента.
Алгоритм выполнения первого этапа
Шаг 0. S 0 .
Шаг 1. В каждой строке определяется ai min cij .
j
Шаг 2. Для всех cij полагают cij
Шаг 3. S
cij
ai .
n
S
ai .
i 1
Шаг 4. Для каждого j полагают b j
Шаг 5. Для всех cij полагают cij
Шаг 6. S
min cij .
i
cij
bj .
m
S
bj .
j 1
Шаг 7. Переход ко второму этапу.
Этап 2. Подсчет k – числа независимых нулей
Пусть мы хотим вычеркнуть независимые нули горизонтальными или
вертикальными линиями. Заметим, что никакие два независимых нуля нельзя
49
вычеркнуть одной горизонтальной или вертикальной линией, так как они стоят
в разных столбцах и строках. То есть если мы хотим вычеркнуть все независимые нули горизонтальными и (или) вертикальными линиями, то число этих линий будет совпадать с числом независимых нулей. Отсюда следует, что для того чтобы определить, сколько независимых нулей имеет матрица С, достаточно
все нули матрицы С вычеркнуть минимально возможным числом горизонтальных и (или) вертикальных линий.
Рассмотрим следующую матрицу (рис. 5.3):
0
0
0
0
0
0
0
Рис. 5.3
Эта матрица является приведенной, так как в каждой строке и в каждом
столбце имеется, по крайней мере, один ноль. При этом все нули могут быть
вычеркнутыми двумя линиями: вертикальной и горизонтальной, - то есть эта
матрица имеет всего два независимых нуля (рис. 5.4).
0
0
0
0
0
0
0
Рис. 5.4
Отсюда сформулируем алгоритм второго этапа.
Алгоритм выполнения второго этапа
Шаг 1. Отыскивается строка, содержащая один ноль. Этот ноль вычеркивается вертикальной линией. Процесс продолжается, пока может быть найдена
строка, содержащая один ноль.
Шаг 2. Отыскивается столбец, содержащий один ноль. Этот ноль вычеркивается горизонтальной линией. Процесс продолжается, пока может быть
найден столбец, содержащий один ноль.
Шаг 3. Просматриваются невычеркнутые элементы матрицы С.
Шаг 4. Если среди невычеркнутых сij имеются cij 0 , то переход
к Шагу 7.
Иначе Шаг 5.
Шаг 5. Подсчитывается число линий k.
Шаг 6. Если k n , то переход к четвертому этапу. Если k n , то переход к третьему этапу.
50
k1
k2
Шаг 7. Просматриваются строки матрицы С и подсчитывается
min ki , где k i – число невычеркнутых нулей в i-й строке ( k1 2 ).
Шаг 8. Просматриваются столбцы матрицы С и подсчитывается
min k j , где k j – число невычеркнутых нулей в j-м столбце.
Шаг 9. Если k1 k 2 , то выбирается строка, содержащая k1 нулей, и все
нули вычеркиваются вертикальными линиями. Переход к Шагу 1.
Шаг 10. Если k 2 k1 , то выбирается столбец, содержащий k 2 , невычеркнутых нулей и все нули вычеркиваются горизонтальными линиями. Переход к
Шагу 2.
Замечание. В случае выхода на восьмой, девятый или десятые шаги, алгоритм, к сожалению, не гарантирует получение минимального числа линий, так
как эти шаги являются эвристическими. Студенты могут попробовать предложить свои подходы к вычеркиванию нулей для случаев, когда их более одного в
строке или столбце.
Этап 3. Преобразование матрицы С с целью получения новых нулей
Третий этап осуществляется, если полученное на втором этапе число независимых нулей недостаточно, поэтому необходимо преобразовать матрицу
так, чтобы получить новые нули. Пометим через сij те элементы матрицы С,
которые вычеркнуты одной линией, через сij - те элементы, которые вычеркнуты одновременно горизонтальной и вертикальной линиями, невычеркнутые
элементы сij помечать не будем.
Алгоритм выполнения третьего этапа
Шаг 1. Найдем с min сij (из невычеркнутых сij ).
Шаг 2. Элементы матрицы С преобразуются по следующему правилу:
сij сij c (для невычеркнутых),
сij
сij (для вычеркнутых одной линией),
сij
сij c (для вычеркнутых одновременно двумя линиями).
Шаг 3. S S (n k )c .
Шаг 4. Переход ко второму этапу.
Покажем, что приведенный алгоритм есть формализация преобразования
матрицы с помощью ( n k ) шагов, основанных на первом свойстве матрицы С.
Шаги 2-3 могут быть представлены следующим образом.
Шаг 2. Из всех строк вычисляется с, то есть cij cij c .
Шаг 3. S S nc .
Шаг 4. Ко всем вычеркнутым строкам и столбцам прибавляется число с,
то есть все вычеркнутые сij определяются по формуле cij cij c .
51
Шаг 5. S S nc kc S c(n k ) .
Отсюда получается, что после второго шага все элементы матрицы С
уменьшаются на величину c. Следовательно, все нули становятся отрицательными числами, равными ( c ), после четвертого шага все вычеркнутые элементы увеличиваются на с, при этом если элементы были вычеркнуты одной линией, то они не изменяются по сравнению с исходными значениями, а те элементы, которые были вычеркнуты горизонтальной и вертикальной линиями, одновременно увеличились на с, так как с один раз вычиталось и два раза прибавлялось. Именно эта процедура описана в алгоритме, но более кратко.
Этап 4. Поиск независимых нулей и получение оптимального решения
Алгоритм четвертого этапа подобен алгоритму второго этапа, однако
имеет некоторые модификации.
Алгоритм выполнения четвертого этапа.
Шаг 1. В матрице размера ( n n ) помечаются места всех нулей.
Шаг 2. L n .
Шаг 3. Отыскивается строка, содержащая один ноль. Этот ноль выделяется, а соответствующие строка и столбец вычеркиваются. L n 1 . (Процесс
продолжается пока существует строка, содержащая один ноль.)
Шаг 4. Если L 0 , то переход к Шагу 11. Иначе Шаг 5.
Шаг 5. Отыскивается столбец, содержащий один ноль. Этот ноль выделяется, а соответствующие строка и столбец вычеркиваются. L n 1 . (Процесс
продолжается пока существует столбец, содержащий один ноль.)
Шаг 6. Если L 0 , то переход к Шагу 11. Иначе Шаг 7.
Шаг 7. Просматриваются строки и определяется k1 min ki – число невычеркнутых нулей в i-й строке.
Шаг 8. Просматриваются строки и определяется k 2 min k j – число невычеркнутых нулей в j-м столбце.
Шаг 9. Если k1 k 2 , то выбирается строка, содержащая k1 нулей, один из
нулей выделяется, а строка и столбец вычеркиваются. L L 1.
Переход к Шагу 3.
Шаг 10. Если k1 k2 , то выбирается столбец, содержащий k 2 нулей, один
из нулей выделяется, а строка и столбец вычеркиваются. L L 1.
Переход к Шагу 3.
Шаг 11. На исходной матрице С помечаются элементы c ij соответствующие помеченным нулям.
Шаг 12. Вычисляется целевая функция
c( x)
c ij .
Шаг 13. Сравнивается c(x) и S. Эти значения должны совпасть.
Пример 5.1 Дана матрица С (рис. 5.5). Решить задачу о назначениях.
52
3
6
8
4
2
5
1
5
8
10
12
10
4
9
10
9
3
7
4
6
2
6
10
12
14
10
5
4
9
15
16
15
11
6
12
10
Рис. 5.5
Этап 1
Шаг 0. S=0.
Шаг 1 (рис. 5.6).
ai
3
6
8
4̂
2
5
1
5
4̂
9
10
9
3
7
4̂
6
2
6
8
10
12
10
4̂
10
12
14
10
5
15
16
15
3
4
2
5
1
5
1̂1
6
12
9 1̂0
Рис.5.6
Шаг 2. Из строк матрицы вычитаем соответствующее ai (рис. 5.7)
0
0
0
0
0
0
3
4
2
1
1
1
1
5
7
5
6
8
8 10 12
4
5
5
2
3
4
2
4
5
Рис. 5.7
Шаг 3. S=0+20=20.
Шаг 4 (рис. 5.8).
0
0
0
0
0
0
0
3
4
2
1
1
1
1
12
12
13
6
5
7
1
5
7 12
5
6
8 12
8 10 12 13
4
5
5
6
2
3
4
5
2
4
5
7
1
3
4
5
bj
Рис. 5.8
Шаг 5. Из каждого столбца вычитаем соответствующее b j (рис. 5.9).
53
0
0
0
0
0
0
2
3
1
0
0
0
0
2
4
3
7
7
3
2
1
0
1
1
Рис.5.9
3
4
8
1
0
1
7
7
6
1
0
2
Шаг 6. S=20+0+1+1+3+4+5=34.
Этап 2
Подсчет k – числа независимых нулей (рис. 5.10)
0
2
0
2
3
0
3
4
3
4
0
1
7
7
8
0
0
3
2
1
0
0
1
0
0
0
0
1
1
1
7
7
6
1
0
2
Рис. 5.10
k 4 переход к Этапу 3.
Этап 3
Шаг 1. с=1.
Шаг 2. Элементы матрицы С (рис. 5.110преобразуются по следующему правилу:
сij сij c (для невычеркнутых),
сij
сij (для вычеркнутых одной линией),
сij
сij
c (для вычеркнутых одновременно двумя линиями).
0
0
0
0
1
0
2
3
1
0
1
0
0
1
4
2
7
6
3
1
2
0
1
0
Рис.5.11
2
3
7
0
0
0
6
6
5
0
0
1
Шаг 3. S 34 (6 2) 1 36 .
Переход к этапу 2.
Этап 2
Подсчет k – числа независимых нулей (рис. 5.112).
54
0
0
0
0
1
0
k1
3, k 2
2 : k1
2
3
1
0
1
0
0
1
4
2
7
6
3
1
2
0
1
0
Рис.5.12
k 2 . Выбираем столбец. k
2
3
7
0
0
0
6
6
5
0
0
1
5.
Переход к этапу 3.
Шаг 1. с=1.
Шаг 2. Аналогично предыдущей итерации (рис. 5.13).
0
0
0
1
2
1
1
2
0
0
1
0
0
0
4
1
7
5
4
1
3
0
2
0
Рис. 5.13
1
2
6
0
0
0
5
5
4
0
0
1
1
2
0
0
1
0
0
0
4
1
7
5
4
1
3
0
2
0
Рис . 5.14
1
2
6
0
0
0
5
5
4
0
0
1
0
0
0̂
Шаг 3. S 34 (6 5) 1 37 .
Переход к этапу 2 (рис. 5.14).
0
0
0
1
2
1
k1
2, k 2
2:k
6.
Переход к этапу 4 (рис. 5.15).
0
0
0̂
0̂
0
0̂
0
0̂
0
0
0
0̂
Рис. 5.15
Переносим места выделенных нулей на исходную матрицу С. Получаем
C ( x) 4 4 4 11 4 10 37 S .
55
Лабораторная работа №7
Дана матрица С (рис. 5.16).
3
4
2
5
1
5
6
8
4
6
2
6
4
9
10
9
3
7
8
10
12
10
4
9
10
12
14
10
5
10
15
16
15
11
6
12
Рис. 5.16
Решить задачу о назначениях.
Для каждого варианта в исходной матрице С вычеркнуть три элемента.
Координаты вычеркиваемых элементов приведены в табл. 5.1.
Таблица 5.1
Номер Координаты
варианта
1
2
(1,3);(2,1);
(3,2)
(1,3);(2,1);
(4,5)
Номер Координаты
варианта
9
10
11
(1,3);(2,1);
(5,6)
(1,3);(2,1);
(6,4)
(1,3);(3,2);
(4,5)
Номер
варианта
3
4
Координаты
(1,3);(3,2);
(5,6)
(1,3);(3,2);
(6,4)
Номер Координаты
варианта
12
13
14
Номер
варианта
5
6
Номер
варианта
(1,3);(4,5); 15
(5,6);
(1,3);(4,5); 16
(6,4)
(1,3);(5,6); 17
(6,4)
Координаты
Номер
Координаты
варианта
(2,1);(3,2);
(4,5)
(2,1);(3,2);
(5,6)
Координаты
7
8
Номер
варианта
(2,1);(3,2); 18
(6,4)
(2,1);(4,5); 19
(5,6)
(2,1);(4,5); 20
(6,4)
(2,1);(5,6);
(6,4)
(3,2);(4,5);
(5,6)
Координаты
(3,2);(4,5);
(6,4)
(3,2);(5,6);
(6,4)
(4,5);(5,6);
(6,4)
5.4. Система конвейерного типа с двумя приборами
5.4.1 Постановка задачи
Вербальная модель
Имеем n деталей, которые должны быть обработаны последовательно на
первом и втором станках.
аi – время обработки на первом станке,
56
b j – время обработки на втором станке.
Требуется определить, в какой последовательности следует обрабатывать
детали, чтобы выполнить эту работу за минимальное время.
Задача Джонсона
В сборном концерте должны выступать n артистов. Каждый из них должен готовиться к своему номеру в течение времени аi , а время пребывания артиста на сцене – b j . В гримерной одновременно может находиться один человек, так же как и на сцене. Требуется определить порядок выхода артистов на
сцену, так чтобы время перерывов было минимально.
Вербальная модель Задачи Джонсона в терминах теории расписаний
Имеем n требований, каждое их которых должно быть последовательно
обслужено на первом и втором приборах.
аi – время обслуживания i-го требования на 1-м приборе;
b j – время обслуживания i-го требования на 2-м приборе.
Требуется задать расписание обслуживания, минимизирующее общее
время обслуживания.
5.4.2. Диаграмма Гантта
Любое расписание для конвейерной системы можно представить в виде
диаграммы Гантта.
Рассмотрим систему из трех требований, исходные данные для которой
представлены в табл. 5.2.
Таблица 5.2
i
1
2
3
1
1
3
аi
2
1
2
bj
Расписанию 1 (1,2,3) соответствует следующая диаграмма Гантта
(рис. 5.17):
1
2
3
4
5 6
7
Рис. 5.17
57
На рис. 5.17 жирной линией показано время простоя, а Х – общее время обслуживания и Х=7.
Если требования обслуживать в порядке 2 (3,2,1) , то диаграмма Гантта будет иметь следующий вид (рис. 5.18):
1
2
3
4
5
6
7 Рис.
8
5.18
Общее время обслуживания Х=8.
Рис. 5.17-5.18 показывает, что длина расписания зависит от порядка обслуживания требований.
5.4.3. Вычисление длины расписания
Пусть задано расписание , введем обозначения:
a
f i ( ) – момент завершения обслуживания на первом приборе требования, стоящего в расписании на i-м месте;
f i b ( ) – момент завершения обслуживания на втором приборе требования, стоящего в расписании
на i-м месте;
max
F ( ) – длина расписания .
Так как требования обслуживаются последовательно, то длина расписания – это момент завершения обслуживания последнего требования на втором
приборе, то есть
F max ( ) f nb ( ) .
Из анализа диаграмм Гантта (см. рис. 5.4.1-5.4.2) получаем формулы для
вычисления f i a ( ) , f i b ( ) :
f1a ( ) ai ,
f i a ( ) f i a1 ( ) ai ,
f1b ( ) f1a b1 ,
f i a ( ) max( f i a ( ); f i a1 ( )) bi ,
f i b ( ) max( f i a ( ); f i b1 ( )) bi .
58
Пример 5.2. Дано пять деталей, которые последовательно обрабатываются на двух станках. Время обработки каждой детали на каждом станке указано в табл. 5.3.
Таблица 5.3
i
1 2 3 4 5
ai 3 1 5 2 4
bi 5 3 1 4 2
Если составить расписание обработки деталей в данном порядке, то получим
(табл. 5.4)
Таблица 5.4
σ 1 2 3 4 5
fia 3 4 9 11 15
fib 8 11 12 16 18
Здесь общее время обработки деталей составило 18.
Возьмем другое расписание: σ = (2,4,1,5,3), (табл. 5.5).
σ 2
1
4
fia
fib
4
3
8
Таблица 5.5
1 5 3
6 10 15
13 15 16
Здесь общее время обслуживания равно 16.
Достаточное условие оптимальности расписания
Теорема. Если в расписании
го j выполняется условие
min( ai , b j )
для любого требования i предшествующеmin( a j , bi ) ,
(5.4.1)
то расписание оптимально.
5.4.4. Алгоритм построения расписания минимальной длины
Условие (5.4.1) является достаточным для оптимальности расписания. То
есть если для любой пары требований (i, j) из некоторого расписания условие
(5.4.1) выполнено, то расписание оптимально. Однако строить оптимальное
расписание с его помощью не слишком удобно, так как требуется большое количества проверок и переборов. Поэтому ниже будет предложен алгоритм построения расписания, удовлетворяющего условию (5.4.1), то есть являющегося
оптимальным.
Алгоритм Джонсона
59
Шаг 1. В первую группу заносятся требования, у которых ai bi ; во вторую группу заносятся требования, у которых ai bi .
Шаг 2. Требования из первой группы сортируются по неубыванию аi и в
таком порядке занимают первые место в расписании.
Шаг 3. Требования из второй группы сортируются по невозрастанию bi и
занимают в таком порядке последующие места в расписании.
Пример 5.3. Дано пять деталей, которые последовательно обрабатываются на двух станках. Время обработки каждой детали на каждом станке указано в табл. 5.4.5.
Таблица 5.6
i
1 2 3 4 5
ai 3 1 5 2 4
bi 1 3 2 4 5
В соответствии с требованиями алгоритма разобьем требования на группы
(табл. 5.7):
Таблица 5.7
I группа
II группа
ai
i
ai
2
1
ai
bi
4
2
5
4
i
bi
bi
1
1
3
2
Оптимальное расписание
(2,4,5,3,1) .
Длина расписания вычисляется в табл. 5.8.
σ
fia
fib
2
1
7
4
3
8
Таблица 5.8
5 3 1
7 12 15
13 15 16
Здесь общее время обслуживания равно 16.
Замечание о сложности алгоритма. Поскольку алгоритм построения
оптимального расписания состоит из сортировки, а сложность сортировки имеет порядок N ln N , то можно сказать, что задача Джонсона с двумя приборами
имеет полимиальную сложность.
5.5. Конвейерная система с тремя и более приборами
Как было показано выше, задача построения оптимального расписания с
двумя приборами имеет полимиальную сложность.
60
К сожалению, если система имеет три и более прибора, то в общем случае
она является NP-трудной задачей, то есть не существует простых алгоритмов
построения оптимального расписания для такой системы.
Однако существуют частные случаи, в которых возможно построение оптимального расписания с помощью простых алгоритмов.
Будем рассматривать в дальнейшем систему с тремя приборами. Длительность обслуживания требований на первом, втором и третьем приборах
обозначим ai , bi и сi соответственно.
5.5.1. Вычисление длины расписания для системы с тремя приборами
Пусть время обслуживания требований на первом, втором и третьем приборах ai , bi , сi и f i a , f i b , f i c – моменты завершения обслуживания требования, стоящего на i-м месте в расписании на первом, втором и третьем приборах
соответственно.
Тогда
f1a ( ) ai ,
f i a ( ) f i a1 ( ) ai ,
f1b ( ) f1a bi ai bi ,
f i b ( ) max( f i a ( ); f i b1 ( )) bi ,
f1c ( ) f1b ( ) c1 a1 b1 c1 ,
f i c ( ) max( f i b ( ); f i c1 ( )) ci ,
откуда
F1max ( ) f nc ( ) .
Пример 5.4. Дано пять деталей, которые последовательно обрабатываются на трех станках. Время обработки каждой детали на каждом станке указано в
табл. 5.9. Вычислить длину расписания.
i
ai
bi
ci
Расписание
1
3
1
2
2
1
3
5
3
5
2
3
Таблица 5.9
4 5
2 4
4 5
1 4
(2,4,5,3,1) . Длина расписания вычисляется в табл. 5.10.
Таблица 5.10
2 4 5 3 1
f a 1 3 7 12 15
i
fib 4
fic 9
8
13 15 16
10 17 20 22
61
Здесь общее время обслуживания составит F1max ( ) 22 .
5.5.2. Системы, для которых возможно построение
оптимального расписания
Как было сказано выше, задача для системы с тремя приборами является
NP-трудной. Однако существуют частные случаи, для которых возможно построение оптимального расписания с помощью конструктивного алгоритма.
Можно показать, что если
max bi min ai
(5.5.1)
i
i
или
max bi
i
min ci ,
i
(5.5.2)
то достаточным условие оптимальности расписания является условие
min( ai bi ; b j c j ) min( a j b j ; bi ci ) ,
следовательно, если система удовлетворяет условию (5.5.1) или (5.5.2), то при
введении
ai ai bi ,
bi bi ci ,
можно свести задачу к системе с двумя приборами и найти оптимальное расписание с помощью алгоритма построения расписания (алгоритма Джонсона).
Заметим, что длина найденного расписания будет искаться для исходной
системы.
Пример 5.5. Имеются пять деталей, которые последовательно обрабатываются на трех станках. Время обработки каждой детали на каждом станке
указано в табл. 5.11.
Таблица 5.11
i
1 2 3 4 5
ai 3 4 5 4 6
bi 3 1 2 4 3
ci 2 5 1 6 4
Данная система удовлетворяет условию (5.4.1). Сведем ее к системе с
двумя приборами (табл. 5.12) и решим с помощью алгоритма Джонсона.
i
ai
bi
1
6
5
2
5
6
Таблица 5.12
3 4 5
7 8 9
3 10 7
62
В соответствии с требованиями алгоритма разобьем требования на группы
(табл. 5.13):
Таблица 5.13
I группа
II группа
ai
i
ai
bi
2
5
ai
4
8
i
bi
Оптимальное расписание
в табл. 5.14
fia
*
2
4
bi
1
5
3
3
5
7
(2,4,5,1,3) . Длина расписания вычисляется
Таблица 5.14
5 1 3
14 17 22
4
8
f i b 5 12 17 20 24
f c 10 18 22 24 25
i
Здесь общее время обслуживания составит F1max (
*
)
25 .
5.5.3. Эвристические алгоритмы
Поскольку построение оптимального расписания с помощью конструктивных алгоритмов для системы с тремя и более приборами возможно только в
редких и частных случаях, то для построения сколько-нибудь приемлемых расписаний важную роль приобретают эвристические алгоритмы.
Здесь предлагаются три наиболее известных правила построения субоптимальных расписаний для системы с тремя приборами.
Правило 1. Сведение к двум приборам.
Как было сказано выше, это правило дает оптимальное расписание для
частных случаев. Однако можно предположить и опыт показывает, что это действительно так, что его (правило) можно использовать для систем общего вида.
Правило 2. Вперед требование с ближайшей кратчайшей операцией (то
есть требования должны сортироваться в порядке a1 a2 a3 ... an ).
Оно основано на идее сортировки в первой группе для системы с двумя
приборами.
Правило 3. Вперед требование с длиннейшей остающейся технологией
( b1 c1 b2 c2 b3 c3 ... bn cn ).
Основано на идее сортировки во второй группе.
Решать задачу построения субоптимальных расписаний надо следующим
образом: применить все эвристические правила, для каждого полученного расписания, вычислить его длину и выбрать расписание с наименьшей длиной. Та-
63
кое расписание будет называться рекордным, а его длина – рекордом, то есть
рекордное расписание не обязательно оптимально, но является наилучшим из
известных.
Следует отметить, что при применении каждого из правил может быть
получено не одно, а несколько расписаний, это возможно в том с лучае, когда
некоторое соотношение, используемое в данном правиле, выполняется как
строгое равенство, то есть, например, ai a j (второе правило), тогда можно
взять два расписания: i  j , в другом j  i .
Пример 5.6. Имеются пять деталей, которые последовательно обрабатываются на трех станках. Время обработки каждой детали на каждом станке
указано в табл. 5.15.
Таблица 5.15
i
1 2 3 4 5
ai 3 7 7 4 1
bi 1 6 10 7 2
ci 1 9 4 3 9
Применим Правило 1: сведем исходную задачу к задаче с двумя приборами,
полученную задачу (табл. .5.16) решим с помощью алгоритма Джонсона.
i
ai
bi
1
4
2
Таблица 5.16
2 3 4 5
13 17 11 3
15 14 10 11
В соответствии с требованиями алгоритма разобьем требования на группы
(табл. 5.17):
Таблица 5.17
I группа
II группа
ai
bi
ai
i
bi
2
5
i
1
3
4
ai
13
3
2
14
10
bi
Получим расписание 1 (5,2,3,4,1), длина которого вычисляется в табл.
5.18.
f
f
f
1
a
i
b
i
c
i
Таблица 5.18
3 4 1
15 19 22
5
1
2
8
3
14 25 32 33
12 23 29 35 36
64
Здесь общее время обслуживания составит F1max ( 1 ) 36 .
Применим Правило 2. Вперед требование с ближайшей кротчайшей операцией.
(5,1,4,2,3) ,
(5,1,4,3,2) . Вычислим длину каждого расписания
2
3
(табл. 5.19 – 5.20).
Таблица 5.19
5 1 4 2 3
2
f a 1 4 8 15 22
i
f i b 3 5 15 21 32
f c 12 13 18 30 36
i
Здесь F1max ( 2 ) 36 (табл. 5.19).
f
f
f
3
a
i
b
i
c
i
5
1
1
4
Таблица 5.20
4 3 2
8 15 22
3
5
15 25 31
12 13 18 29 40
Здесь F1max ( 3 ) 40 . (табл. 5.20)
Применим Правило 3. Вперед требование с длиннейшей остающейся технологией.
(2,3,5,4,1) . Вычислим длину расписания (табл. 5.21).
4
Таблица 5.21
2 3 5 4 1
4
f a 7 14 15 19 22
i
f i b 13 24 26 33 34
f i c 22 28 37 40 41
Здесь F1max ( 4 ) 41 .
Здесь два рекордных расписания 1R (5,2,3,4,1) , R2 (5,1,4,2,3) со значением рекорда R 36 .
5.5.4. Оценки длины расписаний
Пусть найдено рекордное расписание r с длиной F max ( r ) R .
65
Хотелось бы знать, насколько полученное расписание близко оптимальному. Для этого найдем нижнюю оценку длины расписания F F max ( ) для
всех , тогда если R F , то r – оптимальное расписание.
Если же R F , то определятся близость рекордного расписания к оптимальному по тому, насколько рекорд отклоняется от нижней оценки. При этом,
конечно, важно, чтобы F было насколько возможно ближе к точной нижней
грани длин расписаний. Для системы с тремя приборами в качестве нижней
грани можно предложить следующее выражение:
(5.5.3)
(5.5.4)
ai min( bi ci ),
F
max
bi min ai min ci ,
(5.5.5)
ci min( ai bi ).
Формула (5.5.3) отражает тот факт, что длина расписания не может быть
меньше, чем время работы первого прибора в сумме со временем обслуживания
на втором и третьем приборах последнего требования.
Формула (5.5.4) означает, что длина расписания не может быть меньше
чем время работы второго прибора с учетом обслуживания первого требования
на первом приборе и последнего требования на третьем приборе.
Формула (5.5.5) означает, что длина расписания не может быть меньше
чем время работы третьего прибора в сумме с временем обслуживания треб ования, стоящего на первом месте в расписаниях на первом и втором приборах.
Найдем оценку длины расписания для примера 5.6.
Здесь
ai 3 7 7 4 1 22 ,
bi 1 6 10 7 2 26 ,
ci 1 9 4 3 9 26 .
F
22 2 24
max 26 1 1 28
26 3 29
29 .
Рекорд R 36 , то есть мы не можем гарантировать оптимальности рекордного расписания. Значение рекорда достаточно сильно отличается от нижней оценки, однако возможно, что оценка слишком занижена.
Лабораторная работа № 8
Для системы с тремя приборами и семью требованиями найти:
66
1.Три или больше расписаний с помощью эвристических правил.
2.Вычислить длину каждого расписания.
3.Определить рекордное расписание и значение рекорда.
4.Вычислить нижнюю оценку длины расписания.
5.Сравнить оценку с рекордом.
Исходные данные приведены в табл. 5.22.
i
ai
bi
ci
1
1
2
9
2
3
1
1
3
6
1
3
4
8
9
4
5
9
7
7
6
7
10
4
7
3
2
3
8
7
6
8
Таблица 5.22
9
10
8
5
9
9
9
7
Для каждого варианта из данной системы нужно исключить три требования в соответствии с правилами из табл. 5.23.
Таблица 5.23
Вариант
1
2
3
4
5
6
7
8
9
10
Номера ис1,3, 2,4, 4,6, 3,5, 1,4, 2,4, 1,2, 5,6, 1,2, 3,4,
ключаемых
5
6
8
7
7
10
3
7
9
5
требований
Вариант
11 12
13
14 15 16 17 18 19 20
Номера ис1,5, 2,7, 4,7, 1,5, 5,6, 2,4, 3,9, 3,6, 1,7, 8,7,
ключаемых
9
8
10
7
10
9
10
9
9
10
требований
67
Библиографический список
1. Азарнова, Т.В. Методы оптимизации. Элементы теории, алгоритмы и примеры / Т.В. Азарнова, И.Л. Каширина, Г.Д. Чернышова. – Воронеж: Воронеж. гос. ун-т, 2004. – 151 с.
2. Аснина, А.Я. Вычислительные методы линейной оптимизации / А. Я. Аснина, Н.Б. Баева, Г.Д.Чернышова.– Воронеж: Изд-во ВГУ, 1987. – 156 с.
3. Ашманов, С.А. Линейное программирование / С.А. Ашманов.– М.: Наука,
1981. – 304 с.
4. Банди, Б. Основы линейного программирования / Б. Банди.– М.: Радио
и связь, 1989. – 176 с.
5. Исследование операций в экономике : учеб. пособие для ВУЗов / Н.Ш. Кремер, Б.А. Путко, И.М. Гришин, М.Н. Фридман; под ред. проф. Н.Ш. Кремера.
– М.: Юнити, 2004. -407 с.
6. Красс, М.С. Основы математики и ее приложения в экономическом образовании: учебник / М.С. Красс, Б.П. Чупрынов. – 2-е изд., испр. – М.: Дело, 2001. – 688 с.
7. Танаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев,
Ю.Н. Сотсков, В.А. Струсевич.– М.: Наука. Гл. ред. физ.-мат. лит., 1989. –
328 с.
8. Таха, Хемеди А. Введение в исследование операций / Хемеди А. Таха.7-е изд.: пер. с англ.- М.: Издательский дом «Вильямс», 2005.-912 с.
9. Замков, О.О. Математические методы в экономике: учебник / О.О Замков. – М.: Дело и Сервис, 2001.- 368 с.
68
ОГЛАВЛЕНИЕ
Введение .............................................................................................................. 3
1. Общая постановка задачи линейного программирования.
Графическое решение ЗЛП. Каноническая форма. ........................................ 4
1.1. Основные определения............................................................................... 4
1.2. Графический метод решения задачи линейного программирования ......... 5
Лабораторная работа №1 .................................................................................. 9
1.3. Каноническая форма задачи линейного программирования. ................... 10
Приведение к канонической форме ................................................................ 10
1.4. Базисное решение ЗЛП............................................................................ 11
1.5. Перестроение базисного решения ЗЛП .................................................... 13
Лабораторная работа № 2................................................................................. 15
2. Симплекс-метод............................................................................................ 15
2.1. Основная теорема линейного программирования .................................... 16
2.2. Алгоритм симплекс метода ...................................................................... 16
Лабораторная работа № 3................................................................................. 18
2.3. Симплекс-метод с искусственным базисом ............................................. 18
Лабораторная работа №4 ................................................................................ 22
3. Двойственность в ЗЛП ................................................................................. 22
3.1. Основные понятия и определения......................................................... 22
3.2. Леммы и теоремы двойственности........................................................... 26
Лабораторная работа № 5 ............................................................................... 28
4. Транспортная задача.................................................................................... 28
4.1. Математическая модель транспортной задачи ......................................... 28
4.2. Построение начального базисного решения ............................................ 31
4.3. Метод потенциалов .................................................................................. 33
4.4. Правило вычеркивания............................................................................. 34
4.5. Транспортные задачи, имеющие усложнения в постановке .................... 38
Лабораторная работа № 6 ............................................................................... 43
5. Теория расписаний....................................................................................... 45
5.1. Общие положения .................................................................................... 45
5.2. Задача о назначениях................................................................................ 46
Лабораторная работа №7 ................................................................................ 56
5.4. Система конвейерного типа с двумя приборами ...................................... 56
5.5. Конвейерная система с тремя и более приборами.................................... 60
Лабораторная работа № 8 ............................................................................... 66
Библиографический список ............................................................................ 68
69
Учебное издание
Аснина Наталия Георгиевна
Учебное пособие
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И МЕТОДЫ ОПТИМИЗАЦИИ
Практикум
для студентов, обучающихся по направлению
230700 «Прикладная информатика»
2-е издание, переработанное и дополненное
Отпечатано в авторской редакции
Подписано в печать 18. 04. 2012. Формат 60×84 1/16. Уч.-изд. л. 4,3
Усл.-печ. л. 4,4. Бумага писчая. Заказ № 175. Тираж 100 экз.
_______________________________________________________________________________________________________
Отпечатано: отдел оперативной полиграфии Воронежского ГАСУ
394006 Воронеж, ул. 20-летия Октября, 84
70
Документ
Категория
Без категории
Просмотров
10
Размер файла
2 161 Кб
Теги
метод, оптимизация, 577, операция, исследование, аснина
1/--страниц
Пожаловаться на содержимое документа