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

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

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

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

Постановка задачи А. Пусть имеется m источников финансирования А1, А2, ..., Аm и n периодов финансирования В1, B2, ..., Вn. Известны затраты, связанные с выделением единицы денежных ресурсов Сij из i-го источника в j-ом периоде, а также объемы финансирования из каждого i-го источника в течение всего времени - аi. Известны суммарные объемы финансирования из всех источников в каждый j-й период времени - bj. Требуется определить объемы финансирования xij из i-го источника в j-ом периоде, чтобы:

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

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

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

Постановка задачи В. Пусть имеется n пунктов производства (хранения) А1,А2,...,Аn, некоторого однородного ресурса, запасы которого составляют a1,a2,...,an условных единиц соответственно. Кроме этого, имеется m пунктов потребления В1,В2,...,Вm данного ресурса с потребностями b1,b2,...,bm условных единиц. Кроме этого, известна матрица перевозок С, элементы которой cij - затраты на перемещение единицы ресурса из Ai -пункта хранения в Bj - пункт потребления.

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

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

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

,

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

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

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

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

Обозначим через xij количество ресурса, перемещаемого из Ai пункта хранения в Bj пункт потребления. Таким образом, элементы xij образуют матрицу перевозок X nхm.

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

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

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

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

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

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

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

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

1. Идентифицируйте свою работу, переименовав Лист1 в Титульный лист и записав номер лабораторной работы, ее название, кто выполнил и проверил.

2. На следующем листе, с именем Сбалансированная ТЗ, создайте таблицу для ввода условий задачи и введите исходные данные.

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

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

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

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

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

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

8. Сохраните и проанализируйте полученное решение. Сделайте выводы.

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

1. Идентифицируйте лабораторную работу, набрав ее номер, название, кто выполнил и проверил.

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

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

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

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

MathCad-документ решения транспортной задачи представлен ниже.