• Главная
  •  > 
  • Утилиты
  •  > 
  • Как называются последовательные симплекс таблицы. Решение задачи табличным симплекс-методом

Как называются последовательные симплекс таблицы. Решение задачи табличным симплекс-методом

3.1.
3.2.
3.3.
3.4.
3.5.
3.6. Пример(1) решения задачи ЛП методом симплекс-таблиц
3.7. Пример(2) решения задачи ЛП методом симплекс-таблиц

Идея метода симплекс-таблиц заключается в целенаправленном переборе вершин симплекса. Для начало перебора необходимо выбрать опорную вершину с которой начнется перебор. Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, (перебирая симплекс вершины) при котором значение целевой функции возрастает (убывает). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Для составления такого плана необходимо произвести векторный анализ, на основе которого определить опорную вершину, с которой начнется перебор. Система неравенств приводится к каноническому виду:

x 1 + a 1,m+1* x m+1 + ... + a 1s* x s +...+ a 1n * x n = b 1 ;

x 2 + a 2,m +1* x m+1 + ... + a 2s * x s +...+ a 2n* x n = b 2 ;

x m + a m,m+1* x m+1 + ... + a ms* x s +...+ a mn* x n = b m .

Переменные x 1 , x 2 ,...,x m , входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми - в остальные, называются базисными . В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Остальные n-m переменных (x m+1 , ...,x n) называются небазисными переменными.

3.1. Приведение математической модели к каноническому виду

Приведем математическую модель задачи к каноническому виду. Для этого избавимся от знаков неравенств посредством ввода дополнительных переменных и замены знака неравенства на знак равенства. Дополнительная переменная добавляется для каждого неравенства эксклюзивно, причем эта переменная указывается в целевой функции с нулевым коэффициентом. Правило ввода дополнительных переменых: при ">=" - переменная вводится в неравенство с коэффициентом +1; при "<=" - с коэффициентом (-1).

Причем иногда, когда в уравнении нет базисной переменной, чтобы сделать отрицательную дополнительную переменную базисной можно умножить все уравнение на (-1).

Также можно переориентировать целевую функцию с минимума на максимум или наоборот умножив все коэффициенты при переменных в этой функции на (-1).

3.2. Векторный анализ

При векторном анализе строятся вектора для каждой переменной: составляющими координатами n-мерного (n-количество уравнений системы) вектора будут коэффициенты этой переменной в соответствующих уравнениях.

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

3.3. Метод искусственных переменных

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

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

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

Этап 2. Допустимое базисное решение, найденное на первом этапе, улучшается в соответствии с целевой функцией исходной задачи ЛП на основе симплекс-метода, т.е. оптимальная таблица 1 этапа превращается в начальную таблицу этапа 2 и изменяется целевая функция.

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

Выбираем начальное допустимое базисное решение. Базисным решением называется решение, полученное при нулевых значениях небазисных переменных, т.е. x i =0, i=m+1,...,n. Базисное решение называется допустимым базисным решением , если значения входящих в него базисных переменных неотрицательны, т.е. x j = b j >=0, j=1,2,...,m. В этом случае целевая функция примет следующий вид: S = c b* x b = c 1* b 1 + c 2* b 2 +...+c m* b m . Заполняем первоначальную таблицу симплекс - метода:

Таблица 2.3

c b x b c 1 c 2 ... c m c m+1 ... c n b i
базис x 1 x 2 ... x m x m+1 ... x n
с 1 x 1 1 0 ... 0 a 1,m+1 ... a n b 1
с 2 x 2 0 1 ... 0 a 2,m+1 ... a 2 n b 2
... ... ... ... ... ... ... ... ... ...
c m x m 0 0 ... 1 a m,m+1 ... a m n b m
S

3.5. Анализ симплекс-таблицы

  1. Вычисляем вектор относительных оценок c при помощи правила скалярного произведения

c j = c j - c b* S j ,

где

с b - вектор оценок базисных переменных;

S j - j-тый столбец в канонической системе, соответствующей рассматриваемому базису.

Дополняем первоначальную таблицу c - строкой.

Таблица 2.4

базис x 1 x 2 ... x m x m+1 ... x n с 1 x 1 1 0 ... 0 a 1,m+1 ... a 1 n b 1 с 2 x 2 0 1 ... 0 a 2,m+1 ... a 2 n b 2 ... ... ... ... ... ... ... ... ... ... c m x m 0 0 ... 1 a m,m+1 ... a m n b m 0 0 ... 0 ... W
c b x b c 1 c 2 ... c m c m+1 ... c n b i
c- строка

3. Если все оценки c j <=0 (c j >= 0), i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение найдено.

4. Впротивном случае в базис необходимо ввести небазисную переменную x r с наибольшим значением c j вместо одной из базисных переменных (табл. 2.5).

  1. При помощи правила минимального отношения min(b i /a ir) определяем переменную x p , выводимую из базиса. Если коэффициент a ir отрицателен, то b i /a ir = бесконечность. В результате пересечение столбца, где находится вводимая небазисная переменная x r и строки, где находится выводимая базисная переменная x p определит положение ведущего элемента таблицы (табл. 2.6).

Таблица 2.5

c m+1

b i

базис

x m+1

с 1

a 1,m+1

a 1 r

a 1 n

с 2

a 2,m+1

a 2 r

a 2 n

a m,m+1

a m r

a m n

b m

c - строка

Таблица 2.6

c m+1

b i

b i /

a ir

x m+1

с 1

a 1,m+1

a 1 r

a 1 n

b 1 /a 1r

с 2

a 2,m+1

a 2 r

a 2 n

b 2 /a 2r

с p

a p,m+1

a pr

a pn

b p /a pr

a m,m+1

a m r

a m n

b m

b m /a nr

c - стро - ка

6. Применяем элементарные преобразования для получения нового допускаемого базового решения и новой таблицы. В результате ведущий элемент должен равняться 1, а остальные элементы столбца ведущего элемента принять нулевое значение.

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

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

      Первая строка, в отличие от столбца, сохраняется лишь в первой симплексной таблице. Начиная со второй итерации верхняя строка перестает быть обязательной.

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

    Второй столбец – р k (индеек k – номер итерации).

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

В первой симплексной таблице в столбце р 0 указываются номера всех дополнительных переменных.

3. Третий столбец – х 0 .

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

4. Значение целевой функции F k .

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

    Столбцы «основания матрицы».

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

В этих столбцах в первой симплексной таблице приводятся коэффициенты при неизвестных из уравнений исходных условий.

6. Последующие три столбца таблицы (, , ) имеют вспомогательное значения. Без этих столбцов можно обойтись, но они существенно облегчают проведение расчетов. Более подробно содержание этих столбцов будет рассматриваться ниже.

Пример

Рассмотрим симплексную задачу, записанную в общем виде:

Приведем задачу к канонической форме. Для этого в каждое из неравенств системы введем по одному неизвестному (дополнительному) – х 4 , х 5 . х 6 . Тогда

F = 15x 1 + 20x 2 +5x 3  max.

Заполним первую симплексную таблицу.

Мы заполним все клетки, исходя из условий задачи.

Чтобы заполнить клетку F 0 в первой таблице, необходимо просуммировать произведения элементов столбца х 0 на элементы столбца с 0 , т.е.

F 0 = 600∙0 + 520∙0 +600∙0 =0.

Чтобы заполнить целевую строку в первой таблице, необходимо соответствующее значение с j вычесть из суммы произведений элементов столбца х j на элементы столбца с 0 .

Для столбца х 1 величина двойственной оценки будет определяться

(0∙80+0∙15+0∙5) – 15=-15;

Для х 2: (0 35+0 60+0 5) – 20=-20;

х 3: (0 10+0 0+0 90) – 5=-5 и т.д.

В итоге первая симплексная таблица будет выглядеть так:

Таблица 1

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

Определение

Решение считается оптимальным , если все значения чисел в целевой строке положительны.

Если полученное решение не является оптимальным, то его можно улучшить. Для этого нужно:

1. Выбрать максимальное по абсолютной величине отрицательное значение числа в целевой строке.

В нашем примере таким числом будет (-20), находящееся в столбце «х 2 ». Именно это значение задает ключевой столбец .

