По методу циклических перестановок

Для получения нового плана надо перераспределить перевозимый груз между поставщиками и покупателями таким образом, чтобы снизить суммарную стоимость перевозок, не нарушив при этом условий задачи (т.е. сохранив заданные объемы заявок и запасов). Эффективное решение этой задачи обеспечивает метод циклических перестановок.

Сначала необходимо наметить маршрут циклической перестановки – определить так называемый цикл пересчета. Клетку, с которой начинается цикл пересчета, можно выбрать по результатам выполнения п. 4.4 – из числа тех клеток, в которых нарушаются условия (4.4). Для каждой такой клетки надо определить приращение стоимости перевозки (той перевозки, которую символизирует данная клетка), даваемое текущим решением : D с₁₆ = 3­ – 4 = – 1; D с₃₆ = 5­ – 6 = – 1; D с₄₂ = 5­ – 2 = – 3; D с₄₃ = 4­ – 6 = – 2. В качестве «отправного пункта» цикла пересчета следует взять клетку с наибольшей абсолютной величиной D с_ij. Для рассматриваемого примера – клетка (4, 2).

Циклом пересчета называют ломаную линию, начинающуюся в свободной клетке, остальные вершины которой помещены в базисные клетки, а звенья лежат вдоль строк и столбцов таблицы. В каждой вершине встречаются только два звена, причем одно из них расположено по строке, другое по столбцу. Никакие три вершины, встречающиеся подряд при обходе, не лежат на одной прямой. Если циклом служит самопересекающаяся линия, то точки самопересечения не могут быть ее вершинами. Свободной клетке в цикле присваивается знак «+», другим вершинам - чередующиеся по ходу знаки «-», «+», «-» и т. д.

Цикл пересчета для клетки А₄В₂ показан в таблице 4.7.

Так как число «положительных» и «отрицательных» вершин цикла одинаково, то баланс не нарушится, если в «отрицательных» вершинах вычесть какое-либо число, а в «положительных» вершинах прибавить это же число.

В «минусовых» вершинах составленного таким образом цикла стоят числа 6 и 16. Вычтя минимальное из этих чисел – в данном случае это число 6 – в «отрицательных» вершинах, получим новую свободную переменную x₂₂ (клетка А₂В₂). Вместо нее в базис войдет x₄₂ (клетка А₄В₂). Это значит, что уравнение a₂+b₂ =1 системы (4.3) надо перенести в систему (4.4) в виде a₂ + b₂ £ 1, а неравенство a₄ +b₂ £ 2 из системы (4.4) – в систему (4.3), записав это ограничение в виде уравнения a₄ +b₂ = 2.

Прибавив число 6 в «положительных» вершинах цикла и решив новую систему уравнений, получим следующее допустимое решение (табл. 4.8), которое так же, как и предыдущее, оказалось неоптимальным. Следовательно, необходимо повторить описанные выше действия еще раз (табл. 4.8). Для решения данного примера понадобилось организовать четыре цикла пересчета. Оптимальное решение (табл. 4.9): х₁₄ = 18; х₁₆ = 5; х₂₅ = 28; х₂₆ = 4; х₃₃ = 19; х₃₆ = 12; х₄₁ = 18; х₄₂ = 11; х₄₃ = 5.

Ему соответствует следующее значение суммарной стоимости перевозок (оптимальное значение целевой функции):

W_min = f_min(x) = 1 × 18 + 2 × 11 + 4 × 19 + 5 × 4 + 1 × 20 + 5 × 28 + + 4 × 4 + 3 × 5 + 5 × 12 = 387.

 

Таблица 4.8

Второе допустимое решение и второй цикл пересчета

	b1 = 0	b2 = 1	b3 = 5	b4 = 1	b5 = 8	b6 = 7
+ – a1 = 0	0 £ 7	1 = 1	5 £ 8	1 = 1	8 £ 5	7 £ 3
– a2 = – 3	–3 £ 7	–2£1	2 £ 8	–2 £ 5	5 = 5	4 = 4
a3 = – 1	–1 £ 3	4 £ 7	4 = 4	0 £ 5	7 = 7	6 £ 5
– + + a4 = 1	1 = 1	2 = 2	6 £ 4	2 £ 9	9 = 9	8 £ 9

Таблица 4.9

Оптимальное решение транспортной задачи

	b1 = –1	b2 = 0	b3 = 2	b4 = 1	b5 = 4	b6 = 3
a1 = 0	0 £ –1	0 £ 1	2 £ 8	1 = 1	4 £ 5	3 = 3
a2 = 1	0 £ 7	1 £ 1	3 £ 8	2 £ 5	5 = 5	4 = 4
a3 = 2	1 £ 3	2 £ 7	4 = 4	3 £ 5	6 £ 7	5 = 5
a4 = 2	1 = 1	2 = 2	4 = 4	3 £ 9	6 £ 9	5 £ 9

ЗАКЛЮЧЕНИЕ

Основной целью при изучении методов и средств теории принятия решений является выявление их системно-комплексного единства. В области линейного программирования наиболее явно данное свойство проявляется в изоморфизме отдельных моделей в процессе применения методологии «спора моделей». Каждая из указанных моделей возникает в результате рассмотрения объекта исследования на соответствующем уровне абстрактного описания рационально-эмпирического комплекса систем.

Применение рационально-эмпирического подхода и задачного принципа на практике создают условия для формирования системообразующих основ в системном анализе и исследовании операций. «Только при полном понимании задач можно найти соответствующие способы их решения. Для результатов важнее поставить правильные вопросы, чем правильно ответить на ошибочные» [5, с.19].

Необходимо отдавать себе отчет в том, что рассмотренные задачи линейного программирования представляют собой частные случаи более широких классов задач, имеющих важное научно-практическое значение и решаемых в инженерной деятельности.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Shannon R.E., Biles W.E. The Utility of Certain Curriculum Topics to Operation Research Practitioners, Operation Research, v. 18, №4, Jul. Aug. 1970.

2. Weston F.C. OR Technologues Relevant to Corporate Peanning Function Practices, An Investigative Look, presented at 39^th National Meeting, Operation Practices Society of America, Operation Research Bulletin, v.19, Suppl.2, Spring, 1971.

3. Исследование операций в экономике. Учебн. пособие для вузов. Н.Ш. Кремер, Б.А. Путка, И.М. Тришин, М.Н. Фридман/ Под ред. проф. Н.М. Кремера – М.: Банки и биржи, ЮНИТИ, 1999. – 408 с.

4. Панченко В. М. Теория систем: Учебное пособие. М: –МИРЭА (ТУ), 1996 – 128 с.

5. Клир Дж. Системология. Автоматизация решений системных задач. – М.: Радио и связь, 1990. – 540с.

6. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Советское радио, 1972.

7. Грешилов А.А. Как принять наилучшее решение в реальных условиях. – М: Радио и связь, 1991. – 320 с.: ил.

8. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах: Учеб. пособия для студентов втузов. В 2-х ч. Ч. 1. – 4-е изд., испр. и доп. – М.: Высш. шк.,1986. – 304 с.

9. Муртаф Б. Современное линейное программирование/ Пер. с англ. – М.: Мир, 1984. – 224 с.

10. Панченко В.М. Системный анализ. Метод имитационного моделирования: Учеб. пособие. – М.: МИРЭА, 1995. – 120 с.

11. Панченко В.М., Панов А.В. Системный анализ и исследование операций. Линейное программирование: Лабораторный практикум. – М.: МИРЭА, 2000. – 46 с.

12. Моисеев Н.Н. Математические задачи системного анализа. – М.: Наука. Главная редакция физико-математической литературы, 1981. – 488 с.

13. Волкова В.Н., Воронков В.А. и др. Теория систем и методы системного анализа в управлении и связи. – М.: Радио и связь, 1983. – 248 с.

14. Нечаев В.В., Панченко В.М. и др. Исследование операций и теория систем. Основы статистической динамики знаний: Учебное пособие. – М.: МИРЭА, 2000. – 83 с.

15. Рыков А.С. Методы системного анализа: оптимизация. – М.: НПО Экономика, 1999. – 255 с.

16. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. - М.: Наука, 1986. –544 с.

17. Таха Хэдми А. Введение в исследование операций, 6-е издание/ Пер. с англ. – М.: Вильямс, 2001. – 912 с.

18. Панов А.В. Теория систем. Модели и методы в инженерных исследованиях // Курс лекций. Часть I. – М.: Академия ФСБ РФ, 2001. – 95 с.

19. Панов А.В. Теория систем // Курс лекций. Часть II. – М.: Академия ФСБ РФ, 2001. – 64 с.

ПРИЛОЖЕНИЯ

Приложение 1

Проведение исследования