Simplex

Симплекс-метод. Методические указания для самостоятельной работы по

дисциплине «Математические методы исследования операций» для студентов

специальности «Информационные управляющие системы и технологии» / Сост.: Е.Г.

Жданова. – К.: НТУУ “КПИ”, 2010. – 47 с.

Учебное издание

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для самостоятельной работы

по дисциплине «Математические методы исследования операций»

для студентов специальности

«Информационные управляющие системы и технологии»

2

Методические указания содержат теоретические основы симплекс-метода – основного метода решения задач линейного программирования. Приведены основные теоремы линейного программирования, схемы алгоритмов симплексметода и табличного симплекс-метода. Рассмотрены методы нахождения начального допустимого базисного решения, особые случаи использования симплекс-метода. Приведены примеры решения задач линейного программирования и задания для контрольных работ.

Содержание

3

ЗЛП вида:

n

∑c j x j →MAX(MIN);

j=1 n

∑aij x j =bi , i =1,m;

j=1

x j ≥ 0, j =1,n

называется канонической ЗЛП. Она может быть записана в матричном виде следующим образом:

cT x → MAX(MIN);

Ax = b; x ≥ 0.

Метод решения ЗЛП разработан для задачи в канонической форме.

2. Эквивалентность различных форм ЗЛП

Все перечисленные формы ЗЛП являются эквивалентными в том смысле, что простыми преобразованиями задачу, имеющую одну из форм, легко привести к задаче, имеющей одну из оставшихся форм, причем по оптимальному решению построенной задачи легко найти оптимальное решение исходной задачи. Следовательно, различные формы ЗЛП по существу являются различными формами записи ЗЛП.

Правила преобразования различных форм ЗЛП:

а) максимизация целевой функции ∑c j x j эквивалентна минимизации j

целевой функции − ∑c j x j ; j

б) ограничение-неравенство «≤» с помощью введения неотрицательной переменной можно заменить системой:

где si – остаточная переменная;

в) ограничение-неравенство «≥» с помощью введения неотрицательной

переменной можно заменить системой:

5

Второе ограничение также имеет знак “≥”, для приведения к канонической

форме в левую часть ограничения вводим избыточную переменную s2:

–2x1 + 7x2 – s2 = 8, s2 ≥ 0.

Так как третье ограничение имеет знак “≤”, то в левую часть ограничения добавляем остаточную переменную s3:

3x1 – 8x2 + s3 = 15, s3 ≥ 0.

Так как четвёртое ограничение имеет знак “=”, то ограничение оставляем без изменения, не добавляя дополнительных переменных. Данное ограничение в канонической форме имеет исходный вид:

-4x1 + x2 = 10.

Итак, в канонической форме данная ЗЛП будет выглядеть так:

z = 3x1 – x2 + 0s1 + 0s2 + 0s3→ MAX

Пример 2.2

Привести ЗЛП к ЗЛП в канонической форме, в которой направление оптимизации - максимизация:

z = 3x1 – 5x2 → MIN, 4x1 + 7x2 ≤ 6, 5x1 + 2x2 ≥ 8, 3x1 – 3x2 ≥ 5,

x1 , x2 ≥ 0.

Решение

Для изменения направления оптимизации нужно умножить целевую функцию задачи на (–1)). В первое ограничение введём остаточную переменную, а в два последних – избыточные переменные. Каноническая форма задачи выглядит таким образом:

z = –3x1 + 5x2 + 0s1 + 0s2 + 0s3→ MAX,

В этом случае на переменную x2 не накладывается ограничение неотрицательности. Введя две новые неотрицательные переменные x2+≥0, x2–≥0,

исходную переменную x2 можно исключить путём замены: x2 = x2+ – x2–.

Целевая функция будет иметь вид:

MAX z = 13x1 – 20(x2+ – x2–).

После раскрытия скобок:

MAX z = 13x1 – 20x2+ + 20x2–.

Так как первое ограничение имеет знак “≤”, то в левую часть ограничения

вводим остаточную переменную s1, а вместо переменной x2 подставляем разность: x2+ – x2–. Получим систему:

x1 + 2x2+ – 2x2– + s1 = 6, s1 ≥ 0.

Второе ограничение имеет знак “≥”, значит в левую часть ограничения вводим избыточную переменную s2, а вместо переменной x2, как в и предыдущем

ограничении, подставляем разность:

-2x1 + 7x2+ – 7x2– – s2 = 8, s2 ≥ 0.

Итак, каноническая форма после всех преобразований имеет вид:

MAX z = 13x1 – 20x2+ + 20x2– + 0s1 + 0s2 → MAX,

8

Упражнения

1) Укажите, какая из ниже приведенных форм задач является канонической?

2)Укажите, какая из ниже приведенных задач является стандартной формой задачи линейного программирования(ЗЛП).

9

3. Основные свойства ЗЛП

Для ЗЛП справедлива следующая теорема.

Теорема (о существовании решения). Если допустимое множество X

ЗЛП не пусто, а значение её конечно, то эта задача имеет решение.

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

Определение. Многогранником называется ограниченное многогранное множество.

Множество допустимых решений ЗЛП представляет собой многогранное множество.

Теорема. Пусть допустимое множество X ЗЛП MAX cTx, x X является многогранником. Тогда ЦФ cTx достигает своего максимума в вершине X. Если

функция cTx принимает максимальное значение более чем в одной точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией [5].

Из этой теоремы вытекает, что множество оптимальных точек не может быть конечным, если оптимальная точка не единственна [9].

Алгебраическая запись ЗЛП в канонической форме такова:

z = c1x1 + c2 x2 +K+ cn xn → max; a11x1 + a12 x2 +K+ a1n xn = b1;

Пусть задача (6) имеет допустимые решения и ранг матрицы A равен m

(числу ограничений-равенств). Это предположение о ранге практически не является ограничивающим. Этого можно добиться, исключив из системы Ax=b линейно

зависимые уравнения.

Кроме того, будем считать, что n>m, т.к. случай n=m не представляет интереса, а соотношение n<m невозможно, так как в этом случае ранг не может

быть равен m.

Задачу (6) можно трактовать следующим образом: из всех представлений

вектора b в виде линейной комбинации векторов с неотрицательными

10