Краткие теоретические сведения. Защите подлежит лабораторная работа, выполненная в полном объёме

Саратов, 2006 г.

Все права на размножение и распространение в любой форме остаются за разработчиком.

Нелегальное копирование и использование данного продукта запрещено.

Составители: Митяшин Никита Петрович,

Барышникова Елена Сергеевна

Под редакцией Митяшина Н. П.

Рецензент Ю.Б.Томашевский

410054, Саратов, ул. Политехническая, 77

Научно-техническая библиотека СГТУ

тел. 52-52-83, 64-43-03

Регистрационный

номер

© Саратовский государственный

технический университет

Лабораторная работа № 1

«Изучение симплекс-метода решения задач линейного программирования»

ВВЕДЕНИЕ

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

Цель работы - ознакомление с симплекс-методом решения основной задачи линейного программирования.

Краткие теоретические сведения

Основная задача линейного программирования (ОЗЛП)

Задач линейного программирования (ЗЛП) может иметь ограничения как в виде линейных неравенств, так и в виде линейных уравнений. Покажем, что оба случая эквивалентны. Пусть мы имеем задачу с ограничениями-неравенствами:

(1)

(2)

(3)

Введем новые переменные:

(1’)

Очевидно, что

(j=1..m) (3’)

Теперь система (1) принимает вид:

(1’’)

Мы заменили систему ограничений неравенств на систему линейных уравнений ценой введения новых переменных, число которых равно m. Если заменить систему (1) на (1’’), дополнить систему ограничений (3) системой (3’), оставив в качестве целевой функции функцию (2), то мы получим задачу, эквивалентную исходной задаче.

Определение: ЗЛП, в которой ограничения имеют вид системы (1) называется ОЗЛП.

Пусть A- матрица ограничений ОЗЛП, r – ранг этой матрицы, т.е число, обладающее следующими 2-мя свойствами:

1. Существует минор матрицы A порядка r, который отличен от 0;

2. Любой минор порядка больше чем r равен 0.

Интерес представляет случай, когда r меньше наименьшего из чисел m и n. Допустим, что минор порядка r стоит в левом верхнем углу матрицы. Если это не так, то путем замены переменных и перестановки уравнений можно этого добиться. Теперь мы можем рассматривать первые r уравнений:

(4)

Преобразуем каждое уравнение следующим образом:

В последней записи матрица порядка r, стоящая перед переменными в левой части, не особенная. Выразим переменные x₁, …, x_r через переменные x_r+1, …, x_n.

, (5)

где k=n-r.

Система (5) эквивалентна системе (4), но она записана таким образом, что задает структуру решения системы ограничения. Очевидно, что решения системы образуют k-мерную гиперплоскость в n-мерном пространстве.

Допустимыми решениями являются только те точки, которые лежат в первом квадранте (ограничение (3)).

Определение: Переменные x_r+1, …, x_n стоящие в правой части (1^*) называются свободными, а переменные x₁, …, x_r – базисными.

Определение: Допустимое решение называется базисным, если все свободные переменные равны нулю.

Таким образом, базисное решение имеет вид .