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

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

Читайте также:
  1. I. Задачи и методы психологии народов.
  2. II. НАЗНАЧЕНИЕ, ОСНОВНЫЕ ЗАДАЧИ И ФУНКЦИИ ПОДРАЗДЕЛЕНИЯ
  3. II. Цели и задачи Конкурса
  4. II. Цели и задачи Лаборатории
  5. II. Цели и задачи службы .
  6. II. Цель и задачи Фестиваля
  7. III. Обучающие тестовые задачи.

Введение

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

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


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

Решение задачи 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

 


Дата добавления: 2015-09-07; просмотров: 87 | Нарушение авторских прав


Читайте в этой же книге: Решение задачи методом отсекающих плоскостей (метод Гомори) | Решение задачи методом ветвей и границ 1 страница | Решение задачи методом ветвей и границ 2 страница | Решение задачи методом ветвей и границ 3 страница | Решение задачи методом отсекающих плоскостей (метод Гомори) | Решение задачи методом ветвей и границ | Определение вида квадратичной формы | Решение задачи методом Била | Решение задачи сепарабельным симплекс-методом | Переход от прямой задачи к двойственной |
<== предыдущая страница | следующая страница ==>
СВЯТЫНИ СЕЛА ВОЛКОВА| Решение задачи 1.3

mybiblioteka.su - 2015-2024 год. (0.01 сек.)