Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Решение задачи 1.2




Введение

В наше время всё человечество находиться на такой стадии развития, что дальнейший прогресс связан с огромными затратами ресурсов. Не каждая страна или крупная корпорация может позволить себе вести исследования в передовых областях науки. Примером таких исследований служит освоение космоса, создание реактора ядерного синтеза и изучение короткоживущих элементарных частиц. Очевидно, что ошибка в проекте может привести к провалу всего начинания. Ресурсы, затраченные на проект, также не являются бесконечными. В такой обстановке большое влияние на успех всего оказывают процессы моделирования и оптимизации. Теории, позволяющей оптимизировать любое выражение, не существует, однако, для определённых видов выражений построен математический аппарат, позволяющий найти оптимум.

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


Линейное программирование

Решение задачи 1.1

Максимизировать целевую функцию:

Y=-x1+9x2-3x3 → max

При ограничениях:

-x1-2x2-x3 ≥ -5

-x1+x2-2x3 ≤ -5

x1+2x2+x3 ≤ 7

x1,2,3,4 ≥ 0

 

Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x4, x5, x6.

x1+2x2+x3 +x4+0x5+0x6=5

x1-x2+2x3 +0x4-x5+0x6=5

x1+2x2+x3 +0x4+0x5+1x6=7

Выразим допустимый базис в форме Таккера:

X4=5-( x1+2x2+x3)

X5=-5-(-x1+x2-2x3)

X6=7-( x1+2x2+x3)

Целевая функция в форме Таккера:

Y=0-(1x1-9x2+3x3)

На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.1).

Таблица 1.1

БП СЧ X1 X2 X3 X4 X5 X6
X4
X5 -5 -1 -2
X6
Y -9

Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X5. Результат отображен в таблице 1.2.

Таблица 1.2

БП СЧ X1 X2 X3 X4 X5 X6
X4 -1
X1 -1 -1
X6 -1
Y -5 -8

 

Используем обычный симплекс-метод. Вводим в базис X2, выводим из базиса X4. Результат отображен в таблице 1.3.

Таблица 1.3

БП СЧ X1 X2 X3 X4 X5 X6
X2 -1/3 1/3 1/3
X1 5/3 1/3 -2/3
X6 -1
Y -5 -5/3 8/3 11/3

 



Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X1. Результат отображен в таблице 1.4.

Таблица 1.4

БП СЧ X1 X2 X3 X4 X5 X6
X2 1/5 2/5 1/5
X3 3/5 1/5 -2/5
X6 -1
Y

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

 

Ответ : Решения оптимально

Y=0

X=(0;1;3;0;0;2)

Количество итераций=3

 


Решение задачи 1.2

Максимизировать целевую функцию:

Y=2x1-5x2+7x3 → max

При ограничениях:

0x1-2x2+x3 ≤ 1

2x1+x2+x3 ≤ 4

-x1-2x2+0x3 ≤ -1

0x1+2x2+0x3≤3

 

x1,2,3 ≥ 0

 

Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x4, x5, x6 и х7.

0x1-2x2+x3+1x4+0x5+0x6+0x7 = 1

2x1+x2+x3+0x4+1x5+0x6+0x7 = 4

x1+2x2+0x3+0x4+0x5+1x6+0x7 = 1

0x1+2x2+0x3+0x4+0x5+0x6+1x7=3

Выразим допустимый базис в форме Таккера:

X4=1-(0x1-2x2+x3)

X5=4-(2x1+x2+x3)

X6=-1-(-x1-2x2+0x3)

X7=3-(0x1+2x2+0x3)

Целевая функция в форме Таккера:

Y=0-(-2x1+5x2-7x3)

На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.5).



Таблица 1.5

БП СЧ X1 X2 X3 X4 X5 X6 X7
X4 -2
X5
X6 -1 -1 -2
X7
Y -2 -7

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X6. Результат отображен в таблице 1.6.

Таблица 1.6

БП СЧ X1 X2 X3 X4 X5 X6 X7
X4 -2
X5 -3
X1 -1
X7
Y -7 -2

 

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X4. Результат отображен в таблице 1.7.

Таблица 1.7

БП СЧ X1 X2 X3 X4 X5 X6 X7
X3 -2
X5 -1 -1
X1 -1
X7
Y -5 -2

 

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X2, выводим из базиса X1. Результат отображен в таблице 1.8.

Таблица 1.8

БП СЧ X1 X2 X3 X4 X5 X6 X7
X3 -1
X5 3/2 1/2 -1 3/2
X2 1/2 1/2 -1/2
X7 -1
Y 23/2 5/2 -9/2

Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X6, выводим из базиса X5. Результат отображен в таблице 1.9.

Таблица 1.9

БП СЧ X1 X2 X3 X4 X5 X6 X7
X3 4/3 1/3 2/3
X6 1/3 -2/3 2/3
X2 2/3 -1/3 1/3
X7 -4/3 2/3 -2/3
Y

 

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

 

Ответ : Решение оптимально

Y=16

X=(0;1;3;0;0;1;1)

Количество итераций=4

 



mylektsii.ru - Мои Лекции - 2015-2018 год. (0.027 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал