Методы оптимизации систем



Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 

Факультет информационных технологий

Кафедра управления и информатики в технических системах

 

 

 

 

ОТЧЕТ

по расчетно-графической работе

по курсу «Методы оптимизации систем»

Исследование методов  оптимизации

ОГУ 220201.65.6012.040. О

 

 

 

 

 

 

 

Руководитель

преподаватель

____________Ю.С. Зданевич «__»__________ 2012г.

Исполнитель

студент группы 09УИТС

____________  Д. В. Каравайцев

«__»__________ 2012 г.

 

 

 

Оренбург 2012

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Методы решения задач линейного программирования

1.1 Решение задачи графическим способом

Найти максимум и минимум  целевой функции задачи линейного  программирования с двумя переменными графическим методом:

 

 

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

 

 

Построим полученные прямые на графике, как показано на рисунке 1:

 

 

Рисунок 1 – Построение прямых на графике

 

Построим вектор n с координатами n=(4;-3) и проводим перпендикулярную прямую соответствующую значений функции f=0, рисунок 2:

 

Рисунок 2 – Построение вектора n

 

Так как нас интересуют значение max и min целевой функции, то по графику видно, что первое касание прямой с областью допустимых значений происходит в точке B(1,2;3,3), а последнее в точке D(7;-1,2). Эти точки являются входом(min) и выходом(max) области допустимых значений.

Подставим в целевую функцию  полученные координаты точек:

 

 

 

Ответ:

1.2 Решение задачи симплекс методом

Торговое предприятие  для продажи товаров вида А, В, С использует ресурсы: торговая площадь (общий объем b1, м2), время младшего торгового персонала (общий объем b2, человеко-часов), время старшего торгового персонала (общий объем b3, человеко-часов). Затраты на продажу одной партии товаров вида А составляют а11 м2, а21 человеко-часов младшего торгового персонала, а31 человеко-часов старшего торгового персонала. Для В и С эти числа соответственно а12, а22,  а32 и а13,  а23, а33. Прибыль от реализации одной партии товаров А, В, С равна с1, с2, с3 соответственно. При каком объеме реализации прибыль будет максимальна?

 

Таблица 1 – Исходные данные

b1

b2

b3

c1

c2

c3

a11

a12

a13

a21

a22

a23

a31

a32

a33

148

370

140

6

3

7

1

0,7

0

0,9

0,1

0,1

0,5

0,6

0,8


 

Решение: данная задача имеет вид:

 

 

Для построения опорного плана, введем дополнительные переменные:

 

 

Составим новую систему  ограничений:

 

 

Составим матрицу коэффициентов по формуле (1.1):

 

.                                                                        (1.1)               

 

                                         

 

Составим первый опорный план, таблица 2:

 

Таблица 2 – Первый опорный план

План

БП

СП

х1

х2

х3

х4

х5

х6

ζ min>0

1

х4

148

1

0,7

0

1

0

0

-

х5

370

0,9

0,1

0,1

0

1

0

3700

х6

140

0,5

0,6

0,8

0

0

1

175

F(x1)

0

-6

-3

-7

0

0

0

  

 

Первый план не оптимальный, так как в индексной строке есть отрицательные элементы.

Составим второй опорный  план, следую алгоритму:

- просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных переменных) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

- просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке – ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;

- среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка, в которой он находится ключевой;

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

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

- строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.

- в новой таблице все элементы ключевого столбца = 0, кроме разрешающего, он всегда равен 1.

- столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

- строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.

- в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

                                                          (1.2)

 

Таблица 2 – Второй опорный  план

План

БП

СП

x1

x2

x3

x4

x5

x6

ζ min>0

2     

x4

148

1

0,7

0

1

0

0

148

x5

352.5

0.8375

0.025

0

0

1

-0.125

420.9

x3

175

0.625

0.75

1

0

0

1.25

280

F(x2)

1225

-1.625

2.25

0

0

0

8.75

  

 

Второй план не оптимальный, так как в индексной строке есть отрицательные элементы.

Составим третий опорный  план, следую написанному выше алгоритму.

 

Таблица 3 – Третий опорный  план

План

БП

СП

x1

x2

x3

x4

x5

x6

ζ min>0

3

x1

148

1

0.7

0

1

0

0

148

x5

