Линейное программирование, решение задач симплексным методом (стр. 3 из 8)

которая получается по правилам 1 – 5 ОЖИ с тем лишь изменением, что правила 2 и 3 меняются ролями:

1) остальные элементы разрешающей строки остаются без изменения

2) остальные элементы разрешающего столбца меняют лишь свои знаки

Рассмотрим систему

2X₁ + 3X₂ – 5X₃ = 16 = b₁,

3X₁ - 2X₂ + 4X₃ = 36 = b₂,

5X₁ + 7X₂ – 11X₃ = 44 = b₃.

Запишем ее в виде таблицы

	-x1	-x2	-x3
b1 =	-2	-3	5
b2 =	-3	2	-4
b3 =	-5	-7	11

и произведем один шаг МЖИ с разрешающим элементом “2”

	-x1	-b2	-x3
b1 =	-13	3	-2
x2 =	-3	1	-4
b3 =	-31	7	-6

: 2

Экстремумы линейной функции

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

Теорема. Если задача линейного программирования имеет оптимальное решение

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

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

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

Следовательно, принципиальная схема решения задач линейного программирования следующая:

1. С помощью ЖИ найдем все опорные решения системы.

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁,

……...................

a_k1x₁ + a_k2x₂ + … + a_knx_n = b_k,

a_k+1,1x₁ + a_k+1,2x₂ + … + a_k+1nx_n ≤ b_k+1,

……...................

a_m1x₁ + a_m2x₂ + … + a_mnx_n ≤ b_m.

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

Z = c₁x₁ + c₂x₂ + … + c_nx_n.

3. Выберем из них экстремальное Z.

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

каждом шаге монотонного изменения функции Z.

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

Симплексный метод на основе полных таблиц

Постановка задачи об определении оптимального ассортимента продукции

Предприятие может производить два вида изделий А и В, располагая для их изготовления ограниченными ресурсами материала чугуна и стали соответственно в количествах 350 и 392 кг и оборудования в количестве 408 станко-часов. Данные, представленные в виде таблицы, характеризуют затраты каждого из перечисленных трех видов ресурсов на изготовление одного изделия А и В.

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

Виды ресурсов	Объем ресурсов	Затраты на одно изделие
		А	В
Чугун	350	14	5
Сталь	392	14	8
Оборудование	408	6	12
Прибыль в руб.	10	5

Введем искомые неизвестные Х₁ и X₂, обозначающие число изделий А и В, которые должно производить предприятие.

Тогда математически задачу можно сформулировать следующим образом.

Среди множества неотрицательных решений системы неравенств

14X₁ + 5Х₂ ≤ 350, (1.1)

14Х₁ + 8Х₂ ≤ 392,

6Х₁ + 12Х₂ ≤ 408,

найти такое решение, для которого функция

Z = 10 Х₁ + 5 Х₂

достигает наибольшего значения.

Геометрическое решение задачи

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

Для этого, заменив каждое из неравенств равенством

14Х₁ + 5Х₂ = 350, (1-я прямая),

14X₁ + 8Х₂ = 392, (2-я прямая),

6Х₁ + 12Х₂ = 408, (3-я прямая),

строим граничную линию. Учитывая, что Х₁ ≥ 0 и Х₂ ≥ 0, получаем заштрихованную часть плоскости, образующую многоугольник решений OABCD (рис.1).

Затем строим линию уровня 10Х₁ + 5Х₂ = 0 и вектор (10;5), которые взаимно перпендикулярны. Нетрудно показать, что вектор дает направление наибольшего возрастания линейной функции.

Действительно

Z₀ = 10X₁₀ + 5Х₂₀ = 10 * 0 + 5 * 0 = 0,

Z_А = 10X_1A + 5Х_2A = 10 * 0 + 5 * 34 = 170,

Z_D = 10X_1D + 5X_2D = 10 * 25 + 5 * 0 = 250 и т. д.

Из всех линий уровня выбираем две, из которых одна проходит через точку 0 и дает min значение функции Z, а другая проходит через точку С и функция Z для нее принимает mах значение. Эти линии уровня называются опорными.

Рис. 1

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

14Х_l + 5Х₂ = 350,

14Х₁ + 8Х₂ = 392,

найдем координаты точки C

Х₁ = 20, Х₂ = 14,

при этом Z_max = 10 * 20 + 5 * 14 = 270 руб.

Таким образом, mах прибыль в 270 руб. будет получена, если предприятие произведет 20 изделий вида А и 14 изделий вида В.

Отыскание максимума линейной функции

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

Добавляя к левой части неравенств

14X₁ + 5Х₂ ≤ 350,

14Х₁ + 8Х₂ ≤ 392,

6Х₁ + 12Х₂ ≤ 408,

некоторую неотрицательную величину Y_j ≥ 0 (i = 1, 2, 3), (1.2)

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

14	Х1 + 5Х2 + У1	= 350,
14	Х1 + 8Х2	+ У2	= 392,
6	X1 + 12Х2	+ У3	= 408,
-10	X1 - 5Х2	+ Z = 0.

(1.3)

При этом можно показать, что каждому решению системы неравенств (1.1) соответствует единственное решение системы уравнений (1.3) и неравенств (1.2) и наоборот.

Каждая из переменных Y_1, У₂, У₃ входит только в одно уравнение и зависит от переменных Х₁ и X₂, которые мы называем свободными.

Системе (1.3) соответствует исходное допустимое базисное решение X₁ = X₂ = 0;

Y₁ = 350; Y₂ = 392; Y₃ = 408 и Z = 0.

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

Первое уравнение делим на разрешающее число и выписываем получившееся уравнение. Умножая это уравнение на 14, 6 и -10 и вычитая соответственно из 2-го, 3-го и 4-го уравнений системы (1.3), придем к следующей системе (1.4):

X1 +	5/14	X2 + 1/4 Y1 = 25,
3	Х2 – Y1 + Y2	= 42,
138/14	X2 – 6/14 Y1 + У3	= 258,
-20/14	X2 + 10/14 Y1	+ Z = 250.

(1.4)