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

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

Базисным решением называют такое решение, в котором все свободные переменные равны нулю.

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

Этапы СМ:

1) Определяют опорное решение.

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

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

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

                                       (2.6)

                                                  (2.7)

где  – постоянные. При этом СТ имеет вид табл. 2.1.

Таблица 2.1 – Симплекс-таблица

Б  С	Свободный член	Х1	X2	...	Xr	...	Xn
W	C0			...	g r	...	g n
Y1	B1			...	a 1r	...	a 1n
Y2	B2			...	a 2r	...	a 2n
. .	. .	. .	. .		. .		. .
Ys	Bs	a s1	a s2	...	a sr	...	a sn
. .	. .	. .	. .		. .		. .
Ym	Bm	a m1	a m2	...	a mr	...	a mn

 

При заполнении СТ могут возникнуть несколько ситуаций:

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

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

Для этого сначала находят опорное решение, когда свободные члены СТ (кроме W) станут положительными, по следующим правилам:

1) Выбрать одно любое из уравнений-ограничений (2.6) с отрицательным свободным членом.

2) В этой строке СТ найти отрицательный элемент. Если такого элемента нет, это признак того, что система уравнений-ограничений несовместима.

3) Выбрать любой отрицательный элемент этой строки, тем самым выбирается разрешающий столбец.

4) Выбрать в этом столбце сам разрешающий элемент следующим образом:

– рассмотреть все элементы данного столбца, имеющие одинаковый знак со «своим» свободным членом;

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

При достижении опорного решения находят оптимальное решение ОЗЛП СМ по следующим правилам:

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

2) Если в этом столбце есть положительные элементы, то следует выбрать разрешающий элемент по выше рассмотренному правилу.

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

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

1) Выделить в таблице разрешающий элемент  по выше рассмотренному правилу.

2) Вычислить его обратную величину  и записать в правом нижнем углу той же ячейки.

3) Все элементы разрешающей строки (кроме самого ) умножить на , результат записать в правом нижнем углу той же ячейки.

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

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

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

7) Переписать симплекс-таблицу, заменив:

– соответствующие разрешающему элементу свободную на базисную переменную и наоборот;

– элементы разрешающей строки и столбца – числами, стоящими в нижних правых углах тех же ячеек;

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

 

На основании выше сказанного можно схематично изобразить алгоритм симплекс-метода.

 

 

АЛГОРИТМ СИМПЛЕКС-МЕТОДА

 

Заполнение СТ по станд. форме записи ЗЛП: ,

где: - свободные члены; - введенные переменные в для знака равенства

 

                       Опорное решение                      да                         Оптимальное решение           да

                      ()                                                   ()

                                          нет                                                                                   нет   

        Выбор разрешающего столбца :                             Выбор разрешающего столбца :

                                                       

 

Выбор разрешающего элемента:

 

Нахождение новых значений СТ:

 

Заполнение новой СТ: оставшиеся ячейки СТ -

суммой чисел, старых и новых значений соответствующих ячеек

 

 

Получение оптимального решения:

Пример решения ЗЛП симплекс-методом

 

Пример 2.1. Предприятию необходимо изготовить три вида продукции А, В, С и D, с использованием трех видов ресурсов R ₁, R ₂, R ₃ количество которых ограничено. Исходные данные задачи представлены в таблице:

 

Вид ресурсов	Количество ресурсов, идущих на изготовление единицы продукции				Запасы ресурсов
	А	В	С	D
R1	4	2	3	1	116
R2	2	0	3	2	94
R3	4	1	0	5	196
Доходы от реализации продукции	48	15	11	32

 

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

Решение.

Обозначим через х₁, х₂ и x₃ количество единиц продукции видов А, В, С и D, планируемых к выпуску.

Известно, что доход от реализации единицы продукции А составляет 48 усл.ед. и количество этой продукции – х₁. Следовательно, доход от реализации всей продукции А составит 48 х ₁ усл.ед. Аналогично, доход от реализации всей продукции В составит 15 х₂ усл.ед., продукции С – 11 х₃ усл.ед., продукции D – 32 х₄ усл.ед. Учитывая, что доход от реализации продукции должен быть максимальным, целевая функция задачи будет иметь вид:

 

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

 

 

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

 

 

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

 

Необходимо максимизировать целевую функцию, используя симплекс-метод решения ЗЛП.

 

Решение.

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

Получили число всех переменных n=7, число уравнений-ограничений m=3, число свободных членов k=n-m=7-3=4. В качестве свободных членов выберем x₁, x₂, x₃ и x₄ и выразим через них базисные переменные y₁, y₂ и y₃ и целевую функцию Z_max(X^*), для чего найдем minL = max(-Z).

2. Перепишем уравнения целевой функции и ограничения в стандартной форме:

Откуда

3. Заполним первую симплекс-таблицу по исходным данным, записанным в стандартной форме.

	Свободный член	x1^R	x2	x3	x4
L	0 -1392	48 -12	15 -24	11 -36	32 -12
y1^R	116 29	4 1/4	2 1/2	3 3/4	1 1/4	116/4=29
y2	94 -58	2 -1/2	0 -1	3 -3/2	2 -1/2	94/2=47
y3	196 -116	4 -1	1 -2	0 -3	5 -1	196/4=49

 

Т.к. все свободные члены таблицы больше нуля, то имеется опорное решение задачи. Но решение не оптимально, т.к. все коэффициенты целевой функции больше нуля. Для поиска оптимального решения в качестве разрешающего столбца выберем столбец x₁, т.к. он имеет максимальное значение коэффициента целевой функции равное 48. В качестве разрешающего элемента выберем элемент 2-й строки со значением 4, т.к. он имеет минимальное отношение свободного члена к данному элементу. Соответственно разрешающей строкой будет строка y₁. Преобразуем первую симплекс-таблицу в соответствии с алгоритмом: делим единицу на разрешающий элемент, элементы разрешающей строки делим на разрешающий элемент, элементы разрешающего столбца делим на разрешающий элемент и меняем знак. Остальные элементы находятся как произведение выделенных элементов разрешающей строки на соответствующие выделенные элементы разрешающего столбца. Внесем в таблицу необходимые данные, после чего построим вторую симплекс-таблицу.

4. Строим и заполняем вторую симплекс-таблицу, поменяв при этом местами свободную переменную x₁ с базисной переменной y₁.

	Свободный член	y1	x2	x3	x4^R
L	-1392 -400	-12 5	-9 5	-25 15	20 -5
x1	29 -5	1/4 1/16	1/2 1/16	3/4 3/16	1/4 -1 /16	29/(1/4)=116
y2	36 -30	-1/2 3/8	-1 3/8	3/2 9/8	3/2 -3/8	36/(3/2)=24
y3^R	80 20	-1 -1/4	-1 -1/4	-3 -3/4	4 1/4	80/4=20

 

Т.к. свободные члены таблицы больше или раны нулю, то имеется опорное решение задачи. Но решение не оптимально, т.к. не все коэффициенты целевой функции меньше нуля. Для поиска оптимального решения в качестве разрешающего столбца выберем столбец x₄, т.к. он имеет максимальное значение коэффициента целевой функции равное 20. В качестве разрешающего элемента выберем элемент 4-й строки со значением 4, т.к. он имеет минимальное отношение свободного члена к данному элементу. Соответственно разрешающей строкой будет строка y₃. Преобразуем вторую симплекс-таблицу в соответствии с алгоритмом, внесем в нее необходимые данные, после чего построим вторую симплекс-таблицу.

5. Строим и заполняем третью симплекс-таблицу, поменяв при этом местами свободную переменную x₄ с базисной переменной y₃.

	Свободный член	y1	x2	x3	y3
L	-1792	-7	-4	-10	-5
x1	24	5/16	9/16	15/16	-1/16
y2	6	-1/8	-6/8	21/8	-3/8
x4	20	-1/4	-1/4	-3/4	1/4

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

Имеем следующие значения свободных переменных:

x₁ = 24, x₂ = 0, x₃= 0, x₄ = 20.

Отсюда:

 

Пример 2.2. Предприятию необходимо изготовить два вида продукции А и В, с использованием трех видов ресурсов R ₁, R ₂, R ₃ количество которых ограничено. Исходные данные задачи представлены в таблице:

 

Вид ресурсов	Количество ресурсов, идущих на изготовление единицы продукции		Запасы ресурсов
	А	В
R1	6	6	36
R2	4	2	20
R3	4	8	40
Доходы от реализации продукции	12	15

 

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

Решение.

Обозначим через х₁ и х₂ количество единиц продукции видов А и В, планируемых к выпуску.

Известно, что доход от реализации единицы продукции А составляет 12 усл.ед. и количество этой продукции – х₁. Следовательно, доход от реализации всей продукции А составит 12 х ₁ усл.ед. Аналогично, доход от реализации всей продукции В составит 15 х₂ усл.ед. Учитывая, что доход от реализации продукции должен быть максимальным, целевая функция задачи будет иметь вид:

 

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

 

 

Смысл первого ограничения состоит в том, что фактический расход ресурса R ₁ на производство продукции А и В, равный 6 х ₁+6 х ₂ (здесь 6 х ₁ – количество единиц ресурса R ₁, идущего на изготовление х ₁ единиц продукции A; 6 х ₂ – количество единиц ресурса R ₁, идущее на изготовление х ₂ единиц продукции В) не должен превышать запаса этого ресурса на предприятии, равного 36 ед. Аналогичный смысл имеют 2-е и 3-е ограничения только для ресурсов R ₂ и R ₃ соответственно.

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

 

 

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

 

 

Решение.

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

Получили число всех переменных n=5, число уравнений-ограничений m=3, число свободных членов k=n-m=5-3=2. В качестве свободных членов выберем x₁, x₂ и выразим через них базисные переменные y₁, y₂ и y₃ и целевую функцию Z_max(X^*), для чего найдем minL = max(-Z).

2. Перепишем уравнения целевой функции и ограничения в стандартной форме:

 

Откуда

 

3. Заполним первую симплекс-таблицу по исходным данным, записанным в стандартной форме.

	Свободный член	x1	x2^R
L	0 -75	12 - 7, 5	15 - 15/8
y1	36 -30	6 -3	6 -6/8=- 3/4	36/6=6
y2	20 -10	4 -1	2 -2/8= -1/4	20/2=10
y3^R	40 40/8=5	4 4/8=1/2	8 1/8	40/8=5

 

Т.к. все свободные члены таблицы больше нуля, то имеется опорное решение задачи. Но решение не оптимально, т.к. все коэффициенты целевой функции больше нуля. Для поиска оптимального решения в качестве разрешающего столбца выберем столбец x₂, т.к. он имеет максимальное значение коэффициента целевой функции равное 15. В качестве разрешающего элемента выберем элемент 4-й строки со значением 8, т.к. он имеет минимальное отношение свободного члена к данному элементу. Соответственно разрешающей строкой будет строка y₃. Преобразуем первую симплекс-таблицу в соответствии с алгоритмом: делим единицу на разрешающий элемент, элементы разрешающей строки делим на разрешающий элемент, элементы разрешающего столбца делим на разрешающий элемент и меняем знак. Остальные элементы находятся как произведение выделенных элементов разрешающей строки на соответствующие выделенные элементы разрешающего столбца. Внесем в таблицу необходимые данные, после чего построим вторую симплекс-таблицу.

4. Строим и заполняем вторую симплекс-таблицу, поменяв при этом местами свободную переменную x₂ с базисной переменной y₃.

	Свободный член	x1^R	y3
L	-75 -9	4,5 -4,5/3= -1,5	-15/8 -1,12
y1^R	6 6/3=2	3 1/3	-3/4 -3/4/3=-1/4	6/3=2
y2	10 -6	3 -3/3= -1	-1/4 3/4	10/3=3,3
x2	5 -1	1/2 -1/2/3= -1/6	1/8 1/8	5/1/2=10

 

Т.к. свободные члены таблицы больше или раны нулю, то имеется опорное решение задачи. Но решение не оптимально, т.к. не все коэффициенты целевой функции меньше нуля. Для поиска оптимального решения в качестве разрешающего столбца выберем столбец x₁, т.к. он имеет максимальное значение коэффициента целевой функции равное 4,5. В качестве разрешающего элемента выберем элемент 2-й строки со значением 3, т.к. он имеет минимальное отношение свободного члена к данному элементу. Соответственно разрешающей строкой будет строка y₁. Преобразуем вторую симплекс-таблицу в соответствии с алгоритмом, внесем в нее необходимые данные, после чего построим вторую симплекс-таблицу.

5. Строим и заполняем третью симплекс-таблицу, поменяв при этом местами свободную переменную x₄ с базисной переменной y₃.

	Свободный член	y1	y3
L	-84	-1,5	-2,99
x1	2	1/3	-1/4	6/3=2
y2	4	-1	1/2	10/3=3,3
x2	4	-1/6	1/4	5/1/2=10

 

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

Имеем следующие значения свободных переменных:

x₁ = 2, x₂ = 4.

Отсюда: