Файл: Методы оптимизации лабораторный практикум.pdf

Матрица
 
11 12 1
21 22 2
1 2
n
n
ij
m n
m
m
mn
c с 







называется матрицей тарифов (издержек или транспортных расходов. Пример. На складах
1 2
3
,
,
A A
A хранится
1 100,
a

2 200,
a

3 120
a

единиц одного итого же груза, соответственно. Требуется доставить его трем потребителям
1 2
3
,
,
B B
B , заказы которых составляют единиц груза, соответственно. Стоимости перевозки единицы груза с го склада j-му потребителю указаны в транспортной таблице
1 190
b

2 120
b

3 60
b

1 100
a

4 2
6 2
200
a

7 5
3 3
120
a

1 7
6 Установить является ли модель транспортной задачи, заданная таблицей, открытой или закрытой. Если модель является открытой, то ее необходимо закрыть. Составить план перевозок, обеспечивающий минимальную стоимость перевозок. Найти минимальную стоимость перевозок. Решение. Суммарные запасы груза 100+200+120=420, а суммарные потребности 190+120+60=370. Следовательно, задача является задачей открытого типа и ее необходимо закрыть, вводя фиктивного потребителя с потребностями 420-370=50 единиц груза, при нулевых стоимостях перевозок.
1 190
b

2 120
b

3 60
b

4 50
b

1 100
a

4 2
6 0
2 200
a

7 5
3 0
3 120
a

1 7
6 0 Для решения задачи составим ее математическую модель

1. Введем обозначения
0 (
1,3;
1, 4)
ij
x
i
j



– количество единиц груза, которое планируется доставить от ого склада к j-му потребителю.
2. Составим целевую функцию – минимальную стоимость перевозок. Сформулируем ограничения рассматриваемой задачи. Груз из всех складов должен быть перевезен. Это ограничение можно записать в виде
11 12 13 14 21 22 23 24 31 32 33 34 100,
200,
120.
x
x
x
x
x
x
x
x
x
x
x
x

















(2.6)
3.2. Необходимо удовлетворить потребности всех потребителей в грузе. Это ограничение можно записать так
11 21 31 12 22 32 13 23 33 14 24 34 190,
120,
60,
50.
x
x
x
x
x
x
x
x
x
x
x
x



















(2.7)
3.3. Введем граничные условия, которые определяют предельно допустимые значения искомых переменных. Для нашей задачи их можно представить в виде


0,
1,3,
1, 4 .
ij
x
i
j



(2.8) Таким образом, целевая функция (2.5) и ограничения (2.6−2.8) образуют математическую модель транспортной задачи. Решение задачи в пакете Maple Подключаем пакеты linalg и simplex:
>with(linalg):
with(simplex): Вычисляем суммарные запасы груза и суммарные потребности Задаем матрицу перевозок, матрицу стоимостей и целевую функцию
>x:=matrix(3,4);
>C:=matrix(3,4,[[4,2,6,0],[7,5,3,0],[1,7,6,0]]);
>Z:=sum(sum(C[i,j]*x[i,j],i=1..3),j=1..4); Решаем задач линейного программирования, те. находим оптимальный план ТЗ:
>minimize(Z,
{sum(x[1,j],j=1..4)=100,
sum(x[2,j],j=1..4)=200,
sum(x[3,j],j=1..4)=120,
sum(x[i,1],i=1..3)=190,
sum(x[i,2],i=1..3)=120,
sum(x[i,3],
i=1..3)=60,
sum(x[i,4],i=1..3)=50},
NONNEGATIVE);
5. Представляем полученное решение в матричном виде
>v:=matrix([[70,30,0,0],[0,90,60,50],[120,0,0,
0]]); Определяем минимальную стоимость перевозок
>sum(sum(C[i,j]*v[i,j], i=1..3), j=1..4); Если убрать требование перехода к задаче закрытого типа, то решение будет иметь вид

>C:=matrix([[4,2,6], [7,5,3], [1,7,6]]);
>Z:=sum(sum(C[i,j]*x[i,j], i=1..3), j=1..3);
>minimize(Z,
{sum(x[1,j],j=1..3)<=100,
sum(x[2,j],j=1..3)<=200,
sum(x[3,j],j=1..3)<=120,
sum(x[i,1],i=1..3)=190,
sum(x[i,2],i=1..3)=120,
sum(x[i, 3],i=1..3)=60}, NONNEGATIVE);
>v:=matrix([[0,100,0],[70,20,60],[120,0,0]]);
>sum(sum(C[i,j]*v[i,j], i=1..3), j=1..3); Решение задачи в пакете Mathcad Prime Для решения задачи в пакете Mathcad Prime необходимо Задать исходные данные. На вкладке Математика выбрать Блок решения. В области Начальные приближения присвоить переменным, те. матрице X начальные (любые, например, единичные) значения и задать целевую функцию – минимальную стоимость перевозок. В области Ограничения ввести все необходимые ограничения. В области «Решатель» найти оптимальное решение с помощью функции minimize и вычислить минимальную стоимость перевозок Решение задачи в среде электронных таблиц MS Excel Идентифицируйте свою работу, переименовав Лист в Титульный лист и записав номер лабораторной работы, ее название, кто выполнили проверил. Наследующем листе (см. рис. 2.1), с именем Транспортная задача, создайте таблицу для ввода условий задачи и введите исходные данные.
3.Матрицу перевозок заполните пока нулевыми значениями. Матрицу перевозок дополните двумя столбцами справа и двумя строками снизу.

В ячейку D18 введите формулу целевой функции – стоимость перевозок
=СУММПРОИЗВ(C4:F6;C11:F13). Рис. 2.1 В ячейку G11 запишите формулу СУММ. Эту формулу скопируйте автозаполнением в остальные ячейки диапазона G12:G13. В ячейку C14 запишите формулу СУММ. Эту формулу скопируйте автозаполнением в остальные ячейки диапазона D14:F14.
8. На вкладке Данные выберите пункт Поиск решения.
9. В появившемся окне Параметры поиска решения нужно выполнить необходимые установки (см. рис. 2.2):

Рис. 2.2
− Ввести абсолютный адрес целевой ячейки $D$18 в поле Оптимизировать целевую функцию или щѐлкните по кнопке
, затем по ячейке D18 и снова по кнопке
− Введите направление целевой функции, щѐлкнув левой кнопкой мыши по селекторному полю Минимум.
− В поле Изменяя ячейки переменных впишите абсолютный адрес диапазона ячеек $C$11:$F$13 или щѐлкните по кнопке
, выделите мышью диапазон ячеек C11:F13 и снова щѐлкните по кнопке
− В поле В соответствии с ограничениями введите ограничения с помощью кнопки Добавить. При этом вызывается диалоговое окно Добавление ограничения, показанное на рис. 2.3.

Введите систему ограничений (2.6). В поле Ссылка на ячейки щѐлкните по кнопке
, затем выделите мышью диапазон ячеек
G11:G13 и снова щѐлкните по кнопке
, в следующем поле установите знак =, нажав
, затем в поле Ограничение щѐлкните по кнопке
, затем выделите мышью диапазон ячеек H11:H13 и снова щѐлкните по кнопке см. рис. 2.3). Нажмите «ОК». Рис. 2.3 Аналогично введите систему ограничений (2.7). В поле Ссылка на ячейки щѐлкните по кнопке
, затем выделите мышью диапазон ячеек C14:F14 и снова щѐлкните по кнопке
, в следующем поле установите знак =, нажав
, затем в поле Ограничение щѐлкните по кнопке
, затем выделите мышью диапазон ячеек C15:F15 и снова щѐлкните по кнопке
(см. рис. 2.4). Нажмите «ОК». Рис. 2.4 Введите ограничение (2.8). В поле Ссылка на ячейки щѐлкни- те по кнопке
, затем выделите мышью диапазон ячеек C11:F13 и снова щѐлкните по кнопке
, в следующем поле установите знак >=,

нажав
, затем в поле Ограничение введите 0 (см. рис. 2.5). Нажмите «ОК». Рис. 2.5
− Установите галочку Сделать переменные без ограничений неотрицательными.
− Выберете метод решения Поиск решения линейных задач симплекс-методом»
− Нажмите Найти решение. В появившемся окне Результаты поиска решения нажмите «ОК». Результат полученных вычислений представлен на рис. 2.6. Выводы Анализ полученного решения показывает, что минимальная стоимость перевозок составляет 1090 при двух разных оптимальных перевозках
1 70 30 0
0 90 60 120 0
0
опт
X




 





,
2 0
100 0
70 20 60 .
120 0
0
опт
X




 Исходные данные для лабораторной работы Продукция определенного вида производится в городах
1 2
3
,
,
A A
A и потребляется в городах и В таблице указаны объем производства, спрос, стоимость перевозки единицы продукции. Составить оптимальный план перевозки продукции, при котором стоимость всех перевозок будет минимальна. Предварительно следует проверить, сбалансирована ли данная транспортная задача. Если задача не сбалансирована, то нужно ввести фиктивных потребителей или производителей, добавляя к исходной таблице столбцы или строки.

Рис
№1 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
26 47 25 20 48 2
A
10 40 43 6
28 3
A
9 34 46 15 71 Спрос
47 81 25 44

№2 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
47 25 20 47 41 2
A
23 47 28 17 41 3
A
7 43 39 10 79 Спрос
40 46 88 37
№3 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
25 20 47 30 32 2
A
40 43 6
36 49 3
A
22 47 29 16 46 Спрос
13 50 46 28
№4 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
20 47 30 14 22 2
A
47 28 17 46 58 3
A
34 46 15 29 78 Спрос
43 42 50 18
№5 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
47 30 14 45 10 2
A
43 6
36 45 61 3
A
43 39 10 40 60 Спрос
44 23 48 6