228.55

0

-0.555

0

-0.8375

1

-0.125

420.9

x3

82.5

0

0.31

1

-0.625

0

1.25

280

F(x3)

1465.5

0

3.38

0

1.625

0

8.75

  

Третий план, таблица 3, является оптимальным, так как в индексной строке нет отрицательных элементов. Оптимальный план выглядит следующим образом:

 

 

 

Ответ:

1.3 Решение двойственной  задачи линейного программирования

На основе подраздела 1.2 составим экономико-математическую модель двойственной задачи:

 

 

Прямая:

 

Таблица 3 – Матрица  исходной задачи

 

Элементы матрицы

Bj

 

0,1

0,9

0,4

1

0

0

108

 

0,9

0,8

0,4

0

1

0

413

 

0,1

0,2

0,3

0

0

1

129

Ci

4

2

4

0

0

0

max


 

Двойственная:

 

Таблица 4 – Транспонированная  матрица

Транспонированная матрица

0,8

0,9

0,1

4

0,9

0,8

0,2

2

0,4

0,4

0,3

4

1

0

0

0

0

1

0

0

0

0

1

0

108

413

129

min


Выпишем соответствие между  прямой и двойственной задачи:

Таблица 5 – Соответствие

Основные переменные

Дополнительные переменные

x1

x2

x3

x4

x5

x6

z4

z5

z6

z1

z2

z3


 

На основе данного  решения двойственная задача выглядит следующим образом:

 

 

                                                      

                                             

                                         

 

Ответ: .

1.4 Решение транспортной задачи методом потенциалов

