Краткие теоретические сведения. Защите подлежит лабораторная работа, выполненная в полном объёмеЗащите подлежит лабораторная работа, выполненная в полном объёме. Оценка выставляется по 2-х бальной системе: зачтено – не зачтено. Такой порядок оценивания вызван тем, что обычно студенты-заочники имеют трудности в программировании. Студенты, представившие оригинальные программы на языке MatLab и уверенно отвечающие на вопросы по теоретической части и по сути полученных в работе результатов, могут быть поощрены дополнительной оценкой – получением льготного бала. Наличие таких балов по всем работам освобождает студента от сдачи экзамена. Ему выставляется оценка «отлично» автоматом. При наличии четырех балов или трех балов по трем последним работам автоматом предлагается оценка «хорошо». В остальных случаях экзамен сдается на общих основаниях. Министерство образования и науки РФ Федеральное агентство по образованию Саратовский государственный технический университет
ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ Лабораторный практикум по курсу «Теория принятия решений» для студентов специальности АСОИиУ (220200)
Электронное издание локального распространения
Одобрено Редакционно-издательским советом Саратовского государственного технического университета
Саратов, 2006 г.
Все права на размножение и распространение в любой форме остаются за разработчиком. Нелегальное копирование и использование данного продукта запрещено.
Составители: Митяшин Никита Петрович, Барышникова Елена Сергеевна
Под редакцией Митяшина Н. П.
Рецензент Ю.Б.Томашевский
410054, Саратов, ул. Политехническая, 77 Научно-техническая библиотека СГТУ тел. 52-52-83, 64-43-03
Регистрационный номер
© Саратовский государственный технический университет Лабораторная работа № 1 «Изучение симплекс-метода решения задач линейного программирования» ВВЕДЕНИЕ
Во ряде практических задач управления и оптимизации приходится решать задачи линейного программирования. В настоящей лабораторной работе изучается симплекс-метод решения подобных задач. Цель работы - ознакомление с симплекс-методом решения основной задачи линейного программирования.
Краткие теоретические сведения Основная задача линейного программирования (ОЗЛП) Задач линейного программирования (ЗЛП) может иметь ограничения как в виде линейных неравенств, так и в виде линейных уравнений. Покажем, что оба случая эквивалентны. Пусть мы имеем задачу с ограничениями-неравенствами:
Введем новые переменные:
Очевидно, что Теперь система (1) принимает вид:
Мы заменили систему ограничений неравенств на систему линейных уравнений ценой введения новых переменных, число которых равно m. Если заменить систему (1) на (1’’), дополнить систему ограничений (3) системой (3’), оставив в качестве целевой функции функцию (2), то мы получим задачу, эквивалентную исходной задаче. Определение: ЗЛП, в которой ограничения имеют вид системы (1) называется ОЗЛП. Пусть A- матрица ограничений ОЗЛП, r – ранг этой матрицы, т.е число, обладающее следующими 2-мя свойствами: 1. Существует минор матрицы A порядка r, который отличен от 0; 2. Любой минор порядка больше чем r равен 0. Интерес представляет случай, когда r меньше наименьшего из чисел m и n. Допустим, что минор порядка r стоит в левом верхнем углу матрицы. Если это не так, то путем замены переменных и перестановки уравнений можно этого добиться. Теперь мы можем рассматривать первые r уравнений:
Преобразуем каждое уравнение следующим образом:
В последней записи матрица порядка r, стоящая перед переменными в левой части, не особенная. Выразим переменные x1, …, xr через переменные xr+1, …, xn.
где k=n-r. Система (5) эквивалентна системе (4), но она записана таким образом, что задает структуру решения системы ограничения. Очевидно, что решения системы образуют k-мерную гиперплоскость в n-мерном пространстве. Допустимыми решениями являются только те точки, которые лежат в первом квадранте (ограничение (3)).
Определение: Переменные xr+1, …, xn стоящие в правой части (1*) называются свободными, а переменные x1, …, xr – базисными.
Определение: Допустимое решение называется базисным, если все свободные переменные равны нулю. Таким образом, базисное решение имеет вид Очевидно, что число возможных базисных решений равно числу миноров порядка r, отличных от нуля, и, следовательно, конечно. Значение базисных решений состоит в том, что имеет место теорема:
|
(1)
(2)
(3)
(1’)
(j=1..m) (3’)
(1’’)
(4)
, (5)
. 
