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

 

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

Рассмотрим алгоритм симплексного метода на примере задачи планирования товарооборота.

Коммерческое предприятие реализует “n” товарных групп, располагая “m” ограниченными материально-денежными ресурсами в_i 0 (i = 1, 2, …..m). Известны расходы ресурсов каждого i –го вида на реализацию единицы товара по каждой группе, представленной в виде матрицы А=(а _ij), и прибыль “C j ”, получаемая предприятием от реализации единицы товара “j” группы. Надо определить объем и структуру товарооборота “хj” (j = 1, 2, …,n), при которых прибыль коммерческого предприятия была бы максимальной.

Математическую модель задачи запишем следующим образом. Определить вектор Х =(х₁, х₂, …х_n), который удовлетворяет ограничениям вида:

 

a _ij * х_j в_i, i = 1,2 …m (1)

х_j 0, j = 1,2 …..n (2)

 

и обеспечить максимальное значение целевой функции

f(х) = Сj * Хj mах (3)

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

 

 

Виды материально-денежных ресурсов	Норма затрат материально-денежных ресурсов на 1 тыс. руб. товарооборота	Объем ресурсов (вi)
группа А	группа В	группа С
Рабочее время продавцов, чел-ч	0,1	0,2	0,4	1 100
Площадь торговых залов, м2	0,05	0,02	0,02
Площадь складских помещений, м2				8 000
Доход, тыс. руб. (Сj)				mах

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

Переменные:

х₁ – количество товаров группы А, ед.

х₂ – количество товаров группы В, ед.

х₃ – количество товаров группы С, ед.

Ограничения:

1) По использованию рабочего времени продавцов, чел-ч. 0,1х₁+0,2х₂+0,4х₃ 1100

2) По использованию площадей торговых залов, м² 0,05х₁+0,02х₂+0,02х₃ 120

3) По использованию площадей складских помещений, м² 3х₁+х₂+2х₃ 8000

4) Условие не отрицательности переменных х₁ 0, х₂ 0, х₃ 0.

Целевая функция:

Максимальное значение целевой функции, тыс. руб.

f(х) = 3х₁+5х₂+4х₃ mах

 

Алгоритм симплексного метода включает следующие этапы:

1.Составление первого опорного плана

 

Система ограничений задачи, решаемой симплексным методом задана в виде неравенств смысла “ ”, правые части которых в_i 0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных х₄; х₅; х₆; которые образуют базис и называются базисными переменными и определяют объемы неиспользованных ресурсов:

0,1х₁+0,2х₂+0,4х₃ + х₄ = 1100

0,05х₁+0,02х₂+0,02х₃+х₅ = 120

3х₁+х₂+2х₃+х₆ = 8000

 

Матрица коэффициентов А=(а _ij) этой системы уравнений имеет вид:

А = 0,1	0,2	0,4
0,05	0,02	0,02

Решим систему уравнений относительно базисных переменных:

х₄ = 1100 – (0,1х₁+0,2х₂+0,4х₃)

х₅ = 120 – (0,05х₁+0,02х₂+0,02х₃)

х₆ = 8000 – (3х₁+х₂+3х₃)

Функцию цели запишем в виде уравнения f(х) = 0 – (-3х₁ – 5х₂ – 4х₃). Полагая что основные переменные х₁=0 х₂=0 х₃=0, получим первый опорный план, х₄= в ₁; х₅= в ₂; х₆= в ₃ f(x) =0; который заносим в симплексную таблицу № 1. Она состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком:

План	Базисные переменные	Свободные члены	Основн. перемен.	Допол.перем.	i
х1	х2	х3	х6	х5	х6
I	х4		0,1	0,2	0,4
х5		0,05	0,02	0,02
х6
Индексная строка	f(x)		-3	-5	-4

 

2. Проверка плана на оптимальность

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

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

Первый опорный план, представленный в первой симплексной таблице неоптимальный, т.к. в индексной строке находятся отрицательные коэффициенты: -3; -5; -4.

Полагая что основные переменные х₁=0; х₂=0;х₃=0, а дополнительные переменные х₄=1100; х₅=120; х₆=800; f(x)=0. Следовательно, товары не продаются, а ресурсы не используются, доход равен нулю. В этом случае переходим к следующему этапу алгоритма.

3. Определение ведущих столбца и строки

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

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

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

За ведущий столбец выберем столбец, соответствующий переменной х_2, т.к. сравнивания по модулю [-5] >[-3]; [-4].

Вычислим значения _i по строкам и выберем наименование 1100/0,2 = 5500(min); 120/0,02=6000; 8000/1=8000; следовательно, строка х₄ является ведущей.

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

4. Построение нового плана.

Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо (х _i) (х₄) в базис войдет переменная (х _j) (х₂) соответствующая ведущему столбцу.

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

(х₂) 1100/0,2=5500; 0,1/0,2=0,5; 0,2/0,2=1;0,4/0,2=2;1/0,2=5.

2. Все остальные других строк определяются по формуле:

нов.коэфф.=соотв.коэфф.пред.табл. – (коэфф.ведущ.столбца х коэфф.нач.строки нов. плана)

Выполняя последовательно все этапы алгоритма, составляем план 2:

План	Базисные переменные	Свободные члены	Основн. перемен.	Допол.перем.	2
х1	х2	х3	х4	х5	х6
II	х2		0,5
х5		0,04		-0,02	-0,1
х6		2,5			-5
Индексная строка	f(x2)	27 500	-0,5

Анализ второго плана: План не оптимальный т.к. в индексной строке имеется отрицательный коэффициент (-0,5). Максимальный доход в размере 25.500 руб. торговое предприятие получит от продажи товаров второй группы В 5500 ед. (х₂). Среди базисных переменных находится дополнительные переменные х₅и х₆. Это указывает на то, что ресурсы второго вида (площадь торговых залов) недоиспользована на 10 м² и ресурсы третьего вида (площадь складских помещений) недоиспользованы на 2500 м² .

На третьей итерации получаем план 3, который является оптимальным т.к. все коэффициенты в индексной строке 0.

 

План	Базисные переменные	Свободные члены	Основн. перемен.	Допол.перем.	2
х1	х2	х3	х4	х5	х6
III	х2				2.25	6,25	12,5
х1				0,5	-2,5
х6				1,25	1,25	62,5
Индексная строка	F(x3)	27 625			5,75	23,75	12,5

 

Анализ третьего плана: Необходимо продавать товаров первой группы А 250 ед., а второй группы В 5375 ед. При этом торговое предприятие получает максимальный доход в размере 27625 тыс. руб. Товары группы С не реализуются.

В оптимальном плане среди базисных переменных находится дополнительная переменная х₆. Это указывает, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м², т.к. переменная х₆ была введена в третье ограничение задачи, характеризующее собой использование складских помещений этого ресурса.