Математическая модель транспортной задач

Переменными (неизвестными) транспортной задачи являются x_ij, i= 1, 2, …, m, j= 1, 2, …, n – объёмы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок

х₁₁ х₁₂ … х_1n

X = х₂₁ х₂₂ … х_2n

… … … …

х_m1 х_m2 … х_mn

Так как произведение C_ijX_ij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны C_ijX_ij. По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид

Z(X) = C_ij X_ij → min

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

X_ij = a_i, i = 1, 2, …, m.

Вторая группа из n уравнений выражает требование полностью

удовлетворить запросы всех n потребителей:

Z(X) = C_ij X_ij → min, (1)

X_ij = a_i, i = 1, 2, …, m, (2) X_ij = b_j, j = 1, 2, …, n, (3)

X_ij ≥ 0, i = 1, 2, …, m, j = 1, 2, …, n. (4)

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей,

т.е. a_i = b_j (5)

Такая задача называется задачей с правильным балансом, а её модель -закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а её модель – открытой.

Математическая формулировка транспортной задачи такова: найти переменные задачи

X = (x_ij), i = 1, 2, …, m, j = 1, 2, …, n,

Удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4), и обеспечивающее минимум целевой функции (1).

Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу А системы уравнений - ограничений задачи (2), (3).

х₁₁ х₁₂ … х_1n х₂₁ х₂₂ … х_2n … х_m1 х_m2... х_mn

1 1 … 1 0 0 … 0 … 0 0... 0

0 0 … 0 1 1 … 1 … 0 0... 0

………………………………………………………………………………………

А = 0 0 … 0 0 0 … 0 … 1 1... 1 (6)

1 0 … 0 1 0 … 0 … 1 0... 0

0 1 … 0 0 1 … 0 … 0 1... 0

………………………………………………………………………………………

0 0 … 1 0 0 … 1 … 0 0... 1

Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной X_ij, является вектором – условием задачи и обозначается через А_ij. Каждый вектор имеет всего m + n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора А_ij Стоит на i-м месте, а вторая – на (m + j)-м месте, т.е.

Номер координаты

0 1 a₁

…

…

1 i a_i

…

А_ij= 0 m; A₀= a_m

0 m+1 b₁

…

1 m+j b_j

…

0 m+n b_n

Обозначим через A₀вектор ограничений (правых частей уравнений (3), (3) и представим систему ограничений задачи в векторном ви­де. Тогда математическая модель транспортной задачи запишется сле­дующим образом:

Z(x)= C_ij X_ij → min (7)

A_ij X_ij =A₀ (8)

X_ij≥0, i=1, 2, …, m, j=1, 2, …, n. (9)

17. Нахождение начального опорного решения транспортной задачи линейного программирования методом минимальной стоимости.

Метод минимальной стоимости

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C = (c_il), i = 1, 2, …, m, j = 1, 2, …, n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клет­ка таблицы, соответствующая минимальной стоимости (c_ij), и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую (c_ij), заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично с потребителем.

Теорема: Решение транспортной задачи, построенное методом минимальной стоимости, является опорным.

18. Нахождение начального опорного решения транспортной задачи линейного программирования методом северо-западного угла.

Метод северо-западного угла

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

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

1) если a_i < b_j, то x_ij = a_ij и исключается поставщик с номером i, x_ik = 0,

k = 1, 2,..., n, k ≠ j, = b_j - a_i;

2) если а_i. > Ь_j, то х_ij = b_j и исключается потребитель с номером j,

x_kj =0, k = 1, 2,..., m, k ≠ i, = a_i - b_j;

3) если a_i = b_j, то x_ij = a_i = b_j, и исключается либо i-й постав­щик,

х_ik = 0, k = 1, 2,..., n, k ≠ j, = 0 либо j-й потребитель, x_kj = 0,

k = 1, 2,... m, k ≠ i, = 0.

Нулевые перевозки принято заносить в таблицу только тогда, когда они попадают в клетку (i, j), подлежащую заполнению. Если в очеред­ную клетку таблицы (i, j) требуется поставить перевозку, а i-й поставщик или j-й потребитель имеет нулевые запасы или запросы, то в клетку ставится

перевозка, равная нулю (базисный нуль), и после этого, как обыч­но, исключается из рассмотрения соответствующий поставщик или по­требитель.

Таким образом, в таблицу заносят только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

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

Теорема: Решение транспортной задачи, построенное методом северо-западного угла, является опорным.

19. Оптимизация начального опорного решения транспортной ЗЛП методом потенциалов.

Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наибо­лее трудоемкую часть вычислений - нахождение оценок свободных клеток.

Теорема (признак оптимальности опорного решения).

Если допустимое решение X = (x_ij), i = 1, 2,..., m, j = 1, 2,..., nтранспортной задачи является оптимальным, то существуют потенциалы (числа) по­ставщиков u_i, i = 1, 2,..., m и потребителей v_j, j = 1, 2,..., nудовлет­воряющие следующим условиям:

u_i + v_j = c_ij при x_ij > 0 (1)

u_i + v_j ≤ c_ij при x_ij = 0 (2)

Группа равенств (1) u_i + v_j = c_ij при x_ij > 0 используется как система уравнений для нахождения потенциалов. Не­трудно видеть, что эта система могла иметь несколько другой вид, на­пример -u_i + v_j = c_ijили u_i - v_j = c_ij,если перед тем, как записать двойственную задачу, все уравнения одной из групп уравнений исход­ной задачи умножить на (-1).

Данная система уравнений имеет m+ n неизвестных u_i, i = 1, 2,..., т, и v_j, j = 1, 2,..., n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m + m - 1. Так как число неизвестных системы на единицу больше числа уравне­ний, то одной из них можно задать значение произвольно, а остальные найти из системы.

Группа неравенств (2) u_i + v_j ≤ c_ij при x_ij = 0 используется для проверки оптимальности опорного решения. Эти неравенства удобно записать в виде

Δ_ij = u_i + v_j – c_ij ≤ 0 при x_ij = 0 (3)

Числа Δ_ij называются оценкамисвободных клеток таблицы или век­торов-условий транспортной задачи, не входящих в базис опорного ре­шения. В этом случае признак оптимальности можно сформулировать так же, как в симплексном методе (для задачи на минимум): опорное решениеявляется оптимальным, если для всех векторов-условий (клеток таблицы) оценки неположительные.

Оценки для свободных клеток транспортной таблицы используются для улучшения опорного решения. С этой целью находят клетку (I, k)таблицы, соответствующую max {Δ_ij} = Δ_Ik. Если Δ_Ik ≤ 0, то решение оптимальное. Если же Δ_Ik > 0, то для соответствующей клетки (I, k) строят цикл и улучшают решение, перераспределяя груз Ө = {x_ij} по этому циклу.

Алгоритм решения транспортной задачи методом потенциалов следующий.

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

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

3 Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений + = при >0. Для того чтобы

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

= - при >0,

если известен потенциал , и

= - при >0,

если известен потенциал .

4 Проверяют, выполняется ли условие оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам = + - и те оценки, которые больше нуля, записывают в левые нижние углы клеток. Если для всех свободных клеток 0, то вычисляют значение целевой функции, и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, то опорное решение не является оптимальным.

5 Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка max{ }= . Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину Ө = {x_ij}. Клетка со знаком «-», в которой достигается Ө = {x_ij}, остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1.

20. Нелинейное программирование.

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

Общая задача нелинейного программирования (ОЗНП) оп­ределяется как задача нахождения максимума (или минимума) целевой функции f(x_{, х₂,..., х_п) на множестве D, определяемом системой ограничений

(2.1)

где хотя бы одна из функций f или g_i является нелинейной.

По аналогии с линейным программированием ЗНП однознач­но определяется парой (D,f) и кратко может быть записана в следующем виде

(2.2)

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

Как и в ЗЛП, вектор называется допус­тимым планом, а если для любого xÎD выполняется неравен­ство , то х^* называют оптимальным планом. В этом случае х^* является точкой глобального максимума.

С точки зрения экономической интерпретации f(x) может рассматриваться как доход, который получает фирма (предпри­ятие) при плане выпуска х, а как технологические ог­раничения на возможности выпуска продукции. В данном слу­чае они являются обобщением ресурсных ограничений в ЗЛП

Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:

или запись условий дискретности множеств:

Набор ограничений, определяющих множество D, при необ­ходимости всегда можно свести либо к системе, состоящей из одних неравенств:

либо, добавив фиктивные переменные у, к системе уравнений:

Перечислим свойства ЗИП, которые существенно усложня­ют процесс их решения по сравнению с задачами линейного про­граммирования:

1. Множество допустимых планов D может иметь очень сложную структуру (например, быть невыпуклым или несвяз­ным).

2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще гово­ря, будет не совпадать ни с одним из локальных экстремумов).

3. Целевая функция f может быть недифференцируемой, что затрудняет применение классических методов математическо­го анализа.

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

Решение задач условной оптимизации методом Лагранжа. Одним из наиболее общих подходов к решению за­дачи поиска экстремума (локального максимума или миниму­ма) функции при наличии связующих ограничений на ее переменные (или, как еще говорят, задачи условной оптимизации) является метод Лагранжа. Многим читателям он должен быть известен из курса дифференциального исчисления. Идея данного метода состоит в сведении задачи поиска условного эк­стремума целевой функции

(2.3)

на множестве допустимых значения D, описываемом системой уравнений

(2.4)

к задаче безусловной оптимизации функции

Ф(x,u) = f(x₁,x₂,...,x_n)+u_lg_l(xi,x₂,...,x_n)+...+u_ng_m(x_l,x₂,...,x_n), (2.5)

где — вектор дополнительных переменных, называе­мых множителями Лагранжа. Функцию Ф(х,и), где , , называют функцией Лагранжа. В случае диф­ференцируемое™ функций f и g_i справедлива теорема, опре­деляющая необходимое условие существования точки услов­ного экстремума в задаче (2.3)-(2.4). Поскольку она непосредственно относится к предмету математического ана­лиза, приведем ее без доказательства.

Теорема 2.1. Если х^* является точкой условного эк­стремума функции (2.3) при ограничениях (2.4) и ранг матрицы первых частных производных функций

равен т, то существуют такие , не равные одновременно нулю, при которых

(2.6)

Из теоремы (2.1) вытекает метод поиска условного экстре­мума, получивший название метода множителей Лагранжа, или просто метода Лагранжа. Он состоит из следующих этапов.

1. Составление функции Лагранжа Ф(х,и).

2. Нахождение частных производных

и

3. Решение системы уравнений

(2.7)

относительно переменных х и и.

4. Исследование точек, удовлетворяющих системе (2.7), на максимум (минимум) с помощью достаточного признака экст­ремума.

Присутствие последнего (четвертого) этапа объясняется тем, что теорема (2.1) дает необходимое, но не достаточное ус­ловие экстремума. Положение дел с достаточными признаками условного экстремума обстоит гораздо сложнее. Вообще гово­ря, они существуют, но справедливы для гораздо более частных ситуаций (при весьма жестких предпосылках относительно функций f и g_i) и, как правило, трудноприменимы на практике. Еще раз подчеркнем, что основное практическое значение метода Лагранжа заключается в том, что он позволяет перей­ти от условной оптимизации к безусловной и, соответствен­но, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы урав­нений (2.7), к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума (2.3)-(2.4). Методы, подразумевающие такое решение, называются непря­мыми. Они могут быть применены для весьма узкого класса за­дач, для которых удается получить линейную или сводящуюся к линейной систему уравнений (2.7). Их применение объясняет­ся необходимостью получить решение экстремальной задачи в аналитической форме (допустим, для тех или иных теоретиче­ских выкладок). При решении конкретных практических задач обычно используются прямые методы, основанные на итера­тивных процессах вычисления и сравнения значений оптимизи­руемых функций.

Градиентные методы решения задач безуслов­ной оптимизации. Ведущее место среди прямых методов ре­шения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационар­ных точек дифференцируемой функции. Напомним, что стаци­онарной называется точка, в которой и которая в со­ответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.

Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х⁽¹⁾ перемещаться в направлении вектора , то функция f будет возрастать, по крайней мере, в некоторой окрестности х⁽¹⁾. Следовательно, для точки , , лежащей в такой окрестности, справедливо неравенство . Продолжая этот про­цесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1).

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

(2.8)

задающей последовательность точек, стремящихся к точке мак­симума.

В зависимости от способа ее решения различают различные варианты градиентного метода. Остановимся на наиболее изве­стных из них.