Обратите внимание:

Ключевой столбец показывает, какое из х j войдет в новое решение задачи. В нашем случае - неизвестное х 2 .

Обратите внимания:

Чтобы включить в новое решение неизвестное х j , улучшающее это решение, необходимо вывести из базисного решения одно из х j , входящее в него.

2. Выбрать минимальное значение частного от деления элементов столбца х 0 на элементы ключевого столбца. Результаты этих расчетов заносятся в столбец «» симплексной таблицы.

В нашем примере эти отношения равны:

Минимальное значение соответствует х 5 и равно 8,67. Это отношение задает ключевую строку .

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

В нашем примере ключевой элемент равен 60 и находится на пересечении столбца х 2 и строки х 5 .

Обратите внимание:

Ключевым не может быть столбец, все элементы которого оказались отрицательными или нулевыми.

    Просуммировать элементы матрицы по строкам (начиная от столбца х 0 и кончая столбцом х 6). Полученные суммы записываются в столбец «».

    Преобразовать ключевую строку . Для этого

    1. Каждый элемент ключевой строки делится на ключевой элемент, начиная с элемента столбца «х 0 »;

Фрагмент

      В столбце р 1 записывается х 2 вместо х 5 ;

      В столбце с j записывается значение критерия оптимальности при х 2 , т.е. 20.

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

.

При пересчете величины функции цели получаем:

.

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

Таблица 2.

Как видно из табл. 2, оптимальное решение не получено, т.е. необходимо продолжить решение, используя все рассмотренные правила преобразования симплексных таблиц.

Примечание 1.

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

Примечание 2.

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

Самостоятельно дорешайте эту задачу. В результате должно получиться:

F=236.7; x 1 =3.31; x 2 =7.8; x 3 =6.05.

Примечание 3.

В столбце «» записываются частные от деления элемента в ключевом столбце и строке i на ключевой элемент.

Примечание 4.

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

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

Основное содержание симплексного метода заключается в следующем:
  1. Указать способ нахождения оптимального опорного решения
  2. Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения
  3. Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или следать заключение об отсутствии оптимального решения.

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

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:
  1. Привести задачу к каноническому виду
  2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
  3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
  4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
  5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

Пример решения задачи симплексным методом

Пример 26.1

Решить симплексным методом задачу:

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Δ k = C б X k — c k

  • C б = (с 1 , с 2 , ... , с m) — вектор коэффициентов целевой функции при базисных переменных
  • X k = (x 1k , x 2k , ... , x mk) — вектор разложения соответствующего вектора А к по базису опорного решения
  • С к — коэффициент целевой функции при переменной х к.

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

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

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

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

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

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

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

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

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

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

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

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

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

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

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

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

Понравилось? Добавьте в закладки

Решение задач симплекс-методом: примеры онлайн

Задача 1. Компания производит полки для ванных комнат двух размеров - А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В - 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В - 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В - 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

Задача 2. Решить задачу линейного программирования симплекс-методом.

Задача 3. Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.

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

Задача 4. Решить задачу линейного программирования симплексным методом:

Задача 5. Решить задачу линейного программирования симплекс-методом:

Задача 6. Решить задачу симплекс-методом, рассматривая в качестве начального опорного плана, план, приведенный в условии:

Задача 7. Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.

Задача 8. Найти оптимальное решение двойственным симплекс-методом

Лекция 3. Симплексные таблицы. Алгоритм симплексного метода.

§ 3 СИМПЛЕКСНЫЙ МЕТОД

3.1. Общая идея симплекс–метода. Геометрическая интерпретация

Графический способ применим к весьма узкому классу задач линейного программирования: эффективно им можно решать задачи, содержащие не более двух переменных. Были рассмотрены основные теоремы линейного программи­рования, из которых следует, что если задача линейного програм­мирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений систе­мы ограничений. Был указан путь решения любой задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограни­чений и выбрать среди них то, на котором функция цели прини­мает оптимальное решение. Геометрически это соответствует пе­ребору всех угловых точек многогранника решений. Такой пере­бор в конце концов приведет к оптимальному решению (если оно существует), однако его практическое осуществление связано с огромными трудностями, так как для реальных задач число допус­тимых базисных решений хотя и конечно, но может быть чрезвы­чайно велико.

Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы каждое следующее решение было "лучше" (или, по крайней мере, "не хуже"), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума , уменьшение– при отыскании минимума
). Такой перебор позволяет сократить число шагов при отыска­нии оптимума. Поясним это на графическом примере.

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

Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирова­ния – симплексного метода или метода последовательного улучшения плана.

