Экономико-математический практикум

РОССИЙСКАЯФЕДЕРАЦИЯ
МИНИСТЕРСТВООБРАЗОВАНИЯ И НАУКИ
ФЕДЕРАЛЬНОЕАГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГОПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ТЮМЕНСКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
ИНСТИТУТДИСТАНЦИОННОГО ОБРАЗОВАНИЯСПЕЦИАЛЬНОСТЬ«Менеджменторганизаций »К О Н Т Р О Л Ь Н А Я Р А Б О Т А
По предмету:Экономико-математический практикум
 
Выполнил:
Студент 2 курса
4 семестр
Рахимова ЛидияРустамовна

Ташкент,2009

Задача № 1
Условно стандартнаязадача линейного программирования
Необходимо выполнить вуказанном порядке следующие задания.
1. Найти оптимальный планпрямой задачи:
а) графическим методом;
б) симплекс-методом (дляпостроения исходного опорного плана рекомендуется использовать методискусственного базиса).
2. Построить двойственнуюзадачу.
3. Найти оптимальный пландвойственной задачи из графического решения прямой, используя условиядополняющей нежесткости.
4. Найти оптимальный пландвойственной задачи по первой теореме двойственности, используя окончательнуюсимплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверитьутверждение «значения целевых функций пары двойственных задач на своихоптимальных решениях совпадают».
5. Двойственную задачурешить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственнойзадачи найти оптимальный план прямой задачи по первой теореме двойственности.Сравнить результат с результатом, который был получен графическим методом (см.п. 1а).
6. Найти оптимальноецелочисленное решение:
а) графическим методом;
б) Методом Гомори.
Сравнить значения функцийцелочисленного и нецелочисленного решений
4/>

Решение задачи 1
1. Найдем оптимальныйплан решения графическим методом:
/>;
/>
Построим на координатной плоскостиОх1х2 граничные прямые области допустимыхрешений (номера прямых соответствуют их порядковому номеру в системе):
/> /> />
Область допустимыхрешений определяется многоугольником ОАВСD (см. график 1).
Для линий уровня х1 — 3х2 = h(h — const) строим нормальный вектор />. Перпендикулярно нормальномувектору построим одну из линий уровня (на рис. 1 она проходит через началокоординат) Так как задача на минимум, то перемещаем линию уровня в направлениивектора /> доопорной прямой. В данном случае опорной прямой является прямая, проходящаячерез точку пересечения граничных прямых L3 и L4, т. е.через точку />.Для определения координат точки P решаем систему уравнений

/>.
Получаем х1= 5,3, х2 = 0,6. Это и будет оптимальным решением даннойзадачи, которому соответствует минимальное значение целевой функции Zmin=3,5

/>

/> />
10   />

6    
/>
4    /> 
/>
P   /> 
/>
2    
/>

 /> /> /> /> /> /> /> />
(4)   /> />
(3)   /> /> />
(2)  

График № 1

1б) Перейдем красширенной задаче:
/>
Данная расширенная задачаимеет начальное опорное решение /> с базисом />. Вычисляем оценкивекторов условий по базису опорного решения и значение целевой функции наопорном решении:
/>
Расчеты проведем втаблице (Табл. 1)
Таблица 1 1 -3 M
Б
Сб
В
А1
А2
А3
А4
А5
А6
А7
 
А3 9 -2 3 1
 
А4 53 5 2 1
 
А5 17 4 -7 1
←
А7
М 37 6 8 1 1
 
/> –1 3
 
/> 37 6 8

Начальное опорное решениене является оптимальным, так как в задаче на минимум имеются положительныеоценки. Выбираем номер вектора Аk, вводимого в базис опорного решения,и вектора Аl, выводимого из базиса. Наибольшая положительная оценка соответствует А2,за разрешающий элемент выбираем коэффициент 8 и выполняем преобразование Жордана.
Вектор А2выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем второеопорное решение /> с базисом /> (табл. 1.3). Целеваяфункция /> =-3М-21. Это решение не является оптимальным, так как есть положительная оценка.
Таблица 1
Б
Сб
B
А1
А2
А3
А4
А5
А6 
А2
-3 3,0 -0,7 1,0 0,3 0,0 0,0 0,0 0,0
А4 47,0 6,3 0,0 -0,7 1,0 0,0 0,0 0,0
А5 38,0 -0,7 0,0 2,3 0,0 1,0 0,0 0,0
a7
М 13,0 11,3 0,0 -2,7 0,0 0,0 1,0 1,0 M+1 -9,0 1,0 0,0 -1,0 0,0 0,0 0,0 0,0  M+2 13,0 11,3 0,0 -2,7 0,0 0,0 0,0 0,0
A2
-3 -2,4 -0,6 1,0 0,0 0,0 -0,1 0,0 0,0
a4 57,9 6,1 0,0 0,0 1,0 0,3 0,0 0,0
А3 16,3 -0,3 0,0 1,0 0,0 0,4 0,0 0,0
A7
М 56,4 10,6 0,0 0,0 0,0 1,1 1,0 1,0 M+1 7,3 0,7 0,0 0,0 0,0 0,4 0,0 0,0 M+2 56,4 10,6 0,0 0,0 0,0 1,1 0,0 0,0
A2
-3 0,6 0,0 1,0 0,0 0,0 -0,1 0,1 0,1
a4 25,1 0,0 0,0 0,0 1,0 -0,4 -0,6 -0,6
А5 17,8 0,0 0,0 1,0 0,0 0,5 0,0 0,0
A1
1 5,3 1,0 0,0 0,0 0,0 0,1 0,1 0,1 3,5 0,0 0,0 0,0 0,0 0,4 -0,1 -0,1 0,0 0,0 0,0 0,0 0,0 0,0 -1,0 -1,0

Целевая функция после второйитерации равна /> = 3,5. Все оценки отрицательные,план оптимален.
/> 
Оптимальный план исходнойзадачи Х*=(х1*=5,3; х2*=0,6).Минимальное значение целевой функции исходной задачи =3,5.
Ответ: min Z(X*) =3,5.
 
2. Двойственная задача
Двойственная задача имеет вид.
/>
при условиях
/>

3. Прямая задача имеетоптимальное решение, вычислим оптимальное решение двойственной задачи,используя условия дополняющей нежесткости
 
/>
Откуда следует:
/>
4. Оптимальный план двойственной задачинайдем, используя окончательную симплекс-таблицу прямой задачи (Табл.1)
/>
Максимальное значениефункции двойственной задачи совпадает с минимальным значением функции прямойзадачи, что подтверждает первую теорему двойственности.
Проанализируем решение задачи, используя условия дополняющейнежесткости (вторую теорему двойственности). Подставляем координатыоптимального решения двойственной задачи Y* = (0;0;-0,35;-0,068), в систему ограничений.
/>
Ответ: Z(X) =3,5 при Х* = (0;0;-0,35;-0,068).
Задача № 2
Каноническая задача
В каждом вариантеприведены таблицы, в которых записаны условия канонической задачи линейногопрограммирования на минимум, т. е.
/>
В первой строке помещены коэффициенты целевой функции. Востальных строках, в первых пяти столбцах, находятся векторы условий, а впоследнем столбце записан вектор ограничений. В правом верхнем углу таблицыуказана цель задачи.
Необходимопоследовательно выполнить следующие задания.
1. Задачу решитьграфическим методом.
2. Применяясимплекс-метод, решить задачу, т.е. найти ее оптимальный план /> и минимальное значениецелевой функции /> или установить, что задача не имеетрешения. Начальный план рекомендуется искать методом искусственного базиса.
3. Построитьдвойственную задачу. Если вектор /> найден, вычислить оптимальныйплан /> двойственнойзадачи, используя первую теорему двойственности />. Вычислить максимальное значениефункции />.
4. Провести анализполученного решения, применяя условия дополняющей нежесткости.
Если />, то />.
Если />, то />. 14 1 -5 6 8 -2 min 11 7 1 12 5 16 14 10 3 8 17 13 2 9 4 6 15
 
Решение задачи 2
Представим исходные данные задачи в виде:
/>
/>
Проверяем, применим ли графическийметод при решении данной задачи.
/>
линейно независимы, таккак их координаты непропорциональны. Поэтому ранг системы векторов-условий r = 3. Находим n — r =5 — 3 = 2 £ 2. Следовательно, метод применим.
1. Приведём системууравнений-ограничений к равносильной, разрешённой методом Жордана–Гаусса. Преобразуем систему уравнений методомЖордана-Гаусса до получения общего решения (табл. 2.1).
Таблица2.1.
№ итерац.
x1
x2
x3
x4
x5
bi
 
(1) 11 7 1 12 5 16 14 10 3 8 17 13 2 9 4 6 15

(2)
-45,00
-33,00
1,00
0,00
-27,00
-52,00
4,67
3,33
0,00
1,00
2,67
5,67
-5,67
-11,33
9,00
0,00
-4,67
-7,67

(3)
2,25
0,75
1,00
10,13
0,00
5,38
1,75
1,25
0,00
0,38
1,00
2,13
2,50
-5,50
9,00
1,75
0,00
2,25
(4)
-12,21
32,57
-51,07
0,00
0,00
-7,64
1,21
2,43
-1,93
0,00
1,00
1,64
1,43
-3,14
5,14
1,00
0,00
1,29
(5)
0,24
-0,64
1,00
0,00
0,00
0,15
1,68
1,20
0,00
0,00
1,00
1,93
0,20
0,14
0,00
1,00
0,00
0,52
Общее решение системыуравнений имеет вид
/>
Учитывая,что все переменные неотрицательны, перейдем от уравнений к неравенствам изобщего решения системы.

/>
откуда получим системунеравенств с двумя переменными
/>
Целевую функцию выразимчерез свободные переменные
/>
Окончательно получимстандартную задачу линейного программирования с двумя переменными
/>
Строим область допустимыхрешений (график 2). Любая точка многоугольника /> удовлетворяет системе неравенств.Вершина /> являетсяточкой входа семейства прямых /> в область решений, следовательно,в этой точке она принимает минимальное значение.
В свою очередь, />=(1,32;0,12).
Решая систему уравнений получаем х1 =2,2, х2=0,6. Это и будет оптимальным решением данной задачи, которому соответствуетминимальное значение целевой функции Zmin
/>.
/>

/> 
6    
/>
4  
/> A
 А/>/>
2    /> /> /> /> /> /> /> />
(2)  

 (3)
график 2
2. Решим симплекс-методом задачу линейного программирования,используя метод искусственного базиса
/>
/>
Составим расширеннуюзадачу. В левые части уравнений системы ограничений вводим неотрицательныеискусственные переменные с коэффициентом +1. Удобно справа от уравненийзаписать вводимые искусственные переменные. В первое уравнение вводимпеременную х6, во второе — переменную х7, втретье – х8. Данная задача — задача на нахождение минимума. Получаем
/>
/>
Данная расширенная задачаимеет начальное опорное решение /> с базисом />. Вычисляем оценкивекторов условий по базису опорного решения и значение целевой функции наопорном решении:

/>
Записываем исходные ирасчетные данные в симплексную таблицу (табл.2.2).
Таблица 2.2 1 -5 6 8 -2
М M M
Б
Сб
А0
А1
А2
А3
А4
А5
А6
A7
A8
 
А6
М 16 11 7 1 12 5 1
 
A7 M 17 14 10 3 8 1
←
А8
М 15 13 2 9 4 6 1
 
/> -1 5 -6 -8 2
 
/> 48 28 19 10 19 19
Начальное опорное решениене является оптимальным, так как в задаче на минимум имеются положительныеоценки. Выбираем номер вектора Аk, вводимого в базис опорного решения,и вектора Аl, выводимого из базиса. В столбце «А3» (см. табл. 2.1)за разрешающий элемент выбираем коэффициент 9 в третьей строке и выполняемпреобразование Жордана.
Вектор А3выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем первое опорноерешение /> сбазисом /> (табл.2.3). Целевая функция /> =31,33М -10. Это решениене является оптимальным, так как имеются положительные оценки.

Таблица 2.3 1 -5 6 8 -2
М M M
Б
Сб
А0
А1
А2
А3
А4
А5
А6
A7
A8
 
А6
М 14,33 9,56 6,78 0,00 11,56 4,33 1,00 0,00 -0,11
 
A7 M 17,00 14,00 10,00 0,00 3,00 8,00 0,00 1,00 0,00
←
А3
6 1,67 1,44 0,22 1,00 0,44 0,67 0,00 0,00 0,11
 
