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

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

Допустимым решением задачи ЛП назовем всякое решение системы ограничений (4.3), удовлетворяющее условиям не отрицательности

Хj ³ 0 , j = .

В производственных задачах, математические модели которых исследуются методами ЛП, всегда на переменные Xj(j = ) накладывается требование не отрицательности переменных .

Симплекс - метод основан на том, что если в матрице ограничений имеется m строк и они линейно независимы, то существует набор из m столбцов, называемых базисными, которые также линейно независимы. Совокупность значений переменных, соответствующих базисным столбцам, называется базисным решением (опорным решением, опорным планом). Если в системе ограничений - уравнений содержится n переменных Xj ( j = ) и ранг ее равен m, то в симплексном методе на каждой итерации отыскиваются значения m базисных переменных, удовлетворяющих m линейным ограничениям, а остальные n - m переменных называются свободными и полагаются равными нулю.

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

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

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

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

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

Если в системе ограничений содержатся неравенства, то каждое неравенство нужно преобразовать в уравнение путем введения дополнительных или балансовых переменных. Они вводятся по одной переменной в каждое неравенство со знаком «+», если неравенство имеет знак £, и со знаком «-», если неравенство имеет знак ³. Обычно нумерация балансовых переменных продолжает нумерации основных переменных задачи. Эти же переменные с нулевыми коэффициентами вводятся в целевую функцию.

Исходную систему уравнений полезно записать в векторной форме:

 

1Х1 + 2Х2 + .... + nXn = , где

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

Если нет таких векторов, то можно использовать один из следующих способов:

1. Произвести m преобразований по схеме Жордана - Гаусса системы ограничений (4.3) для разрешения относительно m любых переменных. В результате получим в матрице системы (4.3) m базисных вектор - столбцов j, т.е. векторов, у которых одна координата равна 1, а другие - нулю, причем единицы находятся в различных строках матрицы. Соответствующие базисные переменные записывают в столбец баз первой симплексной таблицы.

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

3. Если в исходной системе ограничений неравенств имеются знаки ³, то балансовые переменные вводятся в левую часть неравенства со знаком «-». Соответствующий вектор - столбец такой переменной будет иметь следующие координаты:

В этом случае будет недоставать векторов, координаты которых могут образовать единичную матрицу Е для первого базиса. В каждое такое неравенство вместе с балансовой переменной вводится еще одна переменная (искусственная): Хα1, Хα2 , .... .

На эти переменные тоже налагается требование не отрицательности:Хα1 ³ 0, Хα2 ³ 0, ... .

В целевую функцию в этом случае вводится дополнительное слагаемое вида: ± М (Хα1 + Хα2+ ... + Хαm), где знак « + » используется в задачах на минимум (F®min), знак « - » в задачах на максимум (F®max). М ³0 - очень большое число. В расчетах на ЭВМ обычно принимают М = 1017 .

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

Хα1 = 0 , Хα2 = 0 , ... , Хαm = 0.

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

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

Таблица 4. 1

Исходная информация задачи

Вид товара Вид ресурса   А   Б   В   Г Объем ресурсов
Сырье 1 вида, кг
Сырье 2 вида, кг
Оборудование, станко - ч
Рабочая сила, ч .
Прибыль на единицу товара, ден. ед.  

Известны затраты ресурсов на изготовление единицы каждого вида товара, запасы ресурсов, а также величина прибыли, получаемая предприятием за единицу товара (табл. 4.1.).

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

Решение

Введем переменные х1, х2, х3, х4, - соответственно количество производимого товара вида А, Б, В, Г, тогда математическая модель запишется в виде

П = 30 х1 + 25 х2 + 50 х3 + 40 х4 ® max

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

хj ³ 0, j =

Для решения задачи симплекс - методом преобразуем неравенства в уравнения, получим :

П = 30 х1 + 25 х2 + 50 х3 + 40 х4 + 0 х5 + 0 х6 + 0 х7 + 0 х8 ® max

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

хj ³ 0, j =

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

Первую симплексную таблицу заполняют следующим образом :

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

2. В столбцы 1, 2, ..., n выписывают коэффициенты при переменных х1, х2, ...., хn в уравнениях системы ограничений.

3. В столбец записывают правые части уравнений системы ограничений.

4. В столбец баз вписывают те векторы, координаты которых образуют единичную матрицу Е (базис.).

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

6. Нижняя строка таблицы Zj - Cj = jбаз∙ j - Cj называется индексной строкой или строкой оценок и служит для проверки полученного в очередной таблице решения на оптимальность.

Первый план симплексной таблицы - первый опорный план задачи :

х1 = 0, х2 = 0, х3 = 0 , х4 = 0, х5 = 360, х6 = 400, х7 = 134, х8 = 96

Это соответствует тому, что ничего не производится, ресурсы не используются, прибыль - целевая функция равна нулю и не основные переменные принимают свои предельные значения. С геометрической точки зрения получены координаты вершины многогранника (0, 0, 0, 0, 360, 400, 134, 96).

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

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

Определим, в каком количестве предусмотрен выпуск товара В, это зависит от объема ресурсов и нормативов их затрат. Сырья 1 вида достаточно на 180 единиц товара В (360 кг : 2 кг). Сырья 2 вида - на 20 единиц товара В (400 : 20). Фонда времени оборудования хватит на 16 (134 : 8) единиц, рабочей силы - 8 (96 : 12 ) единиц товара В. Очевидно, что больше 8 единиц товара В изготовить не удастся. Поэтому переменная х3 в плане равна 8 и вводится на место переменной х8, которая исключается из базиса и принимает нулевое значение. Подчеркнем число 12, находящееся на пересечении столбца 3 вводимой переменной х3 и строки х8 выводимой переменной.

Это число называется разрешающим, ключевым, направляющим элементом.

Рассмотрим второй этап расчета таблицы 4. 2. Прежде всего, рассчитывается строка вводимой переменной, отмеченная в таблице стрелкой. Эта строка получается из строки х8 исходного варианта путем деления всех элементов на направляющий элемент, так как в этом отношении (1 : 12) переменная х3 замещает переменную х8. В столбце баз проставляется прибыль за единицу товара В (50).

После расчета строки х3 пересчитывается столбец ресурсов .

Сырье 1 вида уменьшится, первоначально оно составляло 360 кг, на каждую единицу сырья товара В затрачивается 2 кг , всего производится (96 : 12) 8 единиц товара В, следовательно, остающееся неиспользованное сырье 1 вида составит 344 кг, т.е. 360 - 96/12∙2 = 344 .

Аналогично: 400 - 96/12∙20 = 240 кг - неиспользованное сырье 2 вида, 134 - 96/12∙8 = 70 станко - ч. - остающийся неиспользованным фонд времени оборудования.

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

Схема пересчета (правило Жордана - Гаусса)

------аij------------------ аis------ i – строка

 

------ аrj------------------ аrs------ r – разрешающая строка

j – столбец s– столбец

Элемент аij после пересчета по правилу Жордана - Гаусса превращается в элемент а’ij, где .

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

Таблица 4.2

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

Баз. пер. Cjбаз
1 2 3 4 5 6 7 8
х5
х6
х7
х8
Пj - Cj   - 30 -25 - 50 - 40
х5 3,5 3, 5 - 1/ 6
х6 -1 - 5/ 3
х7 - 2/ 3
→х3 0, 5 0,75 0, 25 1/12
Пj – Cj   - 5 12,5 - 27, 5 25/ 6
х5 319,5 - 0, 1 0,7 - 0, 35 1/ 15
х6 - 5 -21 - 2, 5
→х4 0, 6 0,8 0, 1 - 1/ 15
х3 6,25 0, 35 0,55 - 0, 025 0, 1
Пj - Cj   592,5 11, 5 34, 5 2, 75 7/3

Элементы в индексной строке можно рассчитывать либо непосредственно по формуле jбаз∙ j – Сj, либо по правилу Жордана - Гаусса. Одно из правил следует использовать для расчета, другое - в качестве контроля. В результате получим второй опорный план: х1 = 0, х2 = 0, х3 = 8 , х4 = 0, х5 = 344, х6 = 240, х7 = 70, х8 = 0 и значение прибыли - 400 д. ед. С геометрической точки зрения совершен переход в вершину многогранника с координатами (0,0,8,0,344,240,70,0). Затем необходимо проверить данный план на оптимальность. Для этого просматривается индексная строка и, если она содержит отрицательные элементы, то план можно улучшить. Как видим, она содержит два отрицательных числа, которые указывают что прибыль может быть увеличена введением в базис переменной х1 или х4. Переменная х4 вводится в базис, так как ей соответствует наибольшее по абсолютной величине отрицательное число – 27,5.

Если по индексной строке определен ключевой столбец j, в котором все элементы отрицательны, то задача ЛП не имеет решения.

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

х1 = 0, х2 = 0, х3 = 6,25, х4 = 7, х5 = 319,5, х6 = 65, х7 = 0, х8 = 0, т.е. в данных условиях производства нельзя получить прибыли более 592,5 д. ед. При этом выпуск товара В должен составлять 6,25 единицы и товара Г- 7 единиц, остаток сырья первого вида 319,5 кг и второго вида - 65 кг .