ЛП-метод-каЛуценко

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»

Кафедра «Математика и моделирование»

М.М. Луценко

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

РЕШЕНИЕ ЗАДАЧИ

Методические указания и варианты индивидуальных заданий для студентов заочного факультета

САНКТ-ПЕТЕРБУРГ

2006

Постановка задачи

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

Задача. Найти экстремум линейной функции F, если ее аргументы удовлетворяют некоторым ограничениям.

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

Каждый студент должен будет сделать для своей задачи все ниже перечисленные действия.

1.Записать задачу в матричной форме

2.Записать каноническую задачу.

3.Решить задачу геометрически.

4.Найти начальный базисный план с помощью искусственных переменных.

5.Решить задачу симплекс-методом.

6.Написать двойственную задачу к искомой в матричной и развернутой формах.

7.Найти решение двойственной задачи и доказать его оптимальность с помощью теоремы двойственности.

Варианты задач и пример решения указаны в конце этих указаний.

Матричная и развернутая формы задачи линейного программирования

В этом параграфе мы сравним две формы записи задачи линейного программирования.

Определение 1. Следующая задача называется стандартной задачей линейного программирования.

Задача 1. Найти

где A – матрица системы ограничений, имеющая m строк и n столбцов, b – столбец из m элементов; c, x – столбцы из n элементов. Таким образом, эти матрицы имеют вид

В развернутой форме эта стандартная задача линейного программирования может быть записана в следующем виде.

Задача 1’. Найти максимум линейной функции

3

Определение 2. Решением этих задач называется матрица (упорядоченный на-

обеспечивающая максимальное значение функции (1). Иногда это решение называется оптимальным планом задачи. Значение функции на оптимальном плане обозначается

Fmax F (x*) .

Определение 3. Линейная функция F задачи 1 называется целевой функцией, а множество D решений системы (2) – множеством допустимых решений (планов) этой задачи.

Пример 1. Записать задачу линейного программирования (1), (2) с матрицами

в развернутой форме (1 , 2 ) .

Решение. В развернутой форме задача формулируется следующим образом.

3x1 x2 28,

Пример 2. Записать следующую задачу линейного программирования в матричной форме.

Решение. Для того чтобы записать эту задачу в матричной форме (1, 2), изменим неравенства в ограничениях задачи так, чтоб они имели одинаковый знак. Для этого умножим первое неравенство на –1. Мы получим следующую систему ограничений задачи:

4

Геометрическое решение задачи линейного программирования

Для того чтобы решить задачу линейного программирования геометрически, построим множество решений системы ограничений. Любая прямая a1x1 a2 x2 p

разбивает плоскость на две полуплоскости. Для точек M (x1, x2 ) одной из полуплоско-

выпуклое многоугольное множество, полученное как пересечение полуплоскостей, каждая из которых является решением соответствующего неравенства системы.

Построим теперь линии уровня функции F c1 x1 c2 x2 . Очевидно, что это будут параллельные линии c1 x1 c2 x2 p , перпендикулярные нормальному вектору n (c1 ,c2 ) . Следовательно, при параллельном перемещении линии уровня в направ-

лении вектора n значение целевой функции F будет возрастать, а противоположном убывать. Свое максимальное значение функция F примет на «последней» общей точке множества допустимых решений и соответствующей линии уровня при ее параллельном переносе в направлении вектора n .

Пример 3. Решить следующую задачу линейного программирования геометриче-

ски.

таточно проверить хотя бы одну точку этой полуплоскости, например, начало координат O(0,0) . Пересечение полуплоскостей составит множество допустимых решений задачи D.

5

Построение симплекс-таблицы

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

Задача 2. Найти минимум линейной функции:

Определение 5. Мы будем говорить, что задача линейного программирования (1,2) сведена к некоторой канонической задаче линейного программирования (возможно с другим числом переменных и ограничений), если по решению первой задачи можно построить решение второй задачи и наоборот.

Пример 4. Свести задачу линейного программирования

6

3x1 x2 28, x1, x2 0 ,

к канонической задаче.

Перенесем члены неравенств в одну часть так, чтобы полученные выражения были неотрицательны:

компоненты будут неотрицательны. И наоборот каждому неотрицательному решению

Если функция F принимает в некоторой точке максимальное значение, то в этой точке функция (–F) принимает свое минимальное значение. Причем эти значения будут равны с точностью до знака. Таким образом, вместо максимума функции

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

F1 7x1 2x2 min ,

при ограничениях

5x1 6x2 x3 30,

4x1 3x2 x4 20,

3x1 x2 x5 28, x1 , x2 , x3 , x4 , x5 0 .

По оптимальному решению первоначальной задачи легко найти оптимальное решение канонической задачи.

7

Условие оптимальности.

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

нием, быть может, числа c0 .

Таким образом, мы выделили класс симплекс-таблиц, по которым легко построить оптимальное базисное решение.

Пример 6. Записать следующую задачу в форме симплекс таблицы в базисе переменных x3 , x4 , x5 , а также условия допустимости и оптимальности соответствующего базисного решения.

Решение. Соответствующая симплекс таблица будет иметь вид:

тимым, если b1 ,b2 ,b3 0 и оптимальным, если c1 , c2 0 . При выполнении этих условий минимальное значение функции F будет равно c0 .

Преобразование симплекс таблиц

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

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

Проверка оптимальности и выбор генерального элемента симплекс таблицы

Если все элементы последней строки таблицы, кроме последнего, неположительные, то таблица порождает оптимальное базисное решение.

За генеральный столбец берётся тот столбец таблицы, кроме последнего, в последней строке которого стоит положительный элемент.

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

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

9

Генеральный элемент таблицы помечается знаком *.

Составление новой симплекс таблицы.

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

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

Остальные элементы генерального столбца заменяются нулями.

Для элемента s исходной таблицы находятся соответствующий ему

где p * – генеральный элемент.

Компактно это преобразование таблицы можно записать в виде формулы:

x1, x2 0

Решение. В этой задаче легко выделить базисные и свободные переменные. Полагая значения свободных переменных x1 , x2 нулю, найдем значение базисных перемен-

вим теперь (базисную) симплекс-таблицу в первом столбце, которой указаны имена базисных переменных. (Таблица 3.)

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

10