1 разработка общей математической модели

1 РАЗРАБОТКА ОБЩЕЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

1.1 Описание метода решения задач

1.1.1 Общая характеристика предприятия

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

Классическая постановка транспортной задачи. Пусть имеется m поставщиков А₁, А₂,…, А_i,..., А_m однородного а₁, а₂,…,а_i,…, а_m единиц и n потребителей В₁, В₂,…,В_j,…,В_n этого груза, потребность которых составляет соответственно b₁, b₂,…,b_j,…,b_n единиц.

Известны стоимости перевозок единицы груза от i-го поставщика к j-му потребителю —

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

Замечание. Перевозимый груз должен быть однородным, например, песок, уголь, лес, кирпичи, металл и т.п. Единицы измерения количества груза могут быть различными (т, м³, шт., л. и т.п.). Предполагается, что стоимость перевозимого груза пропорциональна его количеству. В качестве поставщиков груза могут выступать предприятия, базы, склады, а в качестве потребителей — предприятия, магазины, строительные объекты и т.п.

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

Чтобы лучше представить условие задачи, сведем исходные данные в таблицу 18. Строка таблицы соответствует поставщику, а столбец — потребителю.

c₁₁

c₂₂

c_i2

c_m2

c_mj

c_ij

c_2j

c_1j

c_2n

c_in

c_mn

c_1n

c₂₁

c_i1

c_m1

c₁₂

Таблица 18

A1	х11	х12	...	х1j	...	х1n
a2	х21	х22	...	х2j	...	х2n
...	...	...	...	...	...	...
ai	хi1	хi2	...	хij	...	хin
...	...	...	...	...	...	...
Am	хm1	хm2	...	хmj	...	хmn

Модели транспортной задачи. При постановке конкретных задач перевозки грузов может возникнуть одна из трёх ситуаций:

1) количество груза у всех поставщиков равно потребности в данном грузе всех потребителей :

или

(4.18)

2) количество груза у всех поставщиков больше потребности в данном грузе всех потребителей :

или

(4.19)

3) количество груза у всех поставщиков меньше потребности в данном грузе всех потребителей

или

(4.20)

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

Рассмотрим ситуацию (1), которой отвечает соотношение (4.18). Объектом исследования в транспортной задаче является планирование перевозок грузов. Цель исследования — составление плана перевозки грузов, обеспечивающего минимальные транспортные расходы. Критерий задачи — минимальные транспортные расходы. Отразим критерий задачи в целевой функции. Стоимость перевозки единицы груза от i -го поставщика к j -му потребителю составляет с_ij, а груза перевозится х_ij единиц. Следовательно, стоимость перевозки всего груза от i -го поставщика к j -му потребителю будет равна величине c_ijx_ij. Учитывая, что суммарная стоимость перевозки грузов от всех поставщиков ко всем потребителям должна быть минимальной, целевая функция транспортной задачи будет иметь вид:

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

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

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

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

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

(4.21)

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

Рассмотрим ситуацию (2), которой отвечает соотношение (4.19). В данной ситуации у всех поставщиков имеется больше груза, чем необходимо потребителям. Поэтому часть груза у поставщиков останется, а потребители получат весь необходимый груз. Поскольку у части поставщиков груз останется, ограничения первой группы будут иметь вид «≤», а модель транспортной задачи примет следующий вид:

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

Модель (4.21) называется закрытой моделью транспортной задачи, а соответствующая ей задача — сбалансированной. Модели, отвечающие соотношениям (4.19) и (4.20), называются открытыми. Количество переменных в модели равно (т×п), а количество ограничений — (m+п).

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

В ситуации (2), когда вводится фиктивный потребитель B_n+1 с потребностью b_n+1= . К левой части каждого ограничения первой группы прибавляется соответственно неотрицательная переменная X_i,n+1 (i =1, m), во вторую группу ограничений добавляется ограничение, соответствующее фиктивному потребителю B_n+1:

.

В таблицу исходных данных задачи (таблица 18) добавляется столбец.

В ситуации (3), когда , вводится фиктивный поставщик А _т+1 с наличием груза в количестве а_n+1= .

К левой части каждого ограничения второй группы прибавляется соответственно неотрицательная переменная X_m+1j (j =1, n), в первую группу ограничений добавляется ограничение, соответствующее фиктивному поставщику А _т+1:

.

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

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

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

Методы построения исходного плана. Для решения исходные данные транспортной задачи (4.21) сводятся в таблицу (таблица 18). Из условия (4.18) следует, что любое ограничение транспортной задачи является линейной комбинацией остальных. Следовательно, система ограничений транспортной задачи линейно зависима и содержит только m+n– 1 независимых уравнений. Поэтому исходный допустимый невырожденный базисный план должен иметь m+n– 1 базисную переменную и его легко можно получить непосредственно из данных таблицы. Все остальные переменные — небазисные и их значения равны нулю, которые в таблице можно не отражать, т.е. клетку, соответствующую небазисной переменной, оставлять незаполненной.

Метод северо-западного угла. Определение значений x_ij начинается с левой верхней клетки таблицы. Находим значение из x₁₁ соотношения

Возможны три варианта:

1. Если a₁ < b₁, то x₁₁ = a₁, строка i =1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b₁ уменьшается на величину a₁;

2. Если a₁ > b₁, то x₁₁ = b₁, столбец j =1 исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика a₁ уменьшается на величину b₁;

3. Если a₁ = b₁, то x₁₁ = a₁ = b₁, строка i =1 и столбец j =1 исключается из дальнейшего рассмотрения. Данный вариант приводит к вырождению исходного плана.

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

После завершения описанного процесса необходимо провести проверку полученного плана на врожденность. Если количество заполненных клеток равно m+n–1, то план является невырожденными, в противном случае — вырожденным.

Если план вырожденный, т.е. количество заполненных клеток оказалось меньше m+n– 1, то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями, чтобы общее количество заполоненных клеток стало равным m+n– 1. Однако при расстановке нулей необходимо помнить, что в таблице не должно быть ни одного прямоугольника, все вершины которого являются заполненными клетками. Например, переменные х₁₁, х₁₂, х₂₁, х₂₂ или х₁₁, х_1n, х₂₁, х_2n (таблица 18) не могут быть одновременно базисными.

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

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

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

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

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

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

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

1. Каждому поставщику A_i поставим в соответствие некоторое число u_i, называемое потенциалом A_i, а каждому потребителю B_j (т.е. каждому столбцу)поставим в соответствие некоторое число, называемое потенциалом B_j.

Для каждой заполненной клетки, т.е. для каждой базисной переменной, строится соотношение

(4.22)

Полученная система должна содержать m+n–1 уравнений с m+n неизвестными. Как известно, такая система имеет множество решений, и любое из них будет содержать искомые потенциалы. Чтобы найти одно из решений, значение одного потенциала в системе задается произвольно. Обычно считают, что u₁ =0, и находят значения остальных потенциалов. Значения потенциалов записывают справа и снизу таблицы против соответствующих строк и столбцов.

2. Для каждой незаполненной клетки, т.е. для каждой небазисной переменной, рассчитываются так называемые косвенные тарифы (с′_ij) по формуле

(4.23)

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

3. Проверим полученный план на оптимальность по критерию оптимальности плана транспортной задачи. Если для каждой незаполненной клетки выполняется условие

(4.24)

то план является оптимальным. В противном случае полученный план не оптимальный, и необходимо переходить к новому базисному плану путем перемещения перевозки в клетку, отвечающей условию max . Если таких клеток более одной, то необходимо перемещать перевозку в первую по порядку. Выбранная клетка помечается в таблице. Переменная, стоящая в этой клетке, вводится в базис.

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

5. В каждой клетке цикла, начиная с незаполненной, проставляются поочередно знаки «+» и «–». В клетках со знаком «–» выбирается минимальная величина. Новый базисный план получается путем сложения выбранной величины с величинами, стоящими в клетках цикла со знаком «+», и вычитания этой величины из величин, стоящих в клетках со знаком «–».

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

Значения переменных, включенных в цикл, после описанной корректировки переносятся в новую таблицу. Все остальные переменные записываются в новую таблицу без изменений.

Осуществляется переход к пункту один алгоритма.

1.1.2 Общая математическая модель

У трех поставщиков А₁, А₂, А₃ имеются однородные грузы соответственно в количествах 335, 2701 и 195 условных единиц, которые нужно распределить между потребителями В₁, В₂, В₃, В₄ и В₅ соответственно в количествах 95, 120, 205, 175 и 205 условных единиц.

Составить такой план перевозок, чтобы стоимость их была бы наименьшей, если тарифы С_ij на перевозку условной единицы груза даны в матрице:

Для получения первого опорного плана заполняем таблицу 19, начиная с клетки А₁В₁, расположенной в левом верхнем углу в направлении клетки А₃В₅ (метод северно-западного угла или метод наименьшего элемента в матрице).

Таблица 19

Пункт назначения Пункт отправления	В1	В2	В3	В4	В5	Наличие грузов у отправителей
+ + - + - - А1
А2
А3
Потребность в грузах у получателей

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

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

L₁ =11×95+15×120+12×120+14×85+10×175+11×10+17+195=10650 (денежных единиц).

Вычисляем оценки матрицы косвенных стоимостей (тарифов) U_i и V_j, используя тарифы только в занятых клетках.

u₁ + v₁ =11 u₁ =0

u₁ + v₂ =15 v₁ =11

u₁ + v₃ =12 v₂ =15

u₂ + v₃ =14 v₃ =12

u₂ + v₄ =10 u₂ =2

u₂ + v₅ =11 v₁ =8

u₃ + v₅ =17 v₅ =9

u₃ =8

Затем находим оценки Z_ij для свободных клеток по формуле:

Z_ij =(u_i + v_j) – c_ij

Z₁₄ =0+8–18<0

Z₁₅ =0+9–19<0

Z₂₁ =2+11–8=5>0

Z₂₂ =2+15–12=5>0 Выбираем клетку с наибольшим

Z₃₁ =8+11–10=9>0 положительным Z_ij

Z₃₂ =8+15–15=8>0 Здесь это Z₃₁ =9

Z₃₃ =8+12–18=2>0

Z₃₄ =8+8–13=3>0.

Строим для клетки Z₃₁ — прямоугольный контур с вершиной Z₃₁, а остальные вершины должны быть в занятых клетках. Получим контур А₃В₁; А₁В₁, А₁В₃, А₂В₃, А₂В₅, А₃В₅.

Наименьшее из отрицательных вершин q — это 85. Сделаем перераспределение (таблица 20).

Таблица 20

Получатели Отправи тели	Vj Ui	B1	B2	B3	B4	B5	Наличие грузов
V1=11	V2=15	V3=12	V4=8	V5=9
А1	U1=0	+ - - +
А2	U2=2
А3	U3=8
Потребность в грузах у получателя

Повторяем процесс.

Для занятых клеток:

u₁ + v₁ =11 u₁ =0

u₁ + v₂ =15 v₁ =11

u₁ + v₃ =12 v₂ =15

u₂ + v₄ =10 v₃ =12

u₂ + v₅ =11 u₃ =–1

u₃ + v₁ =10 v₅ =18

u₃ + v₅ =17 u₂ =–7

v₄ =17

Оценки для свободных клеток:

Z₁₄ =0+17–18=–1<0

Z₁₅ =0+18–19=–1<0

Z₂₁ =–7+11–8=–4<0 Т.к. имеется клетка с

Z₂₂ =–7+15–12<0 положительным Z_ij = Z₃₄ >0,

Z₂₃ =–7+12–14<0 то план не является оптимальным

Z₃₂ =–1+15–15<0

Z₃₃ =–1+12–18<0

Z₃₄ =–1+17–13=3>0.

Для клетки А₃В₄ строим прямоугольный контур А₃В₄, А₂В₄, А₂В₅, А₃В₅. Из отрицательных вершин наименьшее число 110. Перемещаем его в клетку А₃В₄ и делаем перераспределение.

Таблица 21

Получатель Отправитель	B1	B2	B3	B4	B5	Наличие грузов
V1=11	V2=15	V3=12	V4=14	V5=15
А1	U1=0
А2	U2=–4
А3	U3=–1
Потребность в грузах у получателя

L =11×10+15×120+12×205+10×65+11×205+10×85+13×110=9555 (денежных единиц).

Проверяем полученное решение на оптимальность

Для занятых клеток:

u₁ + v₁ =11 u₁ =0

u₁ + v₂ =15 v₁ =11

u₁ + v₃ =12 v₂ =15

u₂ + v₄ =10 v₃ =12

u₂ + v₅ =11 u₃ =–1

u₃ + v₁ =10 v₄ =17

u₃ + v₅ =17 v₂ =–7

u₅ =18

Оценки свободных клеток:

Z₁₄ =0+14–18<0

Z₁₅ =0+15–19<0

Z₂₁ =–4+11–8<0

Z₂₂ =–4+15–12<0

Z₂₃ =–4+12–14<0

Z₃₂ =–1+15–15<0

Z₃₃ =–1+12–18<0

Z₃₅ =–1+15–17<0.

Все Z_ij <0, следовательно план оптимальный.

Тогда, L (x)_min=9555 денежных единиц.

Дата добавления: 2015-11-04