IX Международная студенческая научная конференция Студенческий научный форум - 2017

Цель работы: овладеть навыками составления математической модели сбалансированной транспортной задачи и ее решение в среде ЭТ MS Excel с помощью надстройки «Поиск решения» и в среде пакета MathCad c помощью блока Given … Maximize (Given … Minimize).

Краткая теория

Транспортная задача может быть сформулирована различными способами.

Постановка задачи А. Пусть имеется m источников финансирования А₁, А₂, ..., А_m и n периодов финансирования В₁, B₂, ..., Вn. Известны затраты, связанные с выделением единицы денежных ресурсов С_ij из i-го источника в j-ом периоде, а также объемы финансирования из каждого i-го источника в течение всего времени – а_i. Известны суммарные объемы финансирования из всех источников в каждый j-й период времени – b_j. Требуется определить объемы финансирования x_ij из i-го источника в j-ом периоде, чтобы:

1. Ресурсы всех источников были реализованы.

2. Обеспечить финансирование в полном объеме в каждом периоде.

3. Достигнуть экстремума выбранного критерия оптимизации.

Постановка задачи В. Пусть имеется n пунктов производства (хранения) А₁,А₂,…,Аn, некоторого однородного ресурса, запасы которого составляют a₁,a₂,…,an условных единиц соответственно. Кроме этого, имеется m пунктов потребления В₁,В₂,…,В_m данного ресурса с потребностями b₁,b₂,…,b_m условных единиц. Кроме этого, известна матрица перевозок С, элементы которой c_ij – затраты на перемещение единицы ресурса из A_i –пункта хранения в B_j − пункт потребления.

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

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

Bj Ai	B1	B2	…	Bm	Запасы ai
А1 А2 … Аn	c11 c21 … cn1	c12 c22 … cn2	… … … …	c1m c2m … cnm	a1 a2 … an
Потребности bj	b1	b2	…	Bm

Различают закрытую (сбалансированную) и открытую (несбалансированную) транспортную задачу. При этом, если

,

то задача называется сбалансированной, в противном случае – несбалансированной.

Для решения сформулированной задачи составим ее математическую модель.

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

1. Определим неизвестные и их количество.

Обозначим через x_ij количество ресурса, перемещаемого из A_i пункта хранения в B_j пункт потребления. Таким образом, элементы x_ijобразуют матрицу перевозок Xn_хm.

2. Запишем целевую функцию − суммарные затраты на перевозку ресурсов, которую необходимо минимизировать

3. Сформулируем ограничения рассматриваемой задачи.

3.1. Ресурсы из всех пунктов отправления должны быть вывезены. Это ограничение можно записать в виде:

Т.е. сумма элементов каждой строки матрицы перевозок Х равна запасу ресурса в данном пункте хранения.

3.2. Необходимо удовлетворить запросы каждого потребителя в данном ресурсе. Это ограничение можно записать в виде:

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

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

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

Таблица 1. Данные к сбалансированной транспортной задаче.

карьер стройка	стройка 1	стройка 2	стройка 3	стройка 4	Запас ai
карьер 1	10	15	20	20	350
карьер 2	15	15	10	20	200
карьер 3	20	10	15	25	250
карьер 4	10	10	25	25	400
Потребность bj	500	500	100	100

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

Для решения сформулированной задачи составим ее математическую модель.

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

Математическая модель сбалансированной транспортной задачи. Для построения математической модели задачи:

1. Определим неизвестные и их количество.

Обозначим через x_ij количество песка (м³), перемещаемого из i-го карьера наj-ю стройку. Таким образом, элементы x_ijобразуют матрицу перевозок X_4х4.

2. Запишем целевую функцию.

3. Сформулируем ограничения рассматриваемой задачи.

3.1. Песок из всех карьеров должен быть вывезен. Это ограничение можно записать в виде:

(2´)

3.2. Необходимо удовлетворить потребности каждой стройки в песке. Это ограничение можно записать так:

(3´)

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

. (4´)

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

Решение задачи в среде ЭТ MSExcel. Для решения задачи с помощью надстройки Поиск решения в среде ЭТ MS Excel необходимо:

1. Создайте таблицу для ввода условий задачи и введите исходные данные.

2. Запишите матрицу затрат на перевозки С_4х4.

3. Составьте матрицу перевозок Х_4х4 с пока нулевыми значениями x_ij.

4. Дополните матрицу перевозок двумя столбцами справа и двумя строками снизу, в которые записать:

• запасы песка а_i и количество вывезенного ресурса из каждого карьера, используя встроенную функцию MS Excel – СУММ();

• потребности в песке b_j и количество доставленного песка на каждую стройку, используя встроенную функцию MS Excel – СУММ().

5. Проверить задачу на сбалансированность и записать целевую функцию F(X), используя встроенную функцию MS Excel – СУММПРОИЗВ().

6. Вызвать диалоговое окно надстройки «Поиск решения» и выполнить необходимые установки.

7. Сохраните и проанализируйте полученное решение.

Решение задачи с помощью пакета MathCadосуществляется аналогично. Для решения задачи в среде пакета MathCad:

1. Определите начальные значения переменных и вектор-столбцы переменных Х и затрат на перевозку С.

2. Определите целевую функцию F(X).

3. Введите служебное слово Given и, после него, систему ограничений и граничных условий.

4. Найдите оптимальное решение с помощью функции Minimize и значение целевой функции.

Код для цитирования: Скопировать