Есть три поставщика с запасами a1, a2, a3 и 5 потребителей (их спрос b1, b2, b3, b4, b5 соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей C размера 3х5. Найти оптимальный план поставок.

 

Решение: исходные данные по задаче указаны в таблице 6:

 

Таблица 6 – Таблица тарифов

Пункт

b1

b2

b3

b4

b5

Запас

а1

6

2

1

8

6

65

а2

5

7

2

1

1

50

а3

6

7

2

2

7

20

Потреб

27

13

19

15

11

  

 

Данная модель является открытой, так как не выполняется  условие  , следует, привести ее к закрытой модели добавив фиктивного потребителя с нулевыми тарифами, и составим опорный план методом минимальной стоимости:

 

Таблица 7 – Метод минимальной стоимости

Пункт

b1

b2

b3

b4

b5

b6

Запас

а1

3

13

19

-

-

30

65

а2

24

-

-

15

11

-

50

а3

-

-

-

-

-

20

20

Потреб

27

13

19

15

11

50

  
 

Транспортные расходы

209


 

Составим целевую функцию:

 

 

Проверим полученный опорный план на невырожденность по формуле 1.3:

 

                                                  (1.3)

Решение:

 

Определим потенциалы поставщиков и потребителя из формулы 1.4:

 

                                                              (1.4)

 

Решение:

 

Проверим опорный план на оптимальность, вычислив оценки свободных ячеек из формулы 1.5:

 

                                                    (1.5)

 

Решение:

 

 

Все оценки свободных  ячеек не отрицательны, найдено оптимальное решение.

Ответ: Для того, удовлетворить потребности потребителя, поставщикам необходимо: товар поставщика A1 распределить по потребителям B1, B2, B3 в количестве 3, 13, 19 соответственно; товар поставщика A2 распределить по потребителям B1, B4, B5 в количестве 24, 15, 11 соответственно. Общие затраты на доставку все продукции составляют 209 ден. ед.

 

 

2 Решение задач  линейного программирования с  помощью MS Excel

2.1 Решение  задачи симплекс методом с  помощью надстройки MS Excel «Поиск решения»

Торговое предприятие  для продажи товаров вида А, В, С использует ресурсы: торговая площадь (общий объем b1, м2), время младшего торгового персонала (общий объем b2, человеко-часов), время старшего торгового персонала (общий объем b3, человеко-часов). Затраты на продажу одной партии товаров вида А составляют а11 м2, а21 человеко-часов младшего торгового персонала, а31 человеко-часов старшего торгового персонала. Для В и С эти числа соответственно а12, а22,  а32 и а13,  а23, а33. Прибыль от реализации одной партии товаров А, В, С равна с1, с2, с3 соответственно. При каком объеме реализации прибыль будет максимальна?

Исходные данные задачи представлены на рисунке 2.1:

 

 

Рисунок 2.1 – Исходные данные

 

В ячейку E3, значение целевой функции, введем формулу (2.1):

 

                                (2.1)

 

В ячейки Е9:Е11, количество материалов, введем формулы (2.2):

 

                              (2.2)

 

Результат ввода формул 2.1 и 2.2 показан на рисунке 2.2:

 

 

Рисунок 2.2 – Результат ввода формул 2.1 и 2.2

 

Выбираем команду «Поиск решения» и заполняем диалоговое окно «Поиск решения» как показано на рисунке 2.3:

 

 

Рисунок 2.3 – Диалоговое окно команды «Поиск решения» для задачи оптимизационного типа

 

 

Рисунок 2.4 – Результат расчета задачи оптимизационного типа

 

Прибыль будет максимальна  при объеме реализации .

Ответ:

2.2 Решение  двойственной задачи и анализ  полученных данных

К имеющимся данным задачи подраздела 2.1 добавим следующее: двойственные оценки (z) – H9:H11, в ячейку Н13 введем формулу (2.3) целевой функции:

 

                             (2.3)

 

 

Рисунок 2.5 – Ввод формулы 2.3 целевой ячейки

 

В ячейку диапазона B13:D13 введем формулы (2.4) определяющие левые части ограничений двойственной задачи:

 

                                    (2.4)

 

 

Рисунок 2.6 – Ввод формулы 2.4 ограничения двойственной задачи

Выбираем команду «Поиск решения» и заполним диалоговое окно как показано на рисунке 2.7:

 

Рисунок 2.7 – Диалоговое окно команды «Поиск решения» для двойственной задачи

 

Затраты будут минимальны при объеме реализации равной .

Ответ:

2.3 Решение задачи в предположении целочисленности переменных

На основе задачи подраздела 2.1, при помощи команды «Поиск решения», добавим следующее ограничение целочисленности рисунок 2.8:

 

 

Рисунок 2.8 – Диалоговое окно команды «Поиск решения»

 

Рисунок 2.9 – Результат  целочисленного решения задачи симплекс методом с помощью надстройки MS Excel «Поиск решения»

2.4 Решение  транспортной задачи с помощью  надстройки MS Excel «Поиск решения»

Есть три поставщика с запасами a1, a2, a3 и 5 потребителей (их спрос b1, b2, b3, b4, b5 соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей C размера 3х5. Найти оптимальный план поставок. Исходные данные представлены на рисунке 2.10.

 

 

Рисунок 2.10 – Исходные данные

 

Исходная задача является открытой моделью, так как сумма потребностей больше суммы поставщика. Добавим фиктивного потребителя с нулевыми тарифами и запасами, рассчитанными по формуле (2.5):

 

                                                       (2.5)

 

Введем в ячейку H13 формулу 2.6 целевой функции:

 

                             (2.6)

 

В ячейки B12:G12 введем формулы (2.7):

 

                                       (2.7)

 

В ячейки H9:H11 введем формулы (2.8):

 

                                      (2.8)

 

При помощи команды «Поиск решений» добавим следующие ограничения  и значение целевой функции рисунок 2.12:

 

 

Рисунок 2.12 – Диалоговое окно команды «Поиск решений»

 

 

Рисунок 2.13 – Результат расчета транспортной задачи

 

Минимальные затраты  на поставку всей продукции составляют 209 ден.ед.

Ответ:

 

 

 

 

 

 

 

 

 

Выводы

В данной расчетно-графической работе было рассмотрено решение задач линейного программирования различными методами. Были рассчитаны min(max) значения целевой функции графическим методом. Симплекс методом был рассчитан оптимальный план реализации продукции для получения max прибыли, а так же рассмотрена её двойственное представление, по которому рассматривается минимизация затрат ресурсов. Так же решение задачи транспортным методом, найден оптимальный план перевозки продукции при минимальных расходах. Для проверки решения данные задачи были рассчитаны при помощи программы MS Excel, полученные значения целевых функций совпали.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Лист

 



 


Методы оптимизации систем 📙 Курсовая → 🆔 128265

Методы оптимизации систем 📙 Курсовая → 🆔 128265

Методы оптимизации систем