Учебная работа № /7264. «Контрольная Элементы линейного программирования, вариант 4
Учебная работа № /7264. «Контрольная Элементы линейного программирования, вариант 4
Содержание:
ИДЗ № 2. Элементы линейного программирования
1. Решить системы линейных уравнений методом Гаусса:
1.1. 1.2.
2. Найдите общее решение системы линейных однородных уравнений и запишите ее фундаментальную систему решений:
3. Относительно некоторого базиса заданы векторы: .
а) докажите, что векторы можно принять за новый базис;
б) найдите координаты вектора в базисе .
4. Определите ранг системы векторов:
и укажите какой-нибудь базис этой системы.
5. Найдите собственные векторы
5.1. 5.2.
6. Найдите наибольшее и наименьшее значения линейной функции при ограничениях:
Выдержка из похожей работы
Согласно фундаментальной теореме вместо исследования бесконечного множества допустимых решений, необходимо исследовать лишь конечное число ДБР, Таким образом, принципиальная схема решения ЗЛП такова:
найти все ДБР;
вычислить для каждого из них соответствующее значение ЦФ z;
сравнить и определить наилучшее,
Но, в общем случае при больших значениях п и т количество ДБР может быть огромным (порядка С пт) и практическое осуществление перебора всех ДБР станет невозможным, Эти трудности обусловлены тем, что указанная принципиальная схема связана с беспорядочным перебором ДБР, без учета, насколько новое проверяемое ДБР изменяет ЦФ z и приближает ли оно нас к искомому оптимуму, Если же указанный перебор ДБР производить целеустремленно, добиваясь на каждом шаге монотонного изменения ЦФ z, т,е, чтобы каждое следующее ДБР было лучше предыдущего (или по крайней мере не хуже), то число анализируемых ДБР можно резко сократить,
Основной метод решения ЗЛП — симплекс-метод — базируется на идее последовательного улучшения решения, Очевидно, что для реализации этой идеи метод должен включать три основных элемента:
> способ определения исходного ДБР;
> правило перехода к следующему «лучшему» ДБР;
> критерий, по которому можно определить оптимальность найденного решения или необходимость его дальнейшего улучшения,
Табличный симплекс-метод
Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые т столбцов матрицы А, Введем новую переменную z и с помощью элементарных преобразований Жордана-Гаусса преобразуем расширенную систему к диагональной форме относительно переменных z,x1,x2,,,,,xm :
Данной диагональной форме в дальнейшем будем ставить в соответствие следующую таблицу:
В дальнейшем второй столбец будем опускать!
Построенная таблица называется симплекс-таблицей, Она содержит всю информацию, необходимую для осуществления одной итерации симплекс-метода, Реализация симплекс-метода с помощью симплекс-таблицы называется табличным симплекс-методом, По сути симплекс-метод и табличный симплекс-метод соотносятся между собой как метод и алгоритм,
Схема табличного симплекс-метода,
Шаг 0, Начальный шаг,
Пусть задано ДБР х° исходной задачи, Построим соответствующую этому ДБР х° симплекс-таблицу,
Шаг 1, Проверка условия оптимальности,
Если коэффициенты z-строки d0J, j = 1,m неотрицательные, то прекратить вычисления: текущей симплекс-таблице соответствует оптимальное ДБР,
Шаг 2, Выбор ведущего столбца,
Среди коэффициентов d0j,j = 1,n выбрать отрицательный, Пусть мы выбрали d0p, Тогда р-й столбец будет ведущим, Переменная хр будет вводиться во множество базисных переменных»
