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

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

ЛАБОРАТОРНАЯ РАБОТА «РЕШЕНИЕ НЕСБАЛАНСИРОВАННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. »

Остапенко Д.А. 1, Остапенко Д.А. 1, Киселев Н.В. 1
1Донской Государственный Технический Университет (ДГТУ)
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Цель: Рассмотреть решение несбалансированной транспортной задачи и решение несбалансированной задачи о назначениях и сравнить их.

Построим математические модели задач:

1. Несбалансированная транспортная задача:

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

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

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

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

Различают закрытую (сбалансированную) и открытую (несбалансированную) транспортную задачу. Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е., называется закрытой; в противном случае − открытой. Для открытой транспортной задачи возможны два случая:

а) суммарные запасы превышают суммарные потребности ;

б) суммарные потребности превышают суммарные запасы.

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

В случае а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Вm+1 потребность которого составит

(1).

В случае б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аn+1, запасы которого составляют

(2).

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

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

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

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

Стройка

Карьер

Стройка 1

Стройка 2

Стройка 3

Стройка 4

Запасы песка ai

Карьер 1

20

35

20

40

350

Карьер 2

50

30

50

20

500

Карьер 3

20

30

35

45

450

Потребности

в песке bj

400

400

200

300

 

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

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

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

Случай а: суммарные запасы превышают суммарные потребности;

Для того чтобы определить начальные условия и построить математическую модель данного типа изменим данные таблицы 1, увеличив запасы на первом и третьем карьере на 100 единиц.

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

Обозначим через xij количество песка (м3), перемещаемого из i-го карьера на j-ю стройку. Учтем несбалансированность задачи и введем фиктивного потребителя (Стройку 5) с нулевыми расходами на перевозку песка. Получаем потребность фиктивного потребителя по формуле (1). Таким образом, элементы xijобразуют матрицу перевозок X 4х5.

Таблица 2. Начальные условия для несбалансированной транспортной задаче (случай а)

карьер стройка

 

стройка 1

стройка 2

стройка 3

стройка 4

стройка 5

Вывезено

карьер 1

 

20

35

20

40

0

450

карьер 2

 

50

30

50

20

0

600

карьер 3

 

20

30

35

45

0

550

Доставленно

 

400

400

200

300

300

 

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

F(X)=20*x11+35*x12+20*x13+40*x14+0*x15+50*x21+30*x22+50*x23+20*x24+

+0*x25+20*x31+30*x32+35*x33+45*x34+0*x35 → min(1а´)

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

3.1. Необходимо вывезти весь песок с карьеров:

(2а´)

3.2. Удовлетворить потребности каждой стройки в песке.

(3а´)

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

x11≥0, x12≥0, x13≥0, x14≥0, x15≥0, x21≥0, x22≥0, x23≥0, x24≥0, x25≥0,

x31≥0, x32≥0, x33≥0, x34≥0, x35≥0 (4а´)

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

Решение в среде MS Excel:

 

Рис 1. Математическая модель и матрица перевозок.

 

Рис 2. Решение с помощью надстройки «Поиск решения»

 

Рис 3. Результат решения задачи

Случай б: суммарные потребности превышают суммарные запасы.

Для того чтобы определить начальные условия и построить математическую модель данного типа изменим данные таблицы 1, увеличив потребности строек на 300 единиц.

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

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

Таблица 3. Начальные условия для несбалансированной транспортной

задаче (случай б)

карьер стройка

стройка 1

стройка 2

стройка 3

стройка 4

Вывезено

карьер 1

20

35

20

40

350

карьер 2

50

30

50

20

500

карьер 3

20

30

35

45

250

Карьер 4

0

0

0

0

300

Доставленно

500

500

250

350

 

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

F(X)=20*x11+35*x12+20*x13+40*x14 +50*x21+30*x22+50*x23+20*x24+

+20*x31+30*x32+35*x33+45*x34+0*x14+0*x24 +0*x34 +0*x44→ min(1б´)

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

3.1. Необходимо вывезти весь песок с карьеров:

(2б´)

3.2. Удовлетворить потребности каждой стройки в песке.

(3б´)

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

x11≥0, x12≥0, x13≥0, x14≥0, x21≥0, x22≥0, x23≥0, x24≥0,

x31≥0, x32≥0, x33≥0, x34≥0, x41≥0, x42≥0, x43≥0, x44≥0 (4б´)

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

Решение в среде MS Excel:

 

Рис 4. Математическая модель и матрица перевозок.

 

Рис 5. Решение с помощью надстройки «Поиск решения»

 

Рис 6. Результат решения задачи

2. Несбалансированная задача о назначениях. Назначения претендентов на вакансии.

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

Рассмотрим решение несбалансированной задачи о назначениях, когда число исполнителей n не равно числу выполняемых работ m.

Работы Рj

Исполнители Иi

Р1

Р2

Рm

И1

c11

c12

c1n

И2

c21

c22

c2n

Иn

cn1

cn2

cnm

При этом возможны два случая:

а) число исполнителей n больше числа выполняемых работ m (n > m),

б) число исполнителей n меньше числа выполняемых работ m (n m, вводится k = n – m фиктивных работ Pm+1, Pm+2, …, Pm+k. Во втором случае (n m) т.к. мы формируем данные для задачи из таблицы 2, то сведем её к следующему виду:

Таблица 3. Несбалансированная задача о назначениях. Случай а.

 

Объект 1

Объект 2

Объект 3

Объект 4

Объект 5

Объект 6

Кран 1

23,50

20,3

22,5

19

0

0

Кран 2

31,2

30

31

27,5

0

0

Кран 3

31,2

31,1

31,5

30

0

0

Кран 4

28,5

32

25,5

28,5

0

0

Кран 5

32,5

33,2

31,5

29

0

0

Кран 6

30

32,2

29,3

30

0

0

Таким образом целевая функция будет иметь вид:

Случай б: (n

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