СБАЛАНСИРОВАННАЯ ТРАНСПОРТНАЯ ЗАДАЧА. РАСПРЕДЕЛЕНИЕ ОДНОРОДНЫХ РЕСУРСОВ - Студенческий научный форум

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

СБАЛАНСИРОВАННАЯ ТРАНСПОРТНАЯ ЗАДАЧА. РАСПРЕДЕЛЕНИЕ ОДНОРОДНЫХ РЕСУРСОВ

Гамидов М.М. 1
1Донской государственный технический университет
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

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

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

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

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

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

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

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

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

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. Определим неизвестные и их количество.

Обозначим через xij количество ресурса, перемещаемого из Ai пункта хранения в Bj пункт потребления. Таким образом, элементы xijобразуют матрицу перевозок 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. Определим неизвестные и их количество.

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

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

F(X)=10*x11+15*x12+20*x13+15*x21+15*x22+10*x23 +20*x31+

+10*x32+15*x33+10*x41+10*x42+25*x43 → min(1´)

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

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

(2´)

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

(3´)



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

x11≥0, x12≥0, x13≥0, x21≥0, x22≥0, x23≥0, x31≥0, x32≥0, x33≥0, x41≥0, x42≥0, x43≥0,(4´)

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

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

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

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

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

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

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

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

стройку, используя встроенную функцию 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.

Просмотров работы: 1667