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

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

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

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

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

 

J i						7	Vi
	–
	–	–
	–	–	–
	–	–	–	–
	–	–	–	–	–

 

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

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 (есть также предыдущее издание 1999 года; есть также электронный вариант).

2. Хазанова Л.Э. Математические методы в экономике. Учебное пособие. М.: Изд-во БЕК, 2002.– 144 с.

3. Вагнер Г.. Основы исследования операций. Т.1,2. М: Мир, 1973.

4. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика (Математическое программирование). М.: Вышэйшая школа. 2001. 351 с.

5. Таха Х. Введение в исследование операций. Т.2. М.: Мир, 1985.

ПРИЛОЖЕНИЕ. Бесконтурные сети

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

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

Будем считать, что между двумя вершинами есть не более одной дуги (нет "параллельных" дуг). Формально этого можно добиться, разбив дугу на две с помощью промежуточной вершины. В дальнейшем дугу будем записать в виде упорядоченной пары (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.

Неправильная нумерация Правильная нумерация (1 и 2, 4 и 5 можно поменять местами)

Рис. 2.