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

Решение задачи методом Била

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

Допустимое базисное решение:

x4=2-(x1+x2)

x5=0-(3x1+x3)

Целевая функция:

Y = (0 +10,5x1+2,5x2+3,5x3)*1+

+(10,5 - 5x1 - x2 + 0x3)*x1+

+(2,5 - x1 - x2 + 0x3)*x2+

+(3,5 + 0x1 + 0x2 - x3)*x3

 

Теперь можно сформировать первую таблицу.

 

Таблица 3.1 – Исходная таблица 1 итерации

БП СЧ X1 X2 X3
X1        
X2        
X3        
X4   -1 -3  
X5   -3   -1
    21/2 5/2 7/2
X1 21/2 -5 -1  
X2 5/2 -1 -1  
X3 7/2     -1

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

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

, для и

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

Направляющий столбец – x1

Направляющая строка – x5

Элемент, находящийся на пересечении направляющей строки и направляющего столбца – разрешающий (в данном случае он равен -3).

Таблица 3.2 – Промежуточная таблица 1 итерации

БП СЧ X5 X2 X3
X1   -1/3   -1/3
X2        
X3        
X4   1/3 -3 1/3
X5        
    -7/2 5/2  
X5 21/2 5/3 -1 5/3
X2 5/2 1/3 -1 1/3
X3 7/2     -1

Верхнюю часть окончательной таблицы переписываем без изменений из промежуточной в итоговую.

Второй направляющей строкой является строка, пересекающаяся с направляющим столбцом по главной диагонали нижней части таблицы.

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

,

- искомый элемент, где i – номер строки, а j – номер столбца (нумерация строк начинается с нижней части таблицы)

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

- элемент второй разрешающей строки, где к – номер второй разрешающей строки

- элемент первой разрешающей строки, где h – номер первой разрешающей строки.

 

Таблица 3.3 - Итоговая таблица 1 итерации

БП СЧ X5 X2 X3
X1   -1/3   -1/3
X2        
X3        
X4   1/3 -3 1/3
X5        
    -7/2 5/2  
X5 -7/2 -5/9 1/3 -5/9
X2 5/2 1/3 -1 1/3
X3   -5/9 1/3 -14/9

Элементы первой строки нижней части таблицы, стоящие на пересечении с U-ми столбцами не равны нулю или элементы, стоящие на пересечении с Х-ми столбцами, положительны, следовательно решение не является оптимальным.

В качестве начальной таблицы 2-й итерации воспользуемся итоговой таблицей первой итерации.

Рассматриваем первую строку нижней части таблицы без первого элемента.

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

Направляющий столбец – x2

Направляющая строка – x4

 

Таблица 3.4 – Промежуточная таблица 2 итерации

БП СЧ X5 X4 X3
X1   -1/3   -1/3
X2 2/3 1/9 -1/3 1/9
X3        
X4        
X5        
  5/3 -29/9 -5/6 5/18
X5 -59/18 -14/27 -1/9 -14/27
X4 11/6 2/9 1/3 2/9
X3 2/9 -14/27 -1/9 -41/27

 

Таблица 3.5 – Итоговая таблица 2 итерации

БП СЧ X5 X4 X3
X1   -1/3   -1/3
X2 2/3 1/9 -1/3 1/9
X3        
X4        
X5        
  26/9 -83/27 -11/18 23/54
X5 -83/27 -40/81 -2/27 -40/81
X4 -11/18 -2/27 -1/9 -2/27
X3 23/54 -40/81 -2/27 -121/81

Решение продолжается. Из базиса выводится x1 и вводится x3.

Таблица 3.6 – Промежуточная таблица 3 итерации

БП СЧ X5 X4 X1
X1        
X2 2/3   -1/3 -1/3
X3   -1   -3
X4        
X5        
  26/9 -7/2 -11/18 -23/18
X5 -83/27   -2/27 40/27
X4 -11/18   -1/9 2/9
X1 23/54   -2/27 121/27

 

Таблица 3.7 – Итоговая таблица 3 итерации

БП СЧ X5 X4 X1
X1        
X2 2/3   -1/3 -1/3
X3   -1   -3
X4        
X5        
  26/9 -7/2 -11/18 -23/18
X5 -7/2 -1   -3
X4 -11/18   -1/9 2/9
X1 -23/18 -3 2/9 -121/9

В итоговой таблице матрица в нижней части таблицы симметрическая, а в первой строке значения, стоящие на пересечении с Х-ми столбцами отрицательные, на пересечении с U-ми столбцами – равны нулю, а следовательно, полученное решение является оптимальным.

 

Ответ: Y = 26/9, X = (0; 2/3; 0).

 

 


3.3 Преобразование нелинейной модели к сепарабельному виду. Аппроксимация нелинейной сепарабельной функции кусочно-линейной функцией

 

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

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

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

x1+3x2 ≤ 2

3x1+x3 ≤ 0

x1,2,3 ≥ 0

 

Преобразуем нелинейную модель к сепарабельному виду, введя подстановки

,

где y и z новые переменные.

 

В задачу также добавятся новые ограничения:

и ограничения для обеспечения неотрицательности:

Определим верхние и нижние границы переменных x1, x2, x3, z, y. Для этого решаем соответствующие задачи линейного программирования c ограничениями:

x1+3x2 ≤ 2

3x1+x3 ≤ 0

x1,2,3 ≥ 0

 

Границы х1:

Y=x1 → min, Y=0;

Y=x1 → max, Y=0;

 

Границы х2:

Y=x2 → min, Y=0;

Y=x2 → max, Y=2/3;

 

Границы х3:

Y=x3 → min, Y=0;

Y=x3 → max, Y=0;

 

Границы y:

Y=y → min, Y=0;

Y=y → max, Y=1/3;

 

Границы z:

Y=z → min, Y=-1/3;

Y=z → max, Y=0;

 

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

Рисунок 3.1 - График функции F(x)=5x2-

Рисунок 3.2 - График функции F(x)=y2

Рисунок 3.3 - График функции F(x)=z2

 

Точки следует выбрать в соответствии со следующим правилом: чем менее линейна функция на определенном участке, тем выше должна быть плотность точек аппроксимации. Разбиения, принятые при решении данной задачи, приведены в таблице 3.8.

 

Таблица 3.8 – Сетка аппроксимации

Переменная Номера точек
                     
x1                    
x2   2/27 4/27 2/9 8/27 10/27 4/9 14/27 16/27 2/3
x3                    
y1   1/27 2/27 1/9 4/27 5/27 2/9 7/27 8/27 1/3
z1 -1/3 -8/27 7/27 -2/9 -5/27 -4/27 -1/9 -2/27 -1/27  

 

 


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


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

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