Построение математической модели

Обозначим через x_ij количество единиц сырья, перевозимого из i-го пункта его получения на j-е предприятие. То есть, обозначим через х₁₁ количество единиц продукции, поставляемой 1-м предприятием 1-у потребителю, через х₁₂ – количество единиц продукции, поставляемой этим предприятием второму потребителю и так далее до тех пор, пока вся продукция не будет вывезена, то есть пока не получим равенство х₁₁+х₁₂+х₁₃+х₁₄+х₁₅=100. Аналогично составляем равенства для оставшихся предприятий. После этого по аналогии составляем равенства для потребителей. Так для первого потребителя будет х₁₁+х₂₁+х₃₁+х₄₁=200 равенство и т.д. В результате видим, что условия доставки необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств (ограничений):

При данном плане общая стоимость перевозок составит наименьшее значение линейной функции:

Z=10х₁₁+7х₁₂+4х₁₃+1х₁₄+4х₁₅+2х₂₁+7х₂₂+10х₂₃+6х₂₄+11х₂₅+8х₃₁+5х₃₂+3х₃₃+2х₃₄+2х₃₅+11х₄₁+8х₄₂+12х₄₃+16х₄₄+13х₄₅.

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

Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

Методы построения первоначального опорного плана

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

Рассмотрим систему ограничений (4.2) транспортной задачи. Она содержит m·n неизвестных и m+n уравнений. Если сложить почленно уравнения подсистемы (4.2), то получим два одинаковых уравнения. В таблице 4.1 такое сложение равнозначно соответственно почленному сложению столбцов и почленному сложению строк.

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

Таким образом, если каким-либо способом получен невырожденный опорный план транспортной задачи, то в матрице (х_ij , i= 1, 2, ..., m; j =1, 2,..., n) значений его компонент (таблица 4.1) положительными являются только m+n-1, остальные равны нулю.

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

Циклом называется набор клеток вида (i₁j₁)(i₁j₂)(j₁i₂)…(j₁i_m), в котором две и только две соседние клетки расположены в одном столбце или одной строке таблицы, причем последняя клетка находится в той же строке или столбце, что и первая. Построение циклов начинают с какой-либо занятой клетки и переходят по столбцу (строке) к другой занятой клетке, в которой делают поворот под прямым углом и движутся по строке (столбцу) к следующей занятой клетке и так далее, пытаясь возвратиться к первоначальной клетке. Если такой возврат возможен, то получен цикл и план не является опорным. Клетки, в которых происходит поворот под прямым углом, определяют вершины цикла. В противном случае план является опорным.

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

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

Определение опорного плана методом северо-западного угла

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

Таблица 4.2 – Условие задачи

Поставщики	Потребители	Запасы, ai
В1	В2	В3	В4	В5
A1
A2
A3
А4
Потребности, bj

Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя B₁ за счет запаса поставщика A₁. Для этого сравниваем а₁=100 с b₁=200, a₁< b₁, меньший из объемов, т. е. =100ед. записываем в левый нижний угол клетки A₁B₁
(таблица 4.3).

Таблица 4.3 – Построение опорного плана методом северо-западного угла

Поставщики	Потребители	Запасы, ai
В1	В2	В3	В4	В5
A1		–	–	–	–
A2			–	–	–
A3	–				–
А4	–	–	–
Потребности, bj

 

Запасы первого поставщика полностью израсходованы, поэтому остальные клетки первой строки прочеркиваем. Потребности B₁ остались неудовлетворенными на 200 – 100 = 100 ед. Сравниваем этот остаток с запасами поставщика А₂, т.к. 100 < 250, то 100 ед. записываем в клетку A₂B₁, чем полностью удовлетворяем потребности потребителя B₁, оставшиеся клетки в первом столбце прочеркиваем.

У поставщика A₂ осталось 150 ед. груза. Удовлетворяем потребителя B₂ за счет оставшегося у поставщика A₂ груза. Для этого сравниваем этот остаток с потребностями потребителя B₂: 150< 200, записываем 150 ед. в клетку A₂B₂ и, т.к. запасы A₂ полностью израсходованы, прочеркиваем остальные клетки второй строки. Потребности B₂ остались неудовлетворенными на 50ед. Удовлетворяем их за счет поставщика А₃ и переходим к удовлетворению B₃ за счет остатка, имеющегося у поставщика А₃, и т.д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного план заканчивается.

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

Проверим, является ли план, построенный в таблице 4.3, опорным. Видим, что, начиная движение от занятой клетки A₁B₁, вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым клеткам, невозможно. Следовательно, план является опорным.

В то же время план является невырожденным, т.к. он содержит точно m+n-1=4+5-1=8 занятых клеток. Если же занятых клеток будет меньше, чем m+n-1, то следует ввести в любую незанятую клетку объем груза, равного формальному нулю, то есть вырожденный план привести к невырожденному.

Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же клетках:

Z=100·10+100·2+150·7+50·5+100·3+50·2+50·16+250·13=6950(ед. стоимости).

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

Определение опорного плана методом минимальной стоимости

Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то план будет значительно ближе к оптимальному.

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

Составим с помощью этого метода опорный план уже рассмотренной задачи и запишем ее условие в таблицу 4.4.

Таблица 4.4 – Определение опорного плана методом минимальной стоимости

Поставщики	Потребители	Запасы ai
В1	В2	В3	В4	В5
A1	–	–	–		–
A2			–	–	–
A3	–	–	–	–
А4	–
Потреб. bj

 

Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клетке А₁В₄), так как а₁=b₄, 100 ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке A₂B₁ и в клетке A₃B₅. Заполняем любую из них, например, A₂B₁. Имеем 200< 250, следовательно, записываем в нее 200 и исключаем из рассмотрения столбец B₁. В клетку A₃B₅ записываем 200 ед. и исключаем из рассмотрения строку A₃. В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, потребности удовлетворены. В результате получен план Х=(x₁₄=100; x₂₁=200; x₂₂=50; x₃₅=200; x₄₂=150; x₄₃=100; x₄₅=50), остальные значения переменных равны нулю. План не содержит циклов и состоит из семи положительных перевозок, следовательно, является опорным планом. Определим его стоимость:

Z= 100·1+200·2+50·7+200·2+ 150·8+ 100·12++50·13=4300 (ед.).

Стоимость плана перевозок значительно меньше, следовательно, он ближе к оптимальному.

Определение опорного плана методом двойного предпочтения

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

В каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку VV. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

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

Таблица 4.5 – Определение клеток с минимальной стоимостью

Поставщики, Ai	Потребители, В j	Запасы
В 1	В 2	В 3	В 4	В 5	ai
A1				1 VV
A2	2 VV
A3		5 V	3 V	2 V	2 VV
А4		8 V
Потребности bj

Затем сначала заполняем клетки A₁B₄, A₂B₁, A₃B₅, потом клетку A₄B₅. В оставшейся части таблицы последовательно заполняем клетки по минимальной стоимости A₂B₃, A₄B₃, A₄B₅ (таблица 4.6).

Таблица 4.6 – Определение опорного плана методом двойного предпочтения

Поставщики, Ai	Потребители, В j	Запасы ai
В 1	В 2	В 3	В 4	В 5
A1	–	–	–	1 VV	–
A2	2 VV	–		–	–
A3	–	5 V –	3 V –	2 V –	2 VV
А4	–	8 V		–
Потребности bj

 

План, полученный в таблице 4.6, является опорным планом. Найдем его стоимость:

Z= 100·1+200·2 +50·10+200·2+200·8+50·12+50·13 = 4250 (ед.).

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

С помощью рассмотренных методов построения первоначального плана можно получить опорный план. Оптимальный же план транспортной задачи легко находить, используя разработанные в настоящее время пакеты прикладных программ. В частности, для решения транспортной задачи можно использовать инструмент «Поиск решения» табличного процессора Excel. Рассмотрим применение Excel для решения транспортной задачи.

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. II. Алгоритм процесса кибернетического моделирования.
2. III. 1.-ПОСТРОЕНИЕ ТЕХНИКИ ПЛАВАНИЯ С УЧЕТОМ ОСНОВНЫХ ЗАКОНОВ ДИНАМИКИ
3. III. 3. ПОСТРОЕНИЕ ТЕХНИКИ ПЛАВАНИЯ С УЧЕТОМ АНАТОМИЧЕСКИХ ОСОБЕННОСТЕЙ СТРОЕНИЯ ТЕЛА ЧЕЛОВЕКА
4. XI. ПОСТРОЕНИЕ И ПРОЦЕСС ПСИХОДРАМЫ. КОНСТИТУЕНТЫ (ИНСТРУМЕНТЫ); ФАЗЫ И ФОРМЫ
5. Абстрактные модели защиты информации
6. Аддиктивное поведение: концепции и модели
7. Альтернативные модели поведения фирмы
8. Билет 27. МОДЕЛИРОВАНИЕ ПРОЦЕССА ПЕРЕВОДА. МОДЕЛИ ПРОЦЕССА ПЕРЕВОДА: ДЕНОТАТИВНО-СИТУАТИВНАЯ, ТРАНСФОРМАЦИОННАЯ МОДЕЛЬ, СЕМАНТИЧЕСКАЯ МОДЕЛЬ, ТРЕХФАЗНАЯ МОДЕЛЬ О.КАДЕ, ИНТЕГРАТИВНАЯ МОДЕЛЬ И ДР.
9. Блоки модуля методологических оснований концептуальной модели педагогической системы вузовского формирования функциональных компетентностей будущих учителей физической культуры
10. В связи с этим основными проблемами, связанными с реализацией модели 4С, являются следующие.
11. В то же время, для динамического подхода было характерным построение вертикальных связей, объединяющих первичное с вторичным (функциональная связь) и высшее с низшим (иерархическая связь).
12. Вина при формальной модели преступления