Численные методы

Размещено на http://www.allbest.ru/

1. Задача линейного программирования

Понятия ЛП: Линейное программирование решает задачи, которые относятся к такой сфере человеческой деятельности как сельское хозяйство, военное дело, промышленное производство, транспорт и здравоохранение.

Линейное программирование - это наука о методах, исследование и отыскивания min (max) линейной функции, на переменные которой наложены линейные ограничения.

Линейность - это свойство математических выражений и функций выражение ax+by является линейным относительно переменных x и y.

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

(1) при условиях

, где (2)

_{(i=k+1, m)} (3)

(4)

Функция (1) называется целевой функцией задачи (2) - (4) условия (2) - (4) ограничениями данной задачи.

Стандартной задачей линейного программирования называется, задача которая состоит в определении максимума значения функции (1) при выполнении условий (2) - (4), где k=m и t=n.

Канонической задачей линейного программирования называется задача, которая состоит в определении максимума значения функции (1) при выполнении условий (3) - (4), где k=0 и t=n.

Совокупность чисел x=x1, x2,… xn, удовлетворяющих ограничениям задачи (1.2) - (1.4) называется планом.

Общая задача линейного программирования

Постановка задачи: Найти наибольшее (наименьшее) значение показателей эффективности целевой функции

Z=c₁x₁ + c₂x₂ + … + c_nx_n -> max (min)

При системе линейных ограничений:

n - количество переменных

m - количество ограничений

Необходимо найти значение x₁, x₂, …, x_n, неотрицательные, соответствующие системе ограничений (2), в которой функция Z принимает max (min) значение.

Этапы решения задачи ЛП графическим методом:

1. Систему ограничений представить в виде системы равенств;

2. Получить многоугольник допустимых решений;

3. Начертить прямую целевой функции;

4. Построить перпендикуляр к прямой целевой функции, которая проходит через т. (0; 0)

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

2. Симплекс - метод

Универсальным методом решения систем линейных уравнений является симплексный метод.

Идея симплексного метода состоит в том, что поставленная описательная задача переводится в математическую форму. Математическая формулировка задачи содержит уравнение целевой функции с указанием желаемого результата - определение минимума или максимума целевой функции; системы линейных ограничений, заданных равенствами или неравенствами. Полученное математическое описание приводят к матричному виду. Затем матричное описание задачи приводят к канонической форме. После того как система линейных уравнений приведена к канонической форме, приступают к решению задачи линейного программирования. Алгоритм решения этой задачи состоит из последовательности построения матриц. Каждый шаг решения приближает к получению желаемого результата

а) Алгоритм Симплекс-метода:

1. Заменяя систему неравенств на систему уравнений, добавляем дополнительные переменные;

2. Выражаем дополнительные переменные через остальные;

3. Находим первое опорное решение при независимых переменных;

4. Если при решении задачи в записи целевой функции есть отрицательные (положительные) коэффициенты, то:

а). Рассматриваем элементы из записи целевой функции с наибольшим по модулю `'-`' коэффициентом (при решении на min рассматривается наибольший `'+'' коэффициент).

Переменные с наибольшим коэффициентом выражаем через остальные;

б). Находим min соответствие свободных элементов к коэффициенту выбранной переменной;

в). Подставляем полученное выражение в другие уравнения и целевую функцию;

г). Находим опорное решение при всех независимых переменных, равных нулю;

5. Смотрим пункт 4).

6. Получаем оптимальный план.

б) Метод искусственного базиса:

Если в системе ограничений в неравенствах содержится знак = или >=0, то для построения первого опорного плана вводят искусственные базисные переменные.

Z=x₁ + 1,1x₂ + 7,5x₃ -> min

Решение:

Для получения решения в каждое уравнение добавляют неотрицательные искусственные переменные (0)

Для искусственных переменных коэффициент целевой функции M.

Если решается задача на min M - очень большое `'+'' число, если на max - очень маленькое `'-`'

Продолжить решение системы по алгоритму симплекс - метода.

в) Двойственный симплекс-метод.

Рассмотрим алгоритм двойственного симплекс-метода.

Запишем условия задачи:

линейный ограничение симплекс максимум

Введём новую функцию

Приведём условия задачи к каноническому виду:

1. Запишем симплекс таблицу, соответствующую задаче.

2. Все коэффициенты в строке целевой функции - неположительные , следовательно выполнены условия оптимальности решения.

3. В столбце свободных членов есть отрицательный элемент , следовательно, выделенное базисное решение не является допустимым (так как все неизвестные должны быть неотрицательными). Строку с отрицательным свободным членом назовём «разрешающей».

4. Находим в разрешающей строке отрицательные элементы. Если таковых нет, задача решения не имеет.

5. В разрешающей строке есть отрицательные элементы . Составляем соотношения коэффициентов целевой функции (они не положительные) к отрицательным элементам разрешающей строки и находим среди этих отношений наименьшее:

.

Столбец коэффициентов в ограничениях задачи с наименьшим отношением назовём «разрешающим».

6. На пересечении разрешающей строки и разрешающего столбца находится отрицательный разрешающий элемент (в таблице условно выделен элемент - a₃₁). Производим преобразование Гаусса-Жордана с найденным разрешающим элементом.

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

8. Через конечное число шагов или будет получено оптимальное решение, или же будет установлено, что допустимых (неотрицательных) решений нет.

Существует класс задач, условия которых естественным образом формулируются сразу во 2-й стандартной форме. Для решения таких задач двойственный симплекс метод более удобен, чем обычный алгоритм.

Литература

Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. - Минск: Вышэйшая школа, 1978.

Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б., - М.: Высшая школа, 1980.

Матвеев В.А. Компьютерная поддержка решений. - СПб.: Специальная литература, 1998.

Шикин Е.В., Чхартишвили А.Г. Математические методы и модели управления. - М.: Дело, 2000.

Исследование операций в экономике /Под ред. Кремер. - М.: ЮНИ-ТИ, 1997.

Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.

Размещено на Allbest.ru