Геометрический смысл симплексного метода состоит в последо­вательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение по отношению к цели задачи; до тех пор, пока не будет найдено оптимальное решение – вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.

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

Для реализации симплексного метода – последовательного улучшения решения – необходимо освоить три основных элемента:

способ определения какого-либо первоначального допустимого базисного решения задачи;

правило перехода к лучшему (точнее, не худшему) решению;

критерий проверки оптимальности найденного решения.

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

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

3.2. Алгоритм симплекс–метода.

Рассмотрим решение ЗЛП симплекс-ме­тодом и изложим ее применительно к задаче максимизации.

1. По условию задачи составляется ее математическая мо­дель.

2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.

3. Каноническая модель задачи записывается в форме симп­лекс-таблицы так, чтобы все свободные члены были неотрицатель­ными. Если начальный опорный план выделен, то переходят к пункту 5.

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

4. Находят начальный опорный план, производя симплексные преобразования с положительными разрешающими элементами, отвечающими минимальным симплексным отношениям, и не при­нимая во внимание знаки элементов
–строки. Если в ходе преоб­разований встретится 0-строка, все элементы которой, кроме сво­бодного члена, нули, то система ограничительных уравнений задачи несовместна. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то систе­ма ограничительных уравнений не имеет неотрицательных ре­шений.

Приведение системы (2.55), (2.56) к новому базису будем на­зывать симплексным преобразованием . Если симплексное преобра­зование рассматривать как формальную алгебраическую операцию, то можно заметить, что в результате этой операции происходит перераспределение ролей между двумя переменными, входя­щими в некоторую систему линейных функций: одна переменная из зависимых переходит в независимые, а другая наоборот – из независимых в зависимые. Такая операция известна в алгебре под названием шага жорданова исключения.

5. Найденный начальный опорный план исследуется на опти­мальность:

а) если в
–строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нуле­вых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;

б) если в
–строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то
;

в) если в
–строке есть хотя бы один отрицательный элемент, а в его столбце есть хотя бы один положительный, то можно пе­рейти к новому опорному плану, более близкому к оптимальному. Для этого указанный столбец надо назначить разрешающим, по минимальному симплексному отношению найти разрешающую строку и выполнить симплексное преобразование. Полученный опорный план вновь исследовать на оптимальность. Описанный процесс повторяется до получения оптимального плана либо до установления неразрешимости задачи.

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

Немного сложней определяется переменная, подлежащая ис­ключению из базиса. Для этого составляют отношения свободных членов к положительным элементам разрешающего столбца (та­кие отношения называют симплексными) и находят среди них наименьшее, которое и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, ис­ключаемой из базиса (или выбор разрешающей строки), по ми­нимальному симплексному отношению гарантирует, как уже уста­новлено, положительность базисных компонент в новом опорном плане.

В пункте 3 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование не обя­зательно, но если оно выполнено, то все последующие симплексные преобразования производятся только с положительными разре­шающими элементами, что удобно при расчетах. Если в столбце свободных членов есть отрицательные числа, то разрешающий элемент выбирают следующим образом:

1) просматривают строку, отвечающую какому-либо отрица­тельному свободному члену, например –строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему стол­бец принимают за разрешающий (предполагаем, что ограничения задачи совместны);

2) составляют отношения элементов столбца свободных чле­нов к соответствующим элементам разрешающего столбца, имею­щим одинаковые знаки (симплексные отношения);

3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р –строка;

4) на пересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающим оказался элемент –строки, то после симплексного преобразования свободный член этой строки станет положительным. В противном случае на сле­дующем шаге вновь обращаются к–строке. Если задача разреши­ма, то через некоторое число шагов в столбце свободных членов не останется отрицательных элементов.

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