/> 10,00 -7,67 -6,33 0,00 5,33 -6,00 0,00 0,00 -0,67
  31,33 13,56 16,78 0,00 14,56 12,33 0,00 0,00 -1,11
Вводим вектор А4в базис, получаем второе опорное решение (таблица 2.4) /> с базисом />. Целеваяфункция /> =3,38+13,28M. Далее в таблице 2.4 приведенырасчеты с третьей по пятую итерации.
Таблица 2.4
 
  4 2 -1 5 1 М M M
Б
Сб А0 А1 А2 А3 А4 А5 А6 A7 A8
a4
8 1,24 0,83 0,59 0,00 1,00 0,38 0,09 0,00 -0,01
a7 M 13,28 11,52 8,24 0,00 0,00 6,88 -0,26 1,00 0,03
a3
6 1,12 1,08 -0,04 1,00 0,00 0,50 -0,04 0,00 0,12
/>/>   3,38 -12,08 -9,46 0,00 0,00 -8,00 -0,46 0,00 -0,62   13,28 1,52 8,24 0,00 0,00 6,88 -1,26 0,00 -0,97 a4 8 0,52 0,20 0,14 0,00 1,00 0,00 0,10 -0,05 -0,01 a5 -2 1,93 1,68 1,20 0,00 0,00 1,00 -0,04 0,15 0,00 a3 6 0,15 0,24 -0,64 1,00 0,00 0,00 -0,02 -0,07 0,11     18,84 1,33 0,13 0,00 0,00 0,00 -0,76 1,16 -0,58     0,00 -10,00 0,00 0,00 0,00 0,00 -1,00 -1,00 -1,00 a1 1 2,60 1,00 0,69 0,00 5,04 0,00 0,51 -0,27 -0,06 a5 -2 -2,42 0,00 0,04 0,00 -8,44 1,00 -0,89 0,61 0,10 a3 6 -0,47 0,00 -0,80 1,00 -1,20 0,00 -0,14 -0,01 0,13     4,19 0,00 -0,79 0,00 -6,68 0,00 -1,44 1,53 -0,51     25,99 0,00 6,90 0,00 50,35 0,00 4,07 -3,75 -1,56
Целевая функция после пятойитерации равна /> = 4,19. Положительных оценок нет,план оптимален. Ответ: min Z(X*) =4,2.
 
3.Построимдвойственную задачу
Используя вторуюсимметричную пару двойственных задач, составим задачу, двойственную к исходной:
/>
/>
Вводим неотрицательныедополнительные переменные у4, у5, у6у7, у8 для приведения задачи к каноническомувиду:
/>
/>
Находим начальное опорноерешение Y1 = (0,0,0,1,-5,6,8,-2) с базисом Б1 = (А4,А5, А6, А7, А8).Решение задачи симплексным методом приведено в табл. 2.5. (расчеты табл.2.2. итабл.2.4.)
Таблица 2.5 1 -5 6 8 -2
М M M
Б
Сб
А0
А1
А2
А3
А4
А5
А6
A7
A8
←
А6
М 16 11 7 1 12 5 1
 
A7 M 17 14 10 3 8 1
 
А8
М 15 13 2 9 4 6 1
 
/> -1 5 -6 -8 2
 
/> 48 28 19 10 19 19
  a1 1 2,60 1,00 0,69 0,00 5,04 0,00 0,51 -0,27 -0,06
  a5 -2 -2,42 0,00 0,04 0,00 -8,44 1,00 -0,89 0,61 0,10
  a3 6 -0,47 0,00 -0,80 1,00 -1,20 0,00 -0,14 -0,01 0,13
/> 4,19 0,00 -0,79 0,00 -6,68 0,00 -1,44 1,53 -0,51
/> 25,99 0,00 6,90 0,00 50,35 0,00 4,07 -3,75 -1,56 /> /> /> /> /> /> /> /> /> /> /> /> />
Приведем оптимальное решение прямойзадачи
/>
Окончательный базис, соответствующийоптимальному решению прямой задачи, состоит из векторов А2А3А4поэтому базисная матрица имеет вид
/>
Решение прямой задачи начиналось сединичного базиса А6, А7, А8. Поэтому вокончательной таблице указанные столбцы преобразуются в матрицу />, обратную к базиснойматрице />,следовательно,

/>
Оптимальный план двойственной найдемиз соотношения
/>
Откуда /> При этом плане максимальное значение функциидвойственной задачи составляет величину равную
/>
Максимальное значение целевой функциидвойственной задачи совпадает с минимальным значением целевой функции прямойзадачи.
5. Проанализируемрешение задачи,используя условия дополняющей нежесткости (вторую теорему двойственности).
Подставляем координатыоптимального решения двойственной задачи /> в систему ограничений.
/> 

/>
Первое, третье и пятое ограничениявыполняются как строгие неравенства, следовательно, их координаты оптимальногорешения исходной задачи равны нулю: />. Учитывая это, первую, вторую и пятую координатыоптимального решения Х* находим при совместном решенииуравнений-ограничений исходной задачи:
/>
Ответ: Z(X) = 4,2 при Х* = (0;1,6; 0;4,9;0).
Задача № 3
 
Транспортная задача
Ниже приведены числовыеданные транспортных задач. Стоимость перевозки единицы продукции записаны вклетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу.Требуется построить начальный план методами: «северо-западного угла»,«минимального элемента», «двойного предпочтения», методом Фогеля. Из каждогоплана найти оптимальный план методом потенциалов. 24 34 30 39 29 18 82 40 35 45 41 10 36 36 38 41 50 8 79 14 10 13 10 12 80 77 60 22 68 50
 
Решение.
1.Методсеверо-западного угла.
Исходные данные задачисведем в таблицу (табл. 3.1).
 
