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

РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

“ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”

ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ

СПЕЦИАЛЬНОСТЬ “Менеджмент организаций “

К О Н Т Р О Л Ь Н А Я Р А Б О Т А

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

Выполнил:

Студент 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 она проходит через начало координат) Так как задача на минимум, то перемещаем линию уровня в направлении вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L 3 и L 4 , т. е. через точку . Для определения координат точки P решаем систему уравнений

.

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

10

6

4

P

2

(4)
(3)
(2)

График № 1

1б) Перейдем к расширенной задаче:

Данная расширенная задача имеет начальное опорное решение с базисом . Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:

Расчеты проведем в таблице (Табл. 1)

Таблица 1

1-30000M
БСбВА 1А 2А 3А 4А 5А 6А 7
А 309-2310000
А 40535201000
А 50174-700100
А 7М376800011
0-1300000
376800000

Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора А k, вводимого в базис опорного решения, и вектора А l, выводимого из базиса. Наибольшая положительная оценка соответствует А2 , за разрешающий элемент выбираем коэффициент 8 и выполняем преобразование Жордана.

Вектор А2 выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем второе опорное решение с базисом (табл. 1.3). Целевая функция =-3М -21. Это решение не является оптимальным, так как есть положительная оценка.

Таблица 1

БСбBА 1А 2А 3А 4А 5А 6
А2-33,0-0,71,00,30,00,00,00,0
А 4047,06,30,0-0,71,00,00,00,0
А 5038,0-0,70,02,30,01,00,00,0
A7М13,011,30,0-2,70,00,01,01,0
M+1-9,01,00,0-1,00,00,00,00,0
M+213,011,30,0-2,70,00,00,00,0
A2-3-2,4-0,61,00,00,0-0,10,00,0
A4057,96,10,00,01,00,30,00,0
А 3016,3-0,30,01,00,00,40,00,0
A7М56,410,60,00,00,01,11,01,0
M+17,30,70,00,00,00,40,00,0
M+256,410,60,00,00,01,10,00,0
A2-30,60,01,00,00,0-0,10,10,1
A4025,10,00,00,01,0-0,4-0,6-0,6
А 5017,80,00,01,00,00,50,00,0
A115,31,00,00,00,00,10,10,1
3,50,00,00,00,00,4-0,1-0,1
0,00,00,00,00,00,0-1,0-1,0

Целевая функция после второй итерации равна = 3,5. Все оценки отрицательные, план оптимален.

Оптимальный план исходной задачи Х*= (х1* =5,3; х2* =0,6). Минимальное значение целевой функции исходной задачи =3,5.

Ответ: minZ (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-568-2Min
117112516
141003817
13294615

Решение задачи 2

Представим исходные данные задачи в виде:

Проверяем, применим ли графический метод при решении данной задачи.

Линейно независимы, так как их координаты непропорциональны. Поэтому ранг системы векторов-условий r = 3. Находим n – r =5 – 3 = 2 £ 2. Следовательно, метод применим.

1. Приведем систему уравнений-ограничений к равносильной, разрешенной методом Жордана-Гаусса. Преобразуем систему уравнений методом Жордана-Гаусса до получения общего решения (табл. 2.1).

Таблица 2.1.

№ итерац.X1X2X3X4X5Bi

(1)

117112516
141003817
13294615

(2)

-45,00-33,001,000,00-27,00-52,00
4,673,330,001,002,675,67
-5,67-11,339,000,00-4,67-7,67

(3)

2,250,751,0010,130,005,38
1,751,250,000,381,002,13
2,50-5,509,001,750,002,25
(4)-12,2132,57-51,070,000,00-7,64
1,212,43-1,930,001,001,64
1,43-3,145,141,000,001,29
(5)0,24-0,641,000,000,000,15
1,681,200,000,001,001,93
0,200,140,001,000,000,52

Общее решение системы уравнений имеет вид

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

Откуда получим систему неравенств с двумя переменными

Целевую функцию выразим через свободные переменные

Окончательно получим стандартную задачу линейного программирования с двумя переменными

Строим область допустимых решений (график 2). Любая точка многоугольника удовлетворяет системе неравенств. Вершина является точкой входа семейства прямых в область решений, следовательно, в этой точке она принимает минимальное значение.

В свою очередь, =(1,32;0,12).

Решая систему уравнений получаем х1 =2,2, х2 =0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Z min

.

6

4

A

А

2
(2)

(3)

График 2

2. Решим симплекс-методом задачу линейного программирования, используя метод искусственного базиса

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

Данная расширенная задача имеет начальное опорное решение с базисом . Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:

Записываем исходные и расчетные данные в симплексную таблицу (табл.2.2).

Таблица 2.2

1-568-2МMM
БСбА 0А 1А 2А 3А 4А 5А 6A7A8
А 6М161171125100
A7M171410038010
А 8М15132946001
0-15-6-82000
482819101919000

Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора А k, вводимого в базис опорного решения, и вектора А l, выводимого из базиса. В столбце “А 3 ” (см. табл. 2.1) за разрешающий элемент выбираем коэффициент 9 в третьей строке и выполняем преобразование Жордана.

Вектор А3 выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем первое опорное решение с базисом (табл. 2.3). Целевая функция =31,33М -10. Это решение не является оптимальным, так как имеются положительные оценки.

Таблица 2.3

1-568-2МMM
БСбА 0А 1А 2А 3А 4А 5А 6A7A8
А 6М14,339,566,780,0011,564,331,000,00-0,11
A7M17,0014,0010,000,003,008,000,001,000,00
А 361,671,440,221,000,440,670,000,000,11
10,00-7,67-6,330,005,33-6,000,000,00-0,67
31,3313,5616,780,0014,5612,330,000,00-1,11

Вводим вектор А 4 в базис, получаем второе опорное решение (таблица 2.4) с базисом . Целевая функция = 3,38+13,28M. Далее в таблице 2.4 приведены расчеты с третьей по пятую итерации.

Таблица 2.4

42-151МMM
БСбА0А1А2А3А4А5А6A7A8
A481,240,830,590,001,000,380,090,00-0,01
A7M13,2811,528,240,000,006,88-0,261,000,03
A361,121,08-0,041,000,000,50-0,040,000,12

3,38-12,08-9,460,000,00-8,00-0,460,00-0,62
13,281,528,240,000,006,88-1,260,00-0,97
A480,520,200,140,001,000,000,10-0,05-0,01
A5-21,931,681,200,000,001,00-0,040,150,00
A360,150,24-0,641,000,000,00-0,02-0,070,11
18,841,330,130,000,000,00-0,761,16-0,58
0,00-10,000,000,000,000,00-1,00-1,00-1,00
A112,601,000,690,005,040,000,51-0,27-0,06
A5-2-2,420,000,040,00-8,441,00-0,890,610,10
A36-0,470,00-0,801,00-1,200,00-0,14-0,010,13
4,190,00-0,790,00-6,680,00-1,441,53-0,51
25,990,006,900,0050,350,004,07-3,75-1,56

Целевая функция после пятой итерации равна = 4,19. Положительных оценок нет, план оптимален. Ответ: minZ (X * ) =4,2.

3.Построим двойственную задачу

Используя вторую симметричную пару двойственных задач, составим задачу, двойственную к исходной:

Вводим неотрицательные дополнительные переменные у 4 , у 5 , у 6 у 7 , у 8 для приведения задачи к каноническому виду:

Находим начальное опорное решение Y 1 = (0,0,0,1,-5,6,8,-2) с базисом Б1 = (А 4 , А 5 , А 6 , А 7 , А 8 ). Решение задачи симплексным методом приведено в табл. 2.5. (расчеты табл.2.2. и табл.2.4.)

Таблица 2.5

1-568-2МMM
БСбА 0А 1А 2А 3А 4А 5А 6A7A8
А 6М161171125100
A7M171410038010
А 8М15132946001
0-15-6-82000
482819101919000
A112,601,000,690,005,040,000,51-0,27-0,06
A5-2-2,420,000,040,00-8,441,00-0,890,610,10
A36-0,470,00-0,801,00-1,200,00-0,14-0,010,13
4,190,00-0,790,00-6,680,00-1,441,53-0,51
25,990,006,900,0050,350,004,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
343039291882
403545411036
36384150879
141013101280
7760226850

Решение.

1.Метод северо-западного угла.

Исходные данные задачи сведем в таблицу (табл. 3.1).

Таблица 3.1.

ПоставщикиПотребителиЗапасы
343039291882
403545411036
36384150879
14101310128 0
Потребности7760226 850

Решение. Построим опорный план задачи методом северо-западного угла.

Объем перевозки и последовательность заполнения матрицы будем записывать в соответствующие клетки табл. 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.

343 03 92918
77(1)5(2)82
4 0354 54110
36(3)36
363 841508
19(4)22(5)38(6)79
1 41 01 31 01 2
30(7)50(8)8 0
7 760226 850

Суммарные транспортные издержки на перевозку продукции от поставщиков к потребителю составляют

2.Метод минимального элемента.

Исходные данные

ПоставщикиПотребителиЗапасы
В1В2В3В4В5
А1343039291882
А2403545411036
А336384150879
А414101310128 0
Потребности7760226 850

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.

3430392918
34(5)48(4)82
4035454110
14(7)22(8)36
363841508
29(6)50(1)79
1410131012
60(2)20(3)80
7760226850

Также как и в предыдущем случае, номер шага помещен в скобках над объемами перевозок. Суммарные транспортные расходы, соответствующие данному плану перевозок равны

По сравнению с расчетом по методу северо-западного угла суммарные транспортные расходы уменьшились с 8452 у. е. до 6342 у. е.

Для проверки плана на оптимальность составим систему уравнений, следуя условию – для базисных переменных сумма потенциалов равна тарифу. Значение одного из потенциалов зададим произвольно (пусть ), последовательность вычисления остальных потенциалов указана ниже: 1), 2),…, 8).

Потенциалы поставщиков поместим слева от таблицы, а потенциалы потребителей – сверху над таблицей (табл.3.4).

Таблица 3.4

342939296
03430392918
34(5)48(4)82
-10-12
64035454110
14(7)22(8)36
0-6-2
2363841508
29(6)50(1)79
-70-19
-191410131012
60(2)20(3)80
17-25
7760226850

Для небазисных переменных вычислим оценки по формуле:

Значения оценок поместим в левом нижнем углу незанятых клеток табл. 3.4. Фиксируем наибольшую положительную оценку. В данном случае: . Разрешающей объявим коммуникацию (4,3). Строим цикл пересчета, который показан в табл. 3.4 пунктирной линией.

Величина корректировки ρ=(58,79)=58. Вносим изменение в план: перевозки отрицательного полуцикла уменьшаем на , а перевозки положительного полуцикла увеличиваем на эту же величину, остальные перевозки оставим без изменения. Переменная х11 вводится в базис со значением =58,переменная х14 выводится из базиса. Получим план (табл. 3.5).

План Таблица 3.5

342939296
03430392918
34(5)48(4)82
-10-12
64035454110
14(7)2236
0-6-2
2363841508
29(6)50(1)79
-70-19
-191410131012
60(2)20(3)80
17-25
7760226850

Значение функции уменьшилось на (38*16-9*38=290) и стало:

План не оптимален. Заново вычисляем потенциалы и оценки (табл. 3.6). Наибольшая положительная оценка – это , план не оптимален. Строим цикл пересчета и определяем величину корректировки плана ρ=(48,58)=48.

Таблица 3.6

План X2

342939296
03430392918
1468(4)82
-10-12
64035454110
3636
0-6-2
2363841508
651479
-70-19
-191410131012
1246(2)2280
17-25
7760226850

Значение функции и соответственно транспортные расходы составили

Положительных оценок нет, план Х2 оптимален.

3. Метод Фогеля

В табл. 3.4 показаны последовательность определения базисных переменных, наборы разностей в строках справа от таблицы, а в столбцах снизу под таблицей.

План Х0

Таблица 3.4

12345678
3430392918111111111111
34(6)48(5)82
40354541102525252525252525
14(7)22(8)36
363841508282
29(2)50(1)79
14101310122222
12(4)68(3)80
7760226850
Этап 1202026192
Этап 220202619
Этап 320202619
Этап 420202612
Этап 52026
Этап 62026
Этап 71626
Этап 826

Суммарные транспортные расходы, соответствующие данному плану перевозок равны

.

Сравним расчеты, проделанные тремя методами. Транспортные расходы, рассчитанные:

1) методом северо-западного угла составили 8452 у. е.,

2) методом минимального элемента соответственно 6342 у. е.,

3) пересчитанные по методу потенциалов – 6118 у. е.,

4) методом Фогеля соответственно – 6390 у. е.

Наименьшие транспортные расходы составили расходы, рассчитанные по методу потенциалов.

Задача № 4

Сетевая задача

Ниже приведено 10 вариантов транспортной задачи в сетевой постановке. Каждая задача изображена в виде неориентированного связного графа. На ребрах проставлены значения тарифов , на вершинах (в кружках) – значения запасов-потребностей . Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.

34
10
23