№6 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
30 14 45 35 10 2
A
28 17 46 33 44 3
A
47 29 16 46 41 Спрос
15 43 41 6
№7 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
14 45 35 7
22 2
A
6 36 45 13 83 3
A
46 15 29 47 56 Спрос
39 24 30 18
№8 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
45 35 7
43 83 2
A
17 46 33 10 18 3
A
39 10 40 43 82 Спрос
47 42 15 29
№9 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
4 5
6 10 530 2
A
8 6
3 8
405 3
A
7 10 4
11 540 Спрос
425 415 335 400

№10 Производители Потребители Объем производства
1
B
2
B
3
B
4
B
1
A
3 7
4 8
513 2
A
9 6
4 4
448 3
A
6 10 5
8 522 Спрос
437 417 333 396

ЛАБОРАТОРНАЯ РАБОТА
№3 ЗАДАЧА О НАЗНАЧЕНИЯХ Цель работы овладеть навыками составления математической модели задачи о назначениях и ее решения в математических пакетах
Maple, Mathcad Prime ив. Требуется
− изучить теоретический материал выполнить математическую постановку задачи
− решить задачу в математических пакетах Maple, Mathcad
Prime ив среде электронных таблиц MS Excel. Необходимые теоретические сведения Задача о назначениях является типичным примером оптимального принятия управленческих решений. Эта задача позволяет распределить объекты из некоторого множества по группе субъектов из другого множества и это распределение должно соответствовать оптимальности одного или нескольких итоговых показателей. Данная задача имеет место при назначении людей на должности или работы, автомашин на маршруты, водителей на машины, при распределении студенческих групп по аудиториям, научных тем по научно- исследовательским лабораториями т.п. Пусть требуется выполнить n различных работ и имеется n механизмов (машин) для их выполнения, причем каждый механизм может использоваться на любой работе. Производительность механизма на различных работах, вообще говоря, различна. Обозначим через
ij
c производительность го механизма на й работе. Задача заключается в таком распределении механизмов по работам, при котором суммарная производительность максимальна. Построим математическую модель этой задачи. Сопоставим каждому из возможных вариантов распределения машин по работам набор значений неизвестных
ij
x
, относительно которых условимся, что
1
ij
x

, если в данном варианте й механизм назначается на ю работу, и
0
ij
x

, если й механизм назначается не на ю работу. Для любого варианта среди чисел
ij
x
должно быть точно единиц, причем должны выполняться условия
1 1,
1,
n
ij
i
x
j
n





каждый механизм назначается на одну работу
1 1,
1,
n
ij
j
x
i
n




(на каждую работу назначен один механизм. Суммарная производительность приданном варианте назначения машин на работы выразится суммой
1 1
n
n
ij
ij
i
j
c Математическая постановка задачи
1 1
max
n
n
ij
ij
i
j
L
c при ограничениях
1 1
1,
1, ;
1,
1, ;
n
ij
i
n
ij
j
x
j
n
x
i
n













1, если -й механизм назначен на -ю работу, если -й механизм не назначен на -ю работу 

,
1, .
i Условия выводят задачу о назначениях из класса задач линейного программирования, так как они нелинейны. Задачи математического программирования, в которых на переменные наложены такие условия, называются задачами с булевыми переменными. Поскольку все остальные условия и целевая функция нашей задачи линейны, мы должны формально отнести еѐ к классу задач линейного программирования с булевыми переменными. Однако задачу можно рассмотреть как частный случай транспортной (и, следовательно, просто линейной) задачи. В самом деле, если отбросить последнее условие, заменив его условиями неотрицательности переменных, то задача превращается в обычную транспортную задачу, имеющую ту особенность, что в ней все
i
a
и все
j
b ,
,
1,
i равны единице. Пример. Некоторая компания имеет четыре сбытовые базы и четыре заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы вполне достаточны для того, чтобы вместить один из этих заказов. В табл. 3.1 содержится информация о расстоянии между каждой базой и каждым потребителем. Как следует распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной Решение. Для решения задачи составим ее математическую модель. Введем обозначения

1, если -ая сбытовая база осуществляет перевозки к -му потребителю, иначе, 4.
ij
i
j
x
i j

 Таблица 3.1 Сбытовая база Расстояние, миль Потребители
I
II
III
IV
1 68 72 75 83 2
56 60 58 63 3
38 40 35 45 4
47 42 40 45 2. Составим целевую функцию – минимальная дальность транспортировки 56 60 58 63 38 40 35 45 47 42 40 45
min .
ij
ij
i
j
Z
c x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x























(3.1)
3. Сформулируем ограничения рассматриваемой задачи. Каждая сбытовая база вмещает один заказ. Это ограничение можно записать в виде
11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 1,
1,
1,
1.
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x























(3.2)
3.2. Каждый заказ распределяется на одну сбытовую базу. Это ограничение можно записать так
11 21 31 41 12 22 32 42 13 23 33 43 14 24 34 44 1,
1,
1,
1.
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x























(3.3)
3.3. Бинарность переменных
ij
x
:
ij
x
− бинарные (двоичные,
1, 4,
1, 4.
i
j


(3.4) Таким образом, целевая функция (3.1) и ограничения (3.2−3.4) образуют математическую модель задачи о назначениях.