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

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

x₄=2-(x₁+x₂)

x₅=0-(3x₁+x₃)

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

Y = (0 +10, 5x₁+2, 5x₂+3, 5x₃)*1+

+(10, 5 - 5x₁ - x₂ + 0x₃)*x₁+

+(2, 5 - x₁ - x₂ + 0x₃)*x₂+

+(3, 5 + 0x₁ + 0x₂ - x₃)*x₃

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

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

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

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

, для и

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

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

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

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

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Y=21x₁+5x₂+7x₃- -2x₁x₂- - → max

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

x₁+3x₂ ≤ 2

3x₁+x₃ ≤ 0

x_{1, 2, 3} ≥ 0

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

,

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

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

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

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

x₁+3x₂ ≤ 2

3x₁+x₃ ≤ 0

x_{1, 2, 3} ≥ 0

Границы х₁:

Y=x₁ → min, Y=0;

Y=x₁ → max, Y=0;

Границы х₂:

Y=x₂ → min, Y=0;

Y=x₂ → max, Y=2/3;

Границы х₃:

Y=x₃ → min, Y=0;

Y=x₃ → 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)=5x₂-

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

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

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

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