Решение. Построим пробный опорный план (рис.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
3113114110173825
352026817143836
1237384938221013
2821484344292612
3722394626204449
224919220304516
452752130213423
433320293463321

Решение.

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.

3113114110173825
0 ( 7 )0(13)1 ( 8)
352026817143836
0(11)0(14)0(12)1 ( 15 )0 ( 7)0 ( 10)
1237384938221013
1(1)
2821484344292612
1(4)
3722394626204449
1 ( 2 )
224919220304516
1( 3 )
452752130213423
1 ( 6 )
433320293463321
1 ( 5 )

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

Условных единиц эффективности

Вариант выбора проверим на оптимальность. Для этого вычислим потенциалы и оценки.

Отсюда вычислим потенциалы:

Для небазисных переменных вычислим оценки по соответствующей формуле:

И так далее расчеты по соответствующим формулам и данным приведены в таблице 5.2.

Таблица 5.2

Х02813194110443829
3113114110173825
00 ( 7 )0(13)1 ( 8)
Оценка 1-308274
352026817143836
70(11)0(14)0(12)1 ( 15 )0 ( 7)0 ( 10)
Оценка 24037
81237384938221013
1(1)
Оценка 324-16-11-20303624
292821484344292612
1(4)
Оценка 4292127-5444146
3722394626204449
201 ( 2 )
Оценка 5111101544414
224919220304516
361( 3 )
Оценка 642367526502949
452752130213423
171 ( 6 )
Оценка 733137-3402123
433320293463321
21 ( 5 )
Оценка 8-6-118-1916717

Cреди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок Строим цикл пересчета: (3,5), (2,5), (1,7), (1,4), (3,5) замыкающийся на разрешающей клетке. Вычислим величину корректировки . Базисный нуль 03,5 перемещается в клетку (1,7), переменная х1,7 включается в базис, а переменная х3,5 выходит из базиса. Получим новую комбинацию расстановки единиц и нулей (Табл. 5.3). Суммарная эффективность равна:

Условных единиц эффективности

Таблица 5.3

Х02813194110443829
3113114110173825
01 ( 7 )0(13)0 ( 8)
Оценка 1-308274
352026817143836
70(11)0(14)0(12)0 ( 15 )1 ( 7)0 ( 10)
Оценка 24037
281237384938221013
1 ( 7 )
Оценка 3444920505644
292821484344292612
1(4)
Оценка 4292127-5444146
3722394626204449
201 ( 2 )
Оценка 5111101544414
224919220304516
361( 3 )
Оценка 642367526502949
452752130213423
171 ( 6 )
Оценка 733137-3402123
433320293463321
21 ( 5 )
Оценка 8-6-118-1916717

Заново вычисляем потенциалы и оценки.

Отсюда вычислим потенциалы:

Для небазисных переменных вычислим оценки в таблице 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

Х12813194110443829
3113114110173825
01 ( 7 )0(13)0 ( 8)
Оценка 1-308274
352026817143836
70(11)0(12)0 ( 15 )1 ( 7)0 ( 10)
Оценка 24037
281237384938221013
1 ( 7 )
Оценка 3444920505644
292821484344292612
1(4)
Оценка 4292127-5444146
3722394626204449
201 ( 2 )
Оценка 5111101544414
224919220304516
361( 3 )
Оценка 642367526502949
452752130213423
171 ( 6 )
Оценка 733137-3402123
433320293463321
20(14)1 ( 5 )
Оценка 8-6-118-1916717

Суммарная эффективность не изменилась и равна:

Условных единиц эффективности

Заново вычисляем потенциалы и оценки. Расчеты оценок приведены в таблице 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

Х22813194110443829
3113114110173825
01 ( 7 )0(13)0 ( 8)
Оценка 1-308274
352026817143836
70(11)0(12)0 ( 15 )1 ( 7)0 ( 10)
Оценка 24037
281237384938221013
1 ( 7 )
Оценка 3444920505644
292821484344292612
1(4)
Оценка 4292127-5444146
3722394626204449
201 ( 2 )
Оценка 5111101544414
224919220304516
361( 3 )
Оценка 642367526502949
452752130213423
171 ( 6 )
Оценка 733137-3402123
433320293463321
210(14)1 ( 5 )
Оценка 861120292629

Заново вычисляем потенциалы и оценки. Расчеты оценок приведены в таблице 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 :

3113114110173825
352026817143836
1237384938221013
2821484344292612
3722394626204449
224919220304516
452752130213423
433320293463321

Шаг 1. Обозначим через наибольший элемент столбца матрицы (r1 =45, r2 =49, r3 =48, r4 =49, r5 =44, r6 =46, r7 =45, r8 =49). Каждый элемент -го столбца вычтем из , результаты вычислений будем помещать на место вычитаемого. Аналогичные преобразования проводим в остальных столбцах. Получим неотрицательную матрицу , в каждом столбце которой есть хотя бы один нуль.

C1 =14363783429724
102922412732713
33121006243536
1728060171937
82793182610
23029472416030
022432814251123
21628204101225

Шаг 2. Преобразуем матрицу . Для этого обозначим через минимальный элемент строки , который последовательно вычтем из элементов той же строки, результаты поместим на место уменьшаемого. Наименьший элемент первой строки матрицы равен 7. Проведем вычисления для элементов первой строки: (d11 =7, d12 =29, d13 =30, d14 =1, d15 =27, d16 =22, d17 =0, d18 =17). Такие же вычисления проведем для остальных строк, получим неотрицательную матрицу , в каждом столбце и каждой строке которой есть хотя бы один нуль.

D=72930127220 *17
3221534202506
3312100 *6243536
17280 *60171937
82793182610 *
230 *29472416030
0 *22432814251123
2162820410 *1225

Основной этап. После второго шага предварительного этапа получим неотрицательную матрицу , эквивалентную матрице эффективностей :

П.1. В первом столбце матрицы отметим звездочкой 0*7,1 ,во втором столбце – 06,2 , в третьем столбце – 04,3 , в четвертом столбце – 0*3,4 , в шестом столбце – 08,6 , в седьмом столбце – 01,7 , в восьмом столбце – 05,8. Нули в пятом столбце – 04,5 нельзя отметить звездочкой, так как они лежат в строке, в которой уже есть нуль со звездочкой – 04,3, . Число звездочек равно семи, что меньше размерности матрицы (8), переходим к п.2.

D=+++++++
72930127220 *17
322153420250 ‘6
3312100 *6243536
17280 *60 ‘171937+
82793182610 *
230 *294724160 ‘30
0 *22432814251123
2162820410 *1225

ε=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 =

72924121220 *17
32293414250 ‘6+
331240 *0 ‘243536
23340 *120 ‘232543+
82733122610 *
230 *234718160 ‘30
0 *2237288251123
2162220350 *1225

П.2. Незанятый нуль находится в третьей строке пятого столбца 03,5 . Помечаем штрихом 0’3,5 . Во второй строке седьмого столбца находится нуль со штрихом. Помечаем штрихом 0’2,7 и считаем седьмой столбец незанятым, знак “+” сверху снимаем, а вторую строку объявляем занятой и помечаем знаком “+” справа.

+++++++

D2 =

72924121220 *17
32293414250 ‘6+
331240 *0 ‘243536
23340 *120 ‘232543+
82733122610 *
230 *234718160 ‘30
0 *2237288251123
2162220350 *1225

П.5. Переходим к пункту 2. Помечаем звездочкой 0*6,5, штрихом 0’8,3, 0’2,7 . В третьей нет , следовательно, переходим к пункту 4, ε=d6,4 =7 после преобразований, получим матрицу D3

+++++++

D3 =

72924121220 *17
32293414250 ‘6+
331240 *0 ‘243536
23340 *120 ‘232543+
82733122610 *
230 *234718160 ‘30
0 *2237288251123
2162220350 *1225

П.4. Строим цепочку из нулей. Начиная от только что отмеченного штрихом нуля (0’2,7 ), идем по строке до 5,2 цепочка состоит из двух элементов Ц: 07,2, 0’5,2 . В матрице такие цепочки обозначают так . После преобразования получим новый набор нулей со звездочкой (), который содержит на одну звездочку больше, чем предыдущий набор.

Проводим следующие пересчеты.

++++++

D3 =

2500*2719162032+
34327231450*+
632023205187+
0*3610005217
00′9195451912+
15241070′0*55
220*138915229
6320207340*8+

Процесс окончен, так как число нулей со звездочкой равно размерности матрицы эффективности.

Оптимальный вариант выбора (1,2)(2,7)(3,8)(4,1)(5,4),(6,6),(7,5),(8,3). Это значит, что первая невеста выберет второго жениха, вторая невеста седьмого жениха, третья – восьмого, четвертая первого, пятая четвертого, шестая – шестого, седьмая невеста пятого жениха, а восьмая невеста выберет третьего жениха.

При этом максимальная суммарная эффективность (суммарная продолжительность жизни всех семей) равна: (единиц эффективности)


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