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

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

Постановка задачи А. Пусть имеется 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	Запасы песка ai
Карьер 1	10	15	20	350
Карьер 2	15	15	10	100
Карьер 3	20	10	15	250
Карьер 4	10	10	25	400
Потребности в песке bj	500	500	100

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

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

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





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

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

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

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

F(X)=10*x₁₁+15*x₁₂+20*x₁₃+15*x₂₁+15*x₂₂+10*x₂₃ +20*x₃₁+

+10*x₃₂+15*x₃₃+10*x₄₁+10*x₄₂+25*x₄₃ → min(1´)

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

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

(2´)

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

(3´)



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

x₁₁≥0, x₁₂≥0, x₁₃≥0, x₂₁≥0, x₂₂≥0, x₂₃≥0, x₃₁≥0, x₃₂≥0, x₃₃≥0, x₄₁≥0, x₄₂≥0, x₄₃≥0,(4´)

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

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

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

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

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

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

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

потребности в песке b_j и количество доставленного песка на каждую.

стройку, используя встроенную функцию MSExcel – СУММ().

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

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

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

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

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

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

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

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

Список литературы.

1. Динамическое программирование. Шипилов С.А.

2. Методы условной оптимизации: Рек. к выполнению лаб. и практ.работ / Сост.: Шипилов С.А: НФИ КемГУ.- 2-е изд.перераб.- Новокузнецк. 2002.-48 с.Карасев А.И.

3. Математические методы и модели в планировании: Учебное пособие для экономических вузов. М.: Экономика, 1987.Мишин В.И. Исследование систем управления.- М :2003.

4. Минеева Н.В., Мотышина М.С метод линейного и не линейного программирования – Н. 2003.

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