Куцый Н.Н. Математические методы системного анализа и теория принятия решений. Пособие по курсовой работе

Подождите немного. Документ загружается.

1 2 3 4 5

1 13 7 0,5 0,5 6,5

♣

2 11,5 8,5 2 0 5

3 7,5 7,5 6 6 0

4 0 0 5,5 12,5 7,5

5 8,5 1,5 0 7 12

ЭТАП 5. ПЕРЕМЕЩЕНИЕ НЕКОТОРЫХ НУЛЕЙ

Рассмотрим ту часть таблицы, которая состоит из неотмеченных заливкой

элементов, и возьмем наименьшее число в ней. Вычтем это число из элементов

неотмеченных заливкой столбцов и прибавим к элементам отмеченных залив-

кой строк.

Отметим, что это можно сделать, исходя из основной идеи венгерского ме-

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

шении (или увеличении всех элементов

строки таблицы (или ее столбца) на

одну и ту же величину

В рассматриваемом примере по-прежнему неотмеченными заливкой эле-

ментами являются элементы строки 1; наименьший элемент этой строки равен

0,5. Поэтому вычтем 0,5 из всех элементов столбцов 1,2,3,4,5 и прибавим 0,5 к

элементам строк 2,3,4,5. Если формально рассмотреть эти действия, т.е. вычи-

тание и сложение, то следует отметить, что фактически выполнено вычитание

0,5 из элементов строки 1. Тем самым получим таблицу 5.10.

Таблица 5.10

1 2 3 4 5

1 12,5 6,5 0 0 6

2 11,5 8,5 2 0 5

3 7,5 7,5 6 6 0

4 0 0 5,5 12,5 7,5

5 8,5 1,5 0 7 12

ЭТАП 6. ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ ИЛИ ВЫПОЛНЕ-

НИЕ ОЧЕРЕДНОГО ШАГА

Будем в новой, полученной на этапе 5, таблице, которая содержит числа

)2(

, искать оптимальное решение, как это представлено в описании этапа 2.

Если при этом получим оптимальное решение, то процесс заканчивается. Если

это не так, то повторим этапы 3,4 и 5. Затем, при необходимости, вернемся к

этому этапу еще раз.

Повторим этап 2 в рассматриваемом примере получим таблицу 5.11.

Таблица 5.11

1 2 3 4 5

1 12,5 6,5 0 0 6

♣

2 11,5 8,5 2 0 5

♣

3 7,5 7,5 6 6 0

4 0 0 5,5 12,5 7,5

5 8,5 1,5 0 7 12

♣

♣ ♣

Таблица 5.11 содержит новые перечеркнутые и подчеркнутые двойной

чертой нули. И так как мы получили четыре подчеркнутых двойной чертой

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

к этапу 3.

Преследуя учебные цели, опишем более или менее подробно последую-

щие поэтапные действия. Пометим символом (♣) строку 1, как строку, которая

не содержит ни одного подчеркнутого двойной чертой нуля. Отметим символа-

ми (♣) столбцы 3 и 4, каждый из которых содержит перечеркнутый нуль в по-

меченной строке 1. Отметим строки 2 и 5, как строки, каждая из которых имеет

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

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

ч е н н ый с т о л б е ц , т.е. в нашем случае это строки 3 и 4, а столбцы также 3 и

4, но это не более чем совпадение.

Рассмотрим часть таблицы, которая неотмечена заливкой и возьмем наи-

меньшее в ней, т.е. здесь 1.5 и вычтем это число из элементов столбцов 1,2 и 5,

как из неотмеченных заливкой столбцов и строк. Тем самым мы получим та-

блицу 5.12.

Таблица 5.12

1 2 3 4 5

1 11 5 0 0 4,5

♣

2 10 7 2 0 3,5

♣

3 7,5 7,5 7,5 7,5 0

4 0 0 7 14 7,5

♣

5 7 0 0 7 10,5

♣

♣ ♣ ♣ ♣

Применим к таблице 5.12 действия этапа 2 и получим, что число подчерк-

нутых двойной чертой не равно размерности матрицы, т.е. пяти. Тем самым

переходим к этапу 3. Затем в таблице 5.12 отметим заливкой непомеченную

строку 3 и помеченные столбцы 2,2,3,4. Оформим результаты дей-

ствий в виде таблицы 5.13.

Таблица 5.13

1 2 3 4 5

1 11 5 0 0 4,5

♣

2 10 7 2 0 3,5

♣

3 7,5 7,5 7,5 7,5 0

4 0 0 7 14 7.5

♣

5 7 0 0 7 10,5

♣

♣ ♣ ♣ ♣

Переходим к этапу 5, т.е. из части таблицы, которая не отмечена заливкой

выделим наименьший элемент, т.е.

5,3

и вычтем его значение из элемен-

тов неотмеченных заливкой столбцов, т.е. из элементов столбца 5 и прибавим к

элементам отмеченных заливкой строк, т.е. к элементам строки 3. Получим та-

блицу 5.14.

Таблица 5.14

1 2 3 4 5

1 11 5 0 0 1

2 10 7 2 0 0

3 11 11 11 11 0

4 0 0 7 14 4

5 7 0 0 7 7

Применим к таблице 5.14 действия этапа 2 и в этой таблице получим, что

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

пяти. Тем самым из этих нулей можно составить оптимальное решение. Теперь

необходимо вернуться к таблице 5.4, согласно которой найденному решению

соответствует суммарное время

9 + 5 + 5,5 + 4,5 + 9,5 =33,5.

Представим оптимальное решение в виде таблицы 5.15, которая аналогич-

на таблице 5.5; при этом напомним, что единица соответствует выбранному на-

значению.

Таблица 5.15

1 2 3 4 5

1 0 0 1 0 0

2 0 0 0 1 0

3 0 0 0 0 1

4 1 0 0 0 0

5 0 1 0 0 0

Представим результат решения задачи в более наглядной форме, для чего

рассмотрим последовательно столбцы, начиная с первого.

В первом столбце 1 соответствует времени 4,5 из таблицы 5.4, а это значе-

ние времени взято из таблицы 5.2 и из чего следует, что 1-ый экипаж живет в

пункте А и обслуживает рейсы 1 и 104. Перерыв 4,5 часа.

Во втором столбце 1 соответствует времени 9,5 часа из таблицы 5.4, а это

значение взято из таблицы 5.3, из чего следует, что 2-ой экипаж живет в пунк-

те B и обслуживает рейсы 105 и 2. Перерыв 9,5 часов.

Продолжая этот процесс далее получим.

3-й экипаж живет в пункте B. Обслуживает рейсы 101 и 3. Перерыв 9 ча-

сов.

4-й экипаж живет в пункте A и обслуживает рейсы 4 и 102. Перерыв 5 ча-

сов.

5-й экипаж живет в пункте B. Обслуживает рейсы 103 и 5. Перерыв 5,5 ча-

сов.

ЛИТЕРАТУРА

1.Акоф Р., Сасиени М. Основы исследования операций. - М.: Мир, 1971. -

534с.

2.Акоф Р. Искусство решения проблем. - М.: Мир, 1982. -224с.

3.Алексеев А.Д. Многовариантная транспортная задача по критерию вре-

мени//Известия АН СССР. Техническая кибернетика. - 1984. - № 6. - С.188-189.

4.Банди Б. Основы линейного программирования. - М.: Радио и связь,

1989. - 176с.

5.Вентцель Е.С., Овчаров Л.А. Прикладные задачи теории вероятностей. -

М.: Радио и связь, 1983. - 416с.

6.Гольштейн Е.Г., Юдин Д.В. Задачи линейного программирования транс-

портного типа. - М., Наука, 1969. - 284с.

7.Данциг Дж. Линейное программирование. Его применения и

обобщения/Пер. с англ. -–М., Наука, 1969. – 284с.

8.Дегтярев Ю.И. Исследование операций:Учеб. для вузов по спец. АСУ. –

М.:Высшая школа, 1986. – 320с.

9.Зайченко Ю.П. Исследование операций. – 2-е изд., перераб. и доп. Киев:

Вища школа, 1979. 392с.

10.Кофман А., Фор Р. Займемся исследованием операций/Пер. с франц.

под ред. А.А. Корбута. - М. :Мир, 1966. -279с.

13.Калихман И.Л. Сборник задач по линейной алгебре и программирова-

нию. - М.: Высшая школа, 1969. - 160с.

14.Зайченко Ю.П., Шумилова С.А. Исследование операций. Сбор-

ник задач. - Киев:Вища школа. Изд-во Киев. ун-та, 1984. - 224с.

15.Исследование операций: В 2-х томах/ Под ред. Дж. Моуэра, С. Элмагра-

би. - М.: Мир, 1981.

16.Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая

школа, 1967. - 427с.

17.Кофман А. Методы и модели исследования операций. - М.:Мир,1966. -

524с.

18.Кудрявцев Е.М. Исследование операция в задачах, алгоритмах и про-

граммах. - М.:Радио и связь, 1984. -183с.

19.Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи

производственно-транспортного планирования: Модели, методы, алгоритмы. -

М.:Наука,1986. - 260с.

20.Сакович В.А. Исследование операций (детерминированные методы и

модели): Справ. пособие. - Минск:Высш. шк., 1985. - 256с.

21.Ховард Р.А. Динамическое программирование и марковские

процессы/Пер. с англ. В.В. Быкова; Под ред. Н.П. Бусленко. - М.: Советское ра-

дио, 1964. - 192с.