4 Лекция 4. Применение линейного программирования в энергетике

Содержание лекции:

- области применения и основные приемы решения. Составление математической модели и методы нахождения опорного плана транспортной задачи. Метод потенциалов.

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

Цели лекции:

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

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

Надо найти значения х₁, ……,х_n, при которых может быть обеспечено экстремальное значение функции Ц(х), при ограничениях

В ограничения, присутствующие в задачах линейного программирования, иногда вводят также ограничения в виде условий неотрицательности всех или части переменных x_j≥0, j=1,....,p.

Целевую функция Ц(а,х) иногда называют критерием или функционалом задачи линейного программирования.

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

Постановка транспортной задачи в матричной форме. Формулировка транспортной задачи по критерию стоимости приведена ниже. В m пунктах производства А₁, …..,А_m находится однородный продукт (сахар, уголь, картофель и т.д.)в количествах соответственно а₁,…..,а_m, который должен быть доставлен n потребителям В₁,….,В_n в количествах b₁,…..,b_n. Известны транспортные издержки с_ij (расходы), связанные с перевозкой единицы продукции из пункта А_i в пункт В_j.

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

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

Т а б л и ц а 4.1

Поставщик	Потребитель					Запасы груза
	В1	В2	….	Вn
А1	с11 х11	с12 х12	….	с1n х1n	а1
А2	с21 х21	с22 х22	….	с2n х2n	а2
……	……	……	……	……	……
Аm	сm1 хm1	сm2 хm2	……	сmn хmn	аm
Потребность в грузе	b1	b1	……	bn

Матрица называется матрицей тарифов (издержек или транспортных расходов), а числа с_ij – тарифами.

Планом транспортной задачи называется где каждое число хij обозначает количество единиц груза, которое надо добавить из i-го пункта отправления в j-й пункт назначения. Матрицу Х называют еше матрицей перевозок.

Общие суммарные затраты, связанные с реализацией плана перевозок, можно представить целевой функцией

(4.1)

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

(4.2)

(4.3)

Условия (4.2) образуют систему ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.

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

Для транспортной задачи важное значение имеет следующая теорема: Ранг матрицы транспортной задачи на единицу меньше числа уравнений, т.е.

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

Определение исходного опорного плана. 1. Правило «северо-западного угла». Для составления исходного плана перевозок удобно пользоваться правилом «северо-западного угла», которое состоит в следующем.

Заполняем таблицу начиная с левого верхнего (северо-западного) угла, двигаясь далее по строке вправо или по столбцу вниз. Занесем в клетку (1, 1) меньшее из чисел а₁ и b₁, т.е.

Если a₁>b₁, то х₁₁= b₁ и первый столбец «закрыт» для заполнения остальных его клеток, т.е. х_i1=0 для i=2,3,….,m (потребности первого потребления удовлетворены полностью). Двигаясь далее по первой строке, записываем в соседнюю клетку (1, 2) меньшее из чисел а₁-b₁ и b₂, т.е.

Если b₁>a₁, то аналогично «закрывается» первая строка, т.е. x_1k=0 для k=2,3,….,n. Переходим к заполнению соседней клетки (2, 1) куда заносим

.

Заполнив клетку (1, 2) или (2, 1), переходим к заполнению следующей, третьей клетки либо по второй строке, либо по второму столбцу. Процесс продолжается до полного исчерпания груза у поставщиков или полного удовлетворения потребителей. Последняя заполненная клетка (m, n) окажется лежащей в последнем n-м столбце и в последней m-й строке.

2.Правило «минимального элемента». Число итераций можно сократить, если исходный план строить по более усовершенствованному правилу «минимального элемента». Сущность его состоит в том, что на каждом шаге осуществляется максимально возможная поставка в клетку с минимальным тарифом с_ik. Заполнение таблицы начинаем с клетки, которой соответствует наименьший элемент с_ik из всей матрицы тарифов. Затем остаток по столбцу или строке помещаем в клетку того же столбца или строки, которой соответствует следующее по величине значение с_ik , и т.д. Последовательность заполняемых клеток определяется по величине с_ik , а помещаемые в этих клетках величины x_ik как и в правиле «северо-западного угла».

Решение транспортной задачи методом потенциалов. Сущность метода потенциалов состоит в следующем. После того как найден исходный опорный план перевозок, каждому поставщику Аi (каждой строке) ставится в соответствие некоторое число u_i а каждому потребителю B_j (каждому столбцу) – некоторое число _j. Числа u_i и _j называются потенциалами соответственно поставщика А_i и потребителя В_j и выбираются так, чтобы в любой загруженной клетке их сумма равнялась тарифу этой клетки, т.е.

u_i +_j =с_ij. Так как всех потенциалов m+n, занятых клеток m+n-1, то для определения чисел u_i и _j придется решать систему из m+n-1 уравнений

u_i +_j =с_ij с m+n неизвестными.

План оптимален, когда для каждой свободной клетки (i, j) разность s_ij есть величина неотрицательная, т.е.

Полученные разности называются оценками (характеристиками) свободных клеток.

Чтобы решить транспортную задачу методом потенциалов, необходимо:

1) построить опорный план перевозок по одному из вышеизложенных правил;

2) вычислить потенциалы u_i и _j соответственно поставщиков и потребителей;

3) вычислить суммы потенциалов (косвенные тарифы) для свободных клеток u_i +_j =с_ij ;

4) проверить разность s_ij=c_ij - c_ij.