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

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

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

1. Математическая формализация задачи;

2. Приведение системы ограничений к каноническому виду;

3. Поиск опорного решения и нахождение базиса задачи;

4. Построение первой симплексной таблицы;

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

6. Последовательное улучшение плана до получения оптимального.

Рассмотрение всех этапов нагляднее всего проводить на конкретном примере.

ПРИМЕР

Планируется выпустить два вида продукции. Для производства единицы продукции первого вида требуется 12 кг сырья первого вида, 4 кг сырья второго вида и 2 кг сырья третьего вида. Для производства единицы продукции второго вида требуется 3 кг сырья первого вида, 6 кг сырья второго вида и 14 кг сырья третьего вида. Наличие сырья первого вида - 264 кг; второго - 148 кг; третьего - 280 кг. Прибыль от реализации единицы первой продукции - 6 усл. д.е., от реализации единицы продукции второго вида - 4 усл. д.е. Требуется разработать оптимальный план выпуска продукции, максимизирующий суммарную прибыль.

1. Сформулируем экономико-математическую модель задачи.

Введем неизвестные х1³0 и х2³0, соответствующие количествам продукции первого и второго вида, планируемых к производству.

Суммарный расход сырья первого вида будет 12х1 + 3х2;

Суммарный расход сырья второго вида - 4х1 + 6х2;

Суммарный расход сырья третьего вида - 2х1 + 14х2.

Поскольку запасы сырья ограничены, то получаем систему ограничений:

Целевая функция, соответствующая условиям задачи, будет иметь вид:

Z = 6х1 + 4х2 → max.

2. От общей формы модели переходят к канонической форме путем введения трех дополнительных неизвестных х3, х4 и х5. Дополнительные переменные в ограничениях типа £ обозначают недоиспользованные ресурсы. Модель принимает следующий вид:

Z = 6х1 + 4х2 + 0х3 + 0х4 + 0х5 → max

3. Поиск опорного решения и базиса задачи.

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

Хопор={х1=0, х2=0, х3=264, х4=148, х5=280}

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

Бх={х3, х4, х5}

4. Построение первой симплексной таблицы.

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

I – обозначим номер ограничения;

Бх - базис задачи;

Bi - свободные члены;

Q - симплексное отношение (тета)

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

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

Таблица 1

Первая симплексная таблица

I	Бх	Bi	Основные переменные	Дополнительные переменные.	Q
Х1	Х2	Х3	Х4	Х5
1	Х3	264	12	3	1	0	0	22
2	Х4	148	4	6	0	1	0	37
3	Х5	280	2	14	0	0	1	140
С	0	-6	-4	0	0	0

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

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

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

6. Последовательное улучшение плана.

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

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

ü если решаем задачу на максимум, то разрешающим будет столбец, содержащий наибольший по модулю отрицательный элемент:

ü если решаем задачу на минимум – то наибольший положительный.

В нашем случае разрешающим столбцом, будет столбец содержащий переменную х1.

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

Симплексное отношение (Q)	=	Элементы столбца свободных членов
Соответствующие элементы разрешающего столбца

Значения симплексного отношения заносятся в таблицу.

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

В рассматриваемом примере разрешающей строкой будет строка, содержащая переменную х3.

На пересечении разрешающей строки и столбца находится разрешающий элемент. В нашей задаче разрешающим элементом будет 12.

После отыскания разрешающего элемента переходят к построению новой симплексной таблицы. Для ее построения используют следующие правила[1]:

ü На месте разрешающего элемента в новой таблице ставят 1;

ü Элементы новой таблицы, соответствующие разрешающему столбцу равны 0;

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

ü Обыкновенные элементы (т. е. все остальные) рассчитываются по правилу прямоугольника, выраженному формулой

,

Где bij – обыкновенный элемент новой симплексной таблицы;

Ars – разрешающий элемент (в «старой» симплексной таблице);

Aij – элемент главной диагонали прямоугольника «старой» симплексной таблицы;

Ais, arj – элементы побочной диагонали прямоугольника «старой» симплексной таблицы.

Построенная новая симплексная таблица по вышеперечисленным правилам представлена в таблице 2.

Таблица 2

Вторая симплексная таблица

I	Бх	Bi	Основные переменные	Дополнительные переменные.	Q
Х1	Х2	Х3	Х4	Х5
1	Х1	22	1			0	0	88
2	Х4	60	0	5		1	0	12
3	Х5	236	0			0	1
С	132	0			0	0

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

Для построения следующей симплексной таблицы найдем разрешающий элемент: разрешающий столбец – столбец содержащий переменную х2. разрешающая строка – х4. Разрешающим элементом будет – 5.

Новая таблица представлена в таблице 3.

Таблица 3

Вторая симплексная таблица

I	Бх	Bi	Основные переменные	Дополнительные переменные.	Q
Х1	Х2	Х3	Х4	Х5
1	Х1	19	1	0			0
2	Х2	12	0	1			0
3	Х5	74	0	0			1
С	162	0	0			0

При просмотре индексной строки видно, что все числа неотрицательны. Следовательно, базисное решение Х=(19; 12; 0; 0; 74) оптимально, обеспечивает максимальное значение целевой функции 162. Таким образом, предприятие получит максимальную прибыль в 162 усл. д.е., если примет план по выпуску 19 единиц первого вида и 12 единиц изделий второго вида, при этом останется неизрасходованным сырье третьего вида в количестве 74 кг.

< Предыдущая		Следующая >