Таблица 3.1.Поставщики Потребители Запасы
/>
/>
/>
/>
/>
/> 34 30 39 29 18
82
/> 40 35 45 41 10
36
/> 36 38 41 50 8
79
/> 14 10 13 10 12
8 Потребности
77
60
22
68
50
 
 
Решение. Построим опорный план задачи методом северо-западногоугла.
Объем перевозки /> и последовательность заполненияматрицы /> будемзаписывать в соответствующие клетки табл. 3.2.
Цифры, стоящие в скобках над объемами перевозок,обозначают номер шага, на котором определяются эти перевозки.
1. х11(1)=min(82,77)=77.Потребности первого потребителя удовлетворены, исключаем его. Запасы первогопоставщика уменьшились на х11(1) и стали равны (82-77=5)5.
2. х12(1)=min(5,60)=5.Запасы первого поставщика исчерпаны, исключим первую строку. Второй потребительудовлетворил свои потребности на 5 единиц, его спрос уменьшился на величину х11(1)и стал равным 55.
3. х22(3)=min(36,55)=36.После третьего шага ресурсы поставщика А2 исчерпаны. Спроспотребителя B2 равен b2(3)=55-36=19.
4. х23(4)=min(79,19)=19.Следует исключить потребителя B2. Ресурсыпоставщика А3(4) = a3 – х23(4)=79-19=60 составляет 60единиц.
5. х33(5)=min(60,22)=22.Потребитель В3 полностью удовлетворил свой спрос, исключаем столбец3.
6. х34(6)=min(38,68)=38.Следует исключить поставщика А3, запасы которого исчерпаны. Спрос потребителяВ4 в4(6) – х34(5)=68-38=30составляет 30 единиц.
7. х44(7)=min(80,30)=30.Спрос четвертого потребителя удовлетворен. Запасы поставщика А4 составляет
80-30=50.
8. х45(8)=min(50,50)=0.Запасы исчерпаны, потребности удовлетворены.
Опорныйплан построен (табл. 3.2).
Таблица 3.2.
34
3
39
29
18
77(1)
5(2)
82
4
35
45
41
10
 
36(3)
36
36
38
41
50
8
 
19(4)
22(5)
38(6)
79
14
1
13
1
12
 
30(7)
50(8)
8
77
60
22
68
50
Суммарные транспортные издержки наперевозку продукции от поставщиков к потребителю составляют
/> 
2.Метод минимального элемента.
 
Исходные данныепоставщики потребители Запасы
В1
В2
В3
В4
В5
А1 34 30 39 29 18
82
А2 40 35 45 41 10
36
А3 36 38 41 50 8
79
А4 14 10 13 10 12
8 потребности
77
60
22
68
50
 
1. /> Объем запасов и потребностей послепервого шага уменьшается на величину: х31(1)=50; />. Запасы пятого поставщика исчерпаны, потребностипервого потребителя уменьшились на 50 единиц и стали равны 29, исключаем пятыйстолбец.
2. />. Объем запасови потребностей после второго шага уменьшается на величину: х42(2)=60;/>. Потребности пункта В2 удовлетворены,исключим из рассмотрения второй столбец.
3. />.Объем запасов ипотребностей после третьего шага уменьшается на величину: х44(3)=20;/>. Запасы пункта А4исчерпаны, исключим из рассмотрения четвертую строку.
4./>. Корректируем объемы запасов и потребностейпосле четвертого шага: />. Потребности пункта В4удовлетворены, исключим четвертый столбец.
5. />. После пятого шага запасы поставщикаА1 будут исчерпаны, исключаем первую строку. Потребности В1 равны:/>.
6./>. После шестого шага запасы третьего поставщикабудут исчерпаны />, потребности первого потребителя равны/>. Исключаем третью строку.
7. />. После седьмого шага запасы второго поставщикабудут равны />, потребности первого потребителя удовлетворены.
8. />. После восьмого шага запасы и потребностибудут удовлетворены.
Потребности всех потребителейудовлетворены, запасы поставщиков исчерпаны. После седьмого шага мы получилиисходный опорный план /> (Табл.3.3).
 
Х0 Таблица3.3.
34
30
39
29
18
34(5)
48(4)
82
40
35
45
41
10
 
14(7)
22(8)
36
36
38
41
50
8
 
29(6)
50(1)
79
14
10
13
10
12
 
60(2)
20(3)
80
 
 
77
60
22
68
50
Также как и в предыдущем случае,номер шага помещен в скобках над объемами перевозок. Суммарные транспортныерасходы, соответствующие данному плану перевозок равны
/>
По сравнениюс расчетом по методу северо-западного угла суммарные транспортные расходы уменьшилисьс 8452 у.е. до 6342 у.е.
Для проверкиплана на оптимальность составим систему уравнений, следуя условию — длябазисных переменных сумма потенциалов равна тарифу. Значение одного изпотенциалов зададим произвольно (пусть />), последовательность вычисленияостальных потенциалов указана ниже: 1), 2),…, 8).
/>
Потенциалыпоставщиков /> поместимслева от таблицы, а потенциалы потребителей /> – сверху над таблицей (табл.3.4).
 
Таблица 3.4 34 29 39 29 6 34 30 39 29 18
34(5)
 
48(4)
 
82 -1 -12
 
  6 40 35 45 41 10
 
14(7)
 
22(8)
 
 
36 -6 -2
  2 36 38 41 50 8
 
29(6)
 
 
50(1)
79 -7 -19
  -19 14 10 13 10 12
 
 
60(2)
 20(3)
80 1 7 -25
 
77
 
 
60
 
 
22
 
 
68
 
 
50 /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Длянебазисных переменных вычислим оценки по формуле:
/>
/>
/>
/>
/>
/>
/>
/> />
/>
/>
/>
Значенияоценок поместим в левом нижнем углу незанятых клеток табл. 3.4. Фиксируемнаибольшую положительную оценку. В данном случае: />. Разрешающей объявим коммуникацию (4,3). Строим циклпересчета, который показан в табл. 3.4 пунктирной линией.
Величинакорректировки ρ=(58,79)=58. Вносим изменение в план:перевозки отрицательного полуцикла уменьшаем на />, а перевозки положительногополуцикла увеличиваем на эту же величину, остальные перевозки оставим безизменения. Переменная х11 вводится в базис со значением=58, переменная х14 выводится из базиса. Получим план /> (табл. 3.5).

План />Таблица 3.5 34 29 39 29 6 34 30 39 29 18
34(5)
 
48(4)
 
82 -1 -12
 
  6 40 35 45 41 10
 
14(7)
  22
 
 
36 -6 -2
  2 36 38 41 50 8
 
29(6)
 
 
50(1)
79 -7 -19
  -19 14 10 13 10 12
 
 
60(2)
 20(3)
80 1 7 -25
 
77
 
 
60
 
 
22
 
 
68
 
 
50 /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Значение функцииуменьшилось на (38*16-9*38=290) и стало: />
План не оптимален. Занововычисляем потенциалы и оценки (табл. 3.6). Наибольшая положительная оценка– это/>, план не оптимален. Строим цикл пересчета и определяемвеличину корректировки плана ρ=(48,58)=48.
 
Таблица 3.6
План X2 34 29 39 29 6 34 30 39 29 18
  14
 
68(4)
 
82 -1 -12
 
  6 40 35 45 41 10
 
 
 
  36
36 -6 -2
  2 36 38 41 50 8
  65
 
  14
79 -7 -19
  -19 14 10 13 10 12
  12
46(2) 22
 
80 1 7 -25
 
77
 
 
60
 
 
22
 
 
68
 
 
50 /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Значение функции исоответственно транспортные расходы составили />
Положительныхоценок нет, план Х2 оптимален.
 
3. Метод Фогеля
В табл. 3.4 показаныпоследовательность определения базисных переменных, наборы разностей /> в строкахсправа от таблицы, а /> в столбцах снизу под таблицей.
План Х0
Таблица 3.4 1 2 3 4 5 6 7 8
34
30
39
29
18 11 11 11 11 11 11 - -
34(6)
48(5)
 
 
 
82
 
40
35
45
41
10
  25 25 25 25 25 25 25 25
14(7)
 
22(8)
 
 
36
 
36
38
41
50
8
  28 2 - - - - - -
29(2)
 
 
 
50(1)
79
 
14
10
13
10
12
  2 2 2 2 - - - -
12(4)
 
68(3)
 
80
77
60
22
68
50 Этап 1 20 20 26 19 2 Этап 2 20 20 26 19 - Этап 3 20 20 26 19 - Этап 4 20 20 26 12 - Этап 5 20 - 26 - - Этап 6 20 - 26 - - Этап 7 16 - 26 - - Этап 8 - - 26 - -
Суммарные транспортные расходы,соответствующие данному плану перевозок равны
/>.
Сравнимрасчеты, проделанные тремя методами. Транспортные расходы, рассчитанные:
1) методомсеверо-западного угла составили 8452 у.е.,
2) методомминимального элемента соответственно 6342 у.е.,
3)пересчитанные по методу потенциалов – 6118 у.е.,
4) методомФогеля соответственно – 6390 у.е.
Наименьшиетранспортные расходы составили расходы, рассчитанные по методу потенциалов.
 
Задача № 4
 
Сетевая задача
Ниже приведено 10вариантов транспортной задачи в сетевой постановке. Каждая задача изображена ввиде неориентированного связного графа. На ребрах проставлены значения тарифов />, на вершинах (в кружках) — значениязапасов-потребностей />. Построить пробный допустимыйплан, проверить его на оптимальность. В случае необходимости довести дооптимального плана методом потенциалов.

/>

Решение. Построим пробный опорный план(рис.1)./> /> /> /> /> /> /> /> /> /> /> /> /> /> />

Рис. 1. Пробный планперевозок по сети.
В качестве начальной выберем вершину 12, котораяявляется поставщиком с запасами в 20 единиц продукции. Из этой вершины отправимтранзитом через 13 с запасами 45 ед. и 10 вершину с запасами 30 единиц в 8вершину и удовлетворяем её потребности в 40 единиц. Оставшиеся 55 единиц отправимв 6 вершину с потребностями 40 единиц, оставшиеся 15 единиц отправляем в 5 вершинус потребностями 10 единиц, оставшиеся 5 единиц направим в 1 вершину,потребности которой составляют 35 единиц.
Из 11вершины с запасами 45 единиц направим транзитом через 9 вершину, всего запасовстало 75 единиц, направим их транзитом через 7 вершину в 4 вершину, потребностикоторой составляют 40 единиц, оставшиеся 35 единиц направим во 2 вершину иудовлетворим ее потребности.
Из 3вершины с запасами 30 единиц направим транзитом через 7 вершину в 1 вершину,потребности которой удовлетворим.
В результате проведенных операций все запасы вывезены,потребности всех потребителей удовлетворены.
В результате проведенныхопераций все запасы вывезены, потребности всех потребителей удовлетворены.Число базисных ребер здесь равно 11, число вершин 13.
Итак, полученный планявляется опорным, так как удовлетворяет всем требованиям опорного плана.Значение функции, которое соответствует построенному плану равно
/>.
Проверку плана наоптимальность осуществим с помощью метода потенциалов.
Одной из вершин (например, 1) зададим произвольное значениепотенциала α1=0. Запишем его около вершины 1.
Затем, двигаясь побазисным ребрам, вычисляем потенциалы остальных вершин.
/> ; /> 
/>;/>;
/>;/>;
/>;/>
/>;  />;
/>/>
Послевычисления потенциалов находим оценки для небазисных ребер: (1,2), (2,4),(2,7),(3,7),(7,12), (7,8), (10,12),(4,6). Они определяются по формуле и равнысоответственно:
/>;/>;
/>;/>;.
/>/>
/>/>
Есть три положительные оценки, значит построенныйопорный план не оптимальный.
Наибольшая оценка />. Ребро (7,8), объявляем разрешающим, направляемразрешающую стрелку (пока пустую) от вершины с меньшим потенциалом к вершине сбольшим потенциалом, т.е. от 7–й вершины к 8–й (на рис. 2 разрешающая стрелканамечена пунктиром). В результате получаем цикл пересчета, замыкающийся наребре (7,8). Цикл пересчета на рис.2 намечен сплошной линией.

/>

Рис.3. пересчет перевозокпо потенциалам
Во второй строке выписываем ребра, принадлежащие циклупересчета. В первой строке, над ребрами с помощью стрелок укажем направлениеперевозок, а в третьей строке – объем перевозимого груза. В четвертой строкеполученной конструкции запишем />, если направление перевозкисовпадает с разрешающей стрелкой и />, в противном случае.
/>
Изменяем распределение поставок. Определяем /> величинукорректировки плана. Поскольку перевозки х8,10, х11,9 направленыпротив разрешающей стрелки, величина /> полагается меньшей из них />
Включаем в базис ребро (7,8), а объем перевозки полагаемравным величине корректировки /> Ребро (7,9) исключаем из базиса.
После пересчета получим значение функции:
/>
 
Задача № 5
 
Задача о назначениях
Ниже приведены таблицы, вклетках которых проставлены элементы матрицы эффективностей /> задачи о разборчивойневесте. Решить задачу методом потенциалов и венгерским методом. 44 31 13 11 41 10 17 38 25 35 20 26 8 17 14 38 36 12 37 38 49 38 22 10 13 28 21 48 43 44 29 26 12 37 22 39 46 26 20 44 49 22 49 19 2 20 30 45 16 45 27 5 21 30 21 34 23 43 33 20 29 3 46 33 21
 
Решение.
1. Метод потенциалов.
Начальный вариант выбора /> найдем методоммаксимального элемента (Табл. 5.1).
Шаг 1. Максимальным элементом является с3,4=49. Назначим третьейневесте четвертого жениха. Вычеркнем третью строку.
Шаг 2. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с5,8=49.Назначим пятой невесте восьмогожениха. Вычеркнем пятую строку.
 Шаг 3. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с6,2=49.Шестая невеста выбирает второго жениха, вычеркиваем шестую строку.
Шаг 4. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с4,3=48. Четвертая невеста выбирает третьего жениха, вычеркиваемчетвертую строку.
Шаг 5. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с8,6=46.Восьмая невеста выбирает шестого жениха, вычеркиваем восьмую строку.
Шаг 6. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с7,1=45.Седьмая невеста выбирает первого жениха, вычеркиваем седьмую строку.
Шаг 7. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с1,4=41.Но четвертого жениха уже выбрала третья невеста, поэтому в клетку (1,4)поместим 0. Вдальнейшем, х1,4=0 будем считать базисной переменной. Вычеркнемчетвертый столбец.
Шаг 8. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с1,7=38.Первая невеста назначается седьмому жениху, вычеркиваем первую строку.
Шаг 9. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с2,7=38.Но седьмой жених уже выбран, поэтому в клетку (2,7) поместим 0. Х2,7=0 — базиснаяпеременная. Вычеркнем седьмой столбец.
 Шаг 10. Из невычеркнутых элементовматрицы максимальнымэлементом является с2,8=36.На восьмой жених уже выбран, поэтому в клетку (2,8) поместим 0. Х2,8=0 — базиснаяпеременная. Вычеркнем восьмой столбец.
Шаг 11. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с2,1=35.Но первый жених уже занят, поэтому в клетку (2,1) поместим 0. Х2,1=0 — базиснаяпеременная. Вычеркнем первый столбец.
 Шаг 12. Из невычеркнутых элементовматрицы максимальнымэлементом является Х2,3=26.Но третий жених уже занят, поэтому в клетку (2,3) поместим 0. Х2,3=0 — базиснаяпеременная. Вычеркнем третий столбец.
Шаг 13. Из невычеркнутыхэлементов матрицы максимальнымэлементом является Х1,5=23.Но пятый жених уже занят, поэтому в клетку (1,5) поместим 0. Х1,5=0 — базиснаяпеременная. Вычеркнем пятый столбец.
Шаг 14. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с2,2=20.Но второй жених уже занят, поэтому в клетку (2,2) поместим 0. Х2,2=0 — базиснаяпеременная. Вычеркнем второй столбец.
Шаг 15. Из невычеркнутыхэлементов матрицы максимальнымэлементом является с2,5=17.Вторая невеста назначается пятому жениху, вычеркиваем вторую строку.
В табл. 5.1 номер шага,на котором были получены базисные переменные, указан в скобках. После 15 шагаполучим пробный вариант назначения Х0: х1,7=х2,5= х3,4=х4,3=х5,8=х6,2=х7,1=х8,6=1. Это означает, что первая невеста выходитзамуж за седьмого жениха, вторая невеста за пятого жениха, третья невеста за четвертогожениха, четвертая невеста за третьего жениха, пятая невеста за восьмого жениха,шестая невеста за второго жениха, седьмая невеста за первого жениха, восьмая невестаза шестого жениха.
Таблица 5.1.
 
 
 
 
 
 
 
  31 13 11 41 10 17 38 25
(7)
0(13)
1(8)
 
 
 
  35 20 26 8 17 14 38 36
0(11)
0(14)
0(12)
1(15)
(7)
(10) 12 37 38 49 38 22 10 13
 
1(1)
  28 21 48 43 44 29 26 12
1(4)
  37 22 39 46 26 20 44 49
 
 
1(2) 22 49 19 2 20 30 45 16
1(3)
 
  45 27 5 21 30 21 34 23
1(6)
  43 33 20 29 3 46 33 21
 
 
 
1(5)
 
Суммарная эффективность,отвечающая полученному варианту выбора равна:
/>условныхединиц эффективности
Вариантвыбора /> проверимна оптимальность. Для этого вычислим потенциалы и оценки.
/>
Отсюдавычислим потенциалы:
/>
Длянебазисных переменных вычислим оценки по соответствующей формуле:
/>
/>
/>
/>
/>
/>
/>
/>
/>/>
И так далеерасчеты по соответствующим формулам и данным приведены в таблице 5.2.
 
Таблица 5.2
Х0
28
13
19
41
10
44
38
29 31 13 11 41 10 17 38 25
(7)
0(13)
1(8)
 
Оценка1
-3
8
 
 
27
 
4
  35 20 26 8 17 14 38 36
7
0(11)
0(14)
0(12)
1(15)
(7)
(10)
Оценка2 40 37
8 12 37 38 49 38 22 10 13
 
 
1(1)
 
Оценка3 24 -16 -11 -20 30 36 24 29 28 21 48 43 44 29 26 12
1(4)
 
Оценка4 29 21 27 -5 44 41 46 37 22 39 46 26 20 44 49
20
 
 
1(2)
Оценка5 11 11 15 4 44 14 22 49 19 2 20 30 45 16 36
1(3)
 
 
Оценка6 42 36 75 26 50 29 49 45 27 5 21 30 21 34 23 17
1(6)
 
Оценка7
3 31 37 -3 40 21 23 43 33 20 29 3 46 33 21 2
 
 
 
1(5)
 
Оценка8 -6 -11 8 -19 16 7 17
 
Cреди вычисленных оценок имеютсяотрицательные, это означает, что выбранный вариант назначения не являетсяоптимальным. Наименьшая из отрицательных оценок /> Строим цикл пересчета: (3,5), (2,5), (1,7), (1,4), (3,5)замыкающийся на разрешающей клетке. Вычислим величину корректировки />. Базисныйнуль 03,5 перемещается в клетку (1,7), переменная х1,7включается в базис, а переменная х3,5 выходит из базиса. Получимновую комбинацию расстановки единиц и нулей (Табл. 5.3). Суммарнаяэффективность равна:
/>условныхединиц эффективности
 
Таблица 5.3
Х0
28
13
19
41
10
44
38
29 31 13 11 41 10 17 38 25
1(7)
0(13)
(8)
 
Оценка1
-3
8
 
 
27
 
4
  35 20 26 8 17 14 38 36
7
0(11)
0(14)
0(12)
(15)
1(7)
(10)
Оценка2 40 37
28 12 37 38 49 38 22 10 13
 
 
 
1(7)
 
Оценка3 44 4 9 20 50 56 44 29 28 21 48 43 44 29 26 12
1(4)
 
Оценка4 29 21 27 -5 44 41 46 37 22 39 46 26 20 44 49
20
 
 
1(2)
Оценка5 11 11 15 4 44 14 22 49 19 2 20 30 45 16 36
1(3)
 
 
Оценка6 42 36 75 26 50 29 49 45 27 5 21 30 21 34 23 17
1(6)
 
Оценка7
3 31 37 -3 40 21 23 43 33 20 29 3 46 33 21 2
 
 
 
1(5)
 
Оценка8 -6 -11 8 -19 16 7 17
 
Заново вычисляемпотенциалы и оценки.

/>
Отсюдавычислим потенциалы:
/>
Длянебазисных переменных вычислим оценки в таблице 5.3.
Среди вычисленных оценокимеются отрицательные, это означает, что выбранный вариант назначения неявляется оптимальным. Наименьшая из отрицательных оценок /> Строим цикл пересчета: (8,4), (2,4), (2,2), (8,2),(8,4)замыкающийся на разрешающей клетке. Вычислим величину корректировки />. Базиснаяпеременная х2,2=0 перемещается в клетку (8,4), переменная х8,4включается в базис, а переменная х2,2 выходит из базиса. (Табл. 5.4).
Таблица 5.4
Х1
28
13
19
41
10
44
38
29 31 13 11 41 10 17 38 25
1(7)
0(13)
(8)
 
Оценка1
-3
8
 
 
27
 
4
  35 20 26 8 17 14 38 36
7
0(11)
0(12)
(15)
1(7)
(10)
Оценка2 40 37
28 12 37 38 49 38 22 10 13
 
 
 
1(7)
 
Оценка3 44 4 9 20 50 56 44 29 28 21 48 43 44 29 26 12
1(4)
 
Оценка4 29 21 27 -5 44 41 46 37 22 39 46 26 20 44 49
20
 
 
1(2)
Оценка5 11 11 15 4 44 14 22 49 19 2 20 30 45 16 36
1(3)
 
 
Оценка6 42 36 75 26 50 29 49 45 27 5 21 30 21 34 23 17
1(6)
 
Оценка7
3 31 37 -3 40 21 23 43 33 20 29 3 46 33 21 2
 
 
0(14)
 
1(5)
 
Оценка8 -6 -11 8 -19 16 7 17
 
Суммарная эффективность неизменилась и равна:
/>условныхединиц эффективности
Заново вычисляемпотенциалы и оценки. Расчеты оценок приведены в таблице 5.5.
Среди вычисленных оценокимеются отрицательные, это означает, что выбранный вариант назначения неявляется оптимальным. Наименьшая из отрицательных оценок /> Строим цикл пересчета: (2,4), (2,5), (5,5), (5,2),(2,2)замыкающийся на разрешающей клетке. Вычислим величину корректировки />. Базиснаяпеременная х5,2=0 перемещается в клетку (2,4), переменная х2,4включается в базис, а переменная х5,2 выходит из базиса. (Табл.5.5).
 
Таблица 5.5
Х2
28
13
19
41
10
44
38
29 31 13 11 41 10 17 38 25
1(7)
0(13)
(8)
 
Оценка1
-3
8
 
 
27
 
4
  35 20 26 8 17 14 38 36
7
0(11)
0(12)
(15)
1(7)
(10)
Оценка2 40 37
28 12 37 38 49 38 22 10 13
 
 
 
1(7)
 
Оценка3 44 4 9 20 50 56 44 29 28 21 48 43 44 29 26 12
1(4)
 
Оценка4 29 21 27 -5 44 41 46 37 22 39 46 26 20 44 49
20
 
 
1(2)
Оценка5 11 11 15 4 44 14 22 49 19 2 20 30 45 16 36
1(3)
 
 
Оценка6 42 36 75 26 50 29 49 45 27 5 21 30 21 34 23 17
1(6)
 
Оценка7
3 31 37 -3 40 21 23 43 33 20 29 3 46 33 21 21
 
 
0(14)
 
1(5)
 
Оценка8 6 11 20 29 26 29
Заново вычисляемпотенциалы и оценки. Расчеты оценок приведены в таблице 5.5.
Отрицательных оценок нет.Назначение Х2 оптимально, обозначим его через Х2*.
Суммарная эффективность,отвечающая полученному варианту назначения равна:
/>условныхединиц эффективности
Назначение Х2оптимально. Итак, оптимальный вариант назначения имеет вид:
х1,4=1 (перваяневеста выберет четвертого жениха),
х2,7=1 (втораяневеста выберет седьмого жениха),
 х3,5=1 (третьяневеста выбрала пятого жениха),
х4,3=1 (четвертаяневеста выбрала третьего жениха),
х5,8=1 (пятаяневеста выберет восьмого жениха),
х6,2=1 (шестаяневеста выберет второго жениха),
х7,1=1 (седьмаяневеста выберет первого жениха),
х8,6=1 (восьмаяневеста выберет шестого жениха).
При этом вариантеназначений получим максимальную эффективность /> единицэффективности.  
2. Венгерскийметод.
Предварительный этап. Исходнаяматрица C:
 31 13 11 41 10 17 38 25 35 20 26 8 17 14 38 36 12 37 38 49 38 22 10 13 28 21 48 43 44 29 26 12 37 22 39 46 26 20 44 49 22 49 19 2 20 30 45 16 45 27 5 21 30 21 34 23 43 33 20 29 3 46 33 21
Шаг 1. Обозначим через /> наибольшийэлемент столбца /> матрицы /> (r1=45, r2=49,r3=48, r4=49, r5=44, r6=46, r7=45,r8=49). Каждый элемент />-го столбца вычтем из />, результатывычислений будем помещать на место вычитаемого. Аналогичные преобразованияпроводим в остальных столбцах. Получим неотрицательную матрицу />, в каждом столбцекоторой есть хотя бы один нуль.
 
C1 =
14
36
37
8
34
29
7
24
10
29
22
41
27
32
7
13
33
12
10
6
24
35
36
17
28
6
17
19
37
8
27
9
3
18
26
1
23
29
47
24
16
30
22
43
28
14
25
11
23
2
16
28
20
41
12
25
Шаг 2. Преобразуемматрицу />.Для этого обозначим через /> минимальный элемент строки />, которыйпоследовательно вычтем из элементов той же строки, результаты поместим на местоуменьшаемого. Наименьшийэлемент первой строки матрицы /> равен 7. Проведем вычисления для элементовпервой строки: (d11=7, d12=29, d13=30, d14=1, d15=27, d16=22, d17=0, d18=17). Такие же вычисления проведем для остальных строк,получим неотрицательную матрицу />, в каждом столбце и каждой строкекоторой есть хотя бы один нуль.D=
7
29
30
1
27
22
*
17
3
22
15
34
20
25
6
33
12
10
*
6
24
35
36
17
28
*
6
17
19
37
8
27
9
3
18
26
1
*
23
*
29
47
24
16
30
*
22
43
28
14
25
11
23
2
16
28
20
41
*
12
25
Основной этап. После второго шага предварительногоэтапа получим неотрицательную матрицу />, эквивалентную матрицеэффективностей />:
П.1. В первом столбцематрицы /> отметимзвездочкой 0*7,1, во втором столбце – 06,2, втретьем столбце – 04,3, в четвертом столбце – 0*3,4, в шестом столбце – 08,6, в седьмом столбце – 01,7, ввосьмом столбце – 05,8. Нули в пятом столбце – 04,5 нельзяотметить звездочкой, так как они лежат в строке, в которой уже есть нуль созвездочкой – 04,3,. Число звездочек равно семи, что меньшеразмерности матрицы (8), переходим к п.2.D= + + + + + + +
7
29
30
1
27
22
*
17
3
22
15
34
20
25
’
6
33
12
10
*
6
24
35
36
17
28
*
6
’
17
19
37 +
8
27
9
3
18
26
1
*
23
*
29
47
24
16
’
30
*
22
43
28
14
25
11
23
2
16
28
20
41
*
12
25
/> ε=2
П.2. Помечаем знаком «+» сверху столбцы:1, 2, 3, 4,6, 7,8 и считаем эти столбцы занятыми. Незанятый нуль находится в четвертой строке пятого столбца 04,5, во второй строке и шестой строках седьмогостолбца. Помечаем их штрихом 0'4,5, 0'2,7, 0'6,7. Переходим к пункту 3.
П.3. Столбец 3 считаемнезанятым и знак «+» сверху снимаем (обводим в рамку), а четвертую строкуобъявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацуп.2.
П.2. Незанятых нулей нет,переходим к п.5.
П.5. Среди незанятыхэлементов находим минимальный, который обозначим через />, ε=d3,5=6. Преобразуем матрицу />: незанятые элементы уменьшим на 6;дважды занятые увеличим на 6; остальные элементы оставим без изменения. Получимматрицу />,в которой имеется один незанятый нуль, переходим к четвертому абзацу п.2. + + + + + + +
D1=
7
29
24
1
21
22
*
17
3
22
9
34
14
25
’
6 +
33
12
4
*
’
24
35
36
23
34
*
12
’
23
25
43 +
8
27
3
3
12
26
1
*
23
*
23
47
18
16
’
30
*
22
37
28
8
25
11
23
2
16
22
20
35
*
12
25
/> 
П.2. Незанятый нульнаходится в третьей строке пятого столбца 03,5. Помечаем штрихом 0'3,5. Во второй строке седьмого столбца находится нуль со штрихом.Помечаем штрихом 0'2,7и считаем седьмой столбецнезанятым, знак «+» сверху снимаем, а вторую строку объявляем занятой и помечаемзнаком «+» справа. + + + + + + +
D2=
7
29
24
1
21
22
*
17
3
22
9
34
14
25
’
6 +
33
12
4
*
’
24
35
36
23
34
*
12
’
23
25
43 +
8
27
3
3
12
26
1
*
23
*
23
47
18
16
’
30
*
22
37
28
8
25
11
23
2
16
22
20
35
*
12
25
 
П.5. Переходим к пункту2. Помечаем звездочкой 0*6,5, штрихом 0'8,3, 0'2,7. В третьей нет />, следовательно,переходим к пункту 4, ε=d6,4=7 после преобразований, получим матрицу D3 + + + + + + +
D3=
7
29
24
1
21
22
*
17
3
22
9
34
14
25
’
6 +
33
12
4
*
’
24
35
36
23
34
*
12
’
23
25
43 +
8
27
3
3
12
26
1
*
23
*
23
47
18
16
’
30
*
22
37
28
8
25
11
23
2
16
22
20
35
*
12
25
/> 
П.4. Строим цепочку изнулей. Начиная от только что отмеченного штрихом нуля (0’2,7),идем по строке до />5,2 цепочка состоит издвух элементов Ц: 07,2, 0’5,2. В матрице такиецепочки обозначают так />. После преобразования получимновый набор нулей со звездочкой (/>), который содержит на однузвездочку больше, чем предыдущий набор.
Проводим следующиепересчеты.  +
/>+ + + + +
D3= 25
0* 27 19 16 20 32 + 3 43 2 7 23 14 5
0* + 6 32 23 20 5 18 7 +
0* 36 10
/>0 5 2 17
/>0
/>0' 9 19 5 45 19 12 + 15 24 10 7
/>0’
0* 5 5 22
0* 13 8 9 15 22 9 6 32 20 7 34
0* 8 +
Процесс окончен, так какчисло нулей со звездочкой равно размерности матрицы эффективности.
/>
Оптимальный вариантвыбора (1,2)(2,7)(3,8)(4,1)(5,4),(6,6),(7,5),(8,3). Это значит, что первая невеста выберет второгожениха, вторая невеста седьмого жениха, третья –восьмого, четвертая первого,пятая четвертого, шестая – шестого, седьмая невеста пятого жениха, а восьмаяневеста выберет третьего жениха.
При этом максимальнаясуммарная эффективность (суммарная продолжительность жизни всех семей) равна: /> (единиц эффективности)