4.5 Метод отбора наиболее перспективных проектов

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

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

Минимизации подлежит следующая функция

.

Первое слагаемое здесь – это капитальные затраты на дуге ij, которые зависят от уровня технической оснащенности пути . Второе слагаемое – издержки пользователей сети: произведение потока на стоимость перевозки . Причем эта последняя величина зависит как от величины потока, так и от уровня технической оснащенности дороги:

.

Целевая функция F рассматривается при следующих ограничениях:

• сетевые ограничения;

• фиксированная матрица поездок;

• задан маршрут движения (т.е. известна модель выбора маршрута).

Как и в случае непрерывной оптимальной корректировки в этом методе попеременно игнорируется оптимизация и ограничения.

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

Пример подобной процедуры: формирование сети муниципального транспорта в городе – муниципальная сеть транспорта формируется с точки зрения максимального удовлетворения пассажиров, т.е. это дескриптивное распределение потоков транспорта.

Далее, игнорируя ограничения, получаем следующую задачу оптимизации:

.

Полагая теперь, что функция дифференцируема по непрерывным переменным , получаем, что в точке минимума выполняется условие

.

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

,

(Рисунок 27).

Рисунок 27 – Иллюстрация к методу отбора наиболее

перспективных проектов

Из рисунка 27 следует, что для того чтобы достичь минимума , необходимо поднимать уровень технической оснащенности дуги: . А это означает, что требуется выделение капитальных вложений для реконструкции дуги ij.

Этот процесс должен продолжаться до тех пор, пока производная не обратиться в нуль.

Таким образом, выделение капитальных вложений для дуги ij необходимо, если

.

Из этого неравенства можно получить следующее соотношение:

.

В числителе этого соотношения стоит изменение издержек пользователей сети, а в знаменателе – изменение расхода капитальных вложение. Поэтому правило, которое вытекает из рассмотренного соотношения, может быть записано следующим образом: капитальные вложения в инфраструктуру дорог следует вносить при условии, когда отношение изменений дохода пользователей к изменению расхода капитальных вложений больше единицы.

4.6 Примеры сетевых задач, сводящихся к задачам линейного программирования

Напомним, прежде всего, постановку задачи линейного программирования. Требуется найти экстремум линейной функции, на аргументы которой наложены линейные ограничения.

Таким образом, задачи линейного программирования (ЗЛП) относятся к задачам на условный экстремум. Однако для исследования линейной функции многих переменных на условный экстремум нельзя применять хорошо разработанные методы математического анализа.

Действительно, пусть

при линейных ограничениях

Необходимым условием экстремума является равенство нулю частных производных

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

,

Отсюда

Так как все коэффициенты линейной функции не могут быть равны нулю, то внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть только на границе области.

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

Рассмотрим вначале формы записи задач линейного программирования.

Модель задачи линейного программирования может быть записана в одной из приведенных ниже форм:

1. Общая или произвольная форма записи

при ограничениях

– произвольные .

2. Симметричная или стандартная форма записи

1. 

2. 

3. Каноническая или основная форма записи

Указанные выше три формы записи ЗЛП эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть сведена к другой форме.

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

Так, при необходимости задачу минимизации можно заменить задачей максимизацией и наоборот:

.

Неравенство типа путем умножения левых и правых частей на -1 можно превратить в неравенство типа и наоборот.

Ограничения-неравенства типа

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

Если в ЗЛП какая-либо переменная не подчинена условию неотрицательности, ее заменяют разностью двух других неотрицательных переменных и :

.

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

Найти оптимальный план , доставляющий

(1)

при ограничениях

(2)

(3)

Начнем с геометрической интерпретации области допустимых решений.

Каждые из неравенств (2) определяет на координатной плоскости некоторую полуплоскость, а система неравенств (2), (3) в случае ее совместности – их пересечение.

Это множество будет выпуклым. Оно может представлять собой следующие геометрические конструкции (Рисунок 28).

Перейдем далее к геометрической интерпретации целевой функции (1).

Уравнение при фиксированном значении определяет на плоскости прямую линию

.

При изменении получается семейство параллельных линий, называемое линиями уровня.

а)		выпуклый многоугольник (число вершин равно m);
б)		неограниченная выпуклая многоугольная область;
в)		отрезок прямой;
г)		луч;
д)		точка;
е)		пустое множество.

Рисунок 28 – Геометрическая интерпретация ЗЛП

Вектор с компонентами из коэффициентов при и перпендикулярен к каждой из линий уровня.

Вектор показывает направление возрастания (убывания) целевой функции.