Табличный метод решения задачи.

Исходная таблица стоимостей аренды равнозначна сетевой модели, поэтому потенциалы V_i и оптимальные планы аренды можно найти непосредственно в таблице, не изображая сеть, тем более, что при большихNсеть становится громоздкой.

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

По выделенным клеткам находим оптимальные планы аренды. Для этого в первой строчке найдем выделенную клетку (1,i₁) с номером выделенного столбцаi₁ . Затем найдем в строкеi₁ выделенную клетку (i₁,i₂) с номером выделенного столбцаi₂ и так далее. Получим оптимальный план аренды. Другие планы, если они есть, находятся аналогично.

Рассмотрим снова пример2и получим следующую таблицу.

J i	2	3	4	5	6	7	Vi
1	49	99	145	197	244	296	288
2	–	50	96	146	198	247	239
3	–	–	48	95	147	189	189
4	–	–	–	49	98	148	148
5	–	–	–	–	51	101	101
6	–	–	–	–	–	53	53
7							0

В этой таблице выделены следующие клетки:

1. (6,7),.так как V₆ = C_6,7+V₇ = 53;

2. (5.7), так как V₅ = C_5,7+V₇ = 101

3. (4,7),.так как V₄ = C_4,7+V₇ = 148

4. (3,7), так как V₃ = C_3,7 +V₇= 189

5. (2,3), так как V₂ = C_2,3 + V₃ = 239

6. (1,2) и (1,3), так как V₁ = C_1,2 + V₂ = С_1,3 + V₃ = 288.

Последовательность выделенных клеток (1,2), (2,3),(3,7) дает оптимальный план аренды (1, 2, 3, 7), а последовательность выделенных клеток(1, 3) и(3,7) дает оптимальный план аренды (1, 3, 7). Стоимость оптимальных планов равна 288 у. е. (первая строка, дополнительный столбец).

Рекомендуемый библиографический список

Основная литература

1. Никитенков В.Л. Холопов А.А. Задачи линейного программирования и методы их решения. Уч. пособие. Сыктывкар: Изд-во СыктГУ, 2008, 268с. Электронная версия есть на сервере СыктГУ, лаборатория №2 , Учебные материалы \ Кафедра ГАМС \ Математическое программирование и ИО

2. Грызина Н. Ю.Математические методы исследования операций в экономике. Учебно-методический комплекс  - М.: Евразийский открытый институт. 2009. 204c. Эл. библиотека «Онлайн». (Электронная версия есть в методическом кабинете финансово-экономического факультета)

Дополнительная литература

3. Юденков А. М. Математическое программирование в экономике. Рек.УМО   - Москва: Финансы и статистика, 2010. (ЭБС)

4. Хазанова Л.Э. Математическое моделирование в экономике. М.: БЕК, 2002, 133с.

Приложение. Бесконтурные сети

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

Графявляется математическим, формальным представлением объектов, между которыми попарно установлены некоторые связи [1,2,4]. Объекты называютсявершинами и графически изображаются кружками. Связи считаются установленными междунекоторыми парамиизразличныхвершин и считаются односторонними. Графически связь изображается линией со стрелкой, илидугой,соединяющей две вершины. Согласно направлению связи, т.е. направлению стрелки, соединяемые вершины являютсяначалом иконцомдуги, или, другими словами, начальной и конечной вершинами дуги.

Будем считать, что между двумя вершинами есть не более одной дуги (нет "параллельных" дуг). Формально этого можно добиться, разбив дугу на две с помощью промежуточной вершины. В дальнейшем дугу будем записать в виде упорядоченной пары (a,b), гдеa– начало дуги,b– конец дуги.

Путём из вершиныв вершину, или путём, начинающимся ви заканчивающимся в, называется последовательность вершин, где пары,, …,являются дугами. Графически путь представляет непрерывную направленную линию из дуг, согласованную с направлениями стрелок ("движения по стрелкам"). Если, т.е. если начало пути совпадает с концом пути, то путь называетсяконтуром.Цепочкой из вершиныв вершинуназывается последовательностьиз различных вершин, в которой дугами являютсяили,или, и т.д. Таким образом, цепочка соответствует линии извбез учёта направления стрелок. Замкнутая цепочка называетсяциклом.

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

Рис. 1

( a,c,b,d,f ) – путь ( b,d,f,c,b ) – контур ( a,b,c,f ) – цепочка ( a, b, c, a ) – цикл

Определение. Конечная совокупность вершин и дуг (и их графическое изображение) называетсясетью, если выполняются условия:

а) связности;

б) отсутствия петель (начало и конец дуги различны);

в) отсутствие параллельных дуг. 

Определение.Сеть называетсябесконтурной, илиупорядоченнойсетью, если в ней нет контуров.

Замечание. В литературе встречается также терминациклическая сеть.

Сеть на рис.1 не является бесконтурной, т.к. есть контур (b,d,f,c,b).

Н у м е р а ц и я вершин сети – это сопоставление вершинам номеров – натуральных чисел, при этом различным вершинам сопоставляются различные номера.

Определение. Нумерация называетсяправильной, если:

а) номера идут подряд: 1, 2, …, m, гдеm – число вершин;

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

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

В бесконтурных сетях правильная нумерация возможна и может быть проставлена по следующей процедуре (алгоритм Форда).

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

2.Присвоим найденной вершине текущий номер. Первый раз таким номером являетсяm– число вершин сети.

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

Замечание. 1. Если не удаётся найти вершину в шаге 1, то в сети есть контур и правильная нумерация невозможна, так что алгоритм Форда является проверкой, будет ли сеть бесконтурной.

2. Правильных нумераций в сети может быть несколько.

Пример 2.