Линейное программирование (ЛП)

1. Задача ЛП в общем виде формулируется следующем образом: требуется найти экстремум (минимум или максимум) целевой функции

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

где с_i - затраты в случае минимизации и доход в случае максимизации на (от)

производства i-го продукта,

х_i - искомое количество i-го продукта,

а_ij - удельные затраты j-го ресурса на единицу выпуска i-го продукта,

b_j - лимит j-го ресурса или количественное выражение спроса.

Допустимых решений задачи ЛП бесчисленное множество. Кроме того, множество допустимых решений ВЫПУКЛОЕ (если вместе с 2-я точка этому множеству принадлежит и отрезок, их соединяющий). Угловые (крайние) точки выпуклого множества это точки, которые не являются внутренними точками ни одного из отрезков. Именно в угловой точке Допустимое решение, которому соответствует экстремум Z, называют ОПТИМАЛЬНЫМ ПЛАНОМ. Следовательно, решить задачу ЛП - значит найти угловую точку выпуклого множества, координаты которой дают экстремум Z.

Задача ЛП, ограничения которой носят характер ЛИНЕЙНЫХ УРОВНЕНИЙ, называется задачей ЛП в КАНОНИЧЕСКОЙ ФОРМЕ. Переход от общей задачи ЛП к задаче в канонической форме осуществляется путем ВВЕДЕНИЯ m неотрицательных дополнительных переменных, которые добавляются к каждому из неравенств ограничений, обращая их в равенства, и которые входят в Z с коэффициентами, равными нулю.

Следовательно, КАНОНИЧЕСКАЯ (простейшая) ФОРМА задачи ЛП имеет вид

II. Для решения задачи ЛП симплексным методом следует записать её в канонической форме, введя обозначения:

- X = (x₁, x₂,…, x_n+m) - вектор искомых величин,

- С = (с_1, с₂,…, с_n, 0,…,о) - вектор коэффициентов при неизвестных (искомых) величинах целевой функции Z,

- В = (b_1, b_{2, …,} b_m) - вектор ограничений,

- А_j = (a_1j, a_2j, …, a_mj) - вектор - столбец коэффициентов затрат j-го ресурса,

- е₁ = (1, 0, 0, …0), е₂ = (0, 1, 0, …, 0), …, е_m(0, 0, …, 1) - система единичных векторов, которые линейно независимы между собой и образуют БАЗИС.

Наличие единичного базиса позволяет любой вектор системы А_j, В разложить по векторам этого базиса. Тогда допустимое решение задачи ЛП в виде х = (0, 0, …, 0, х_n+1,…, x_n+m) имеет неотрицательные компоненты, которые являются коэффициентами разложения вектора B по m линейно независимым векторам, называют БАЗИСНЫМ (ОПОРНЫМ) РЕШЕНИЕМ. Для определения базисного решения надо НЕБАЗИСНЫЕ переменные х₁, х₂,…, х_n положить равными нулю. Тогда базисные переменные x_n+1, x_n+2, …, x_n+m будут равны свободным членам x_n+1 = b₁, x_n+2 = b₂, …, x_n+m = b_m и базисное исходное решение будет представлено вектором Х₀ = (0, 0, …, 0, b₁, b₂, b_m), которому соответствует следующее исходное значение целевой функции

Z₀ = c₁0 + c₂ 0 + …+ c_i0 +…+ c_n 0 + 0b₁ + 0b₂ +…+0b_m = 0

Если исходное базисное решение не является оптимальным, то переходят к другому базисному решению путем перехода от одного базиса к другому в определенном НАПРАВЛЕНИИ, при котором в зависимости от критерия оптимальности (max или min) каждое последующее значение Z или возрастает или убывает и в конечном итоге позволяет достич оптимума:

1. Критерий оптимальности при решении задачи ЛП на max: последующее значение Z* должно быть больше исходного, т.е. . Это неравенство будет выполняться при условии, что и если среди разностей Z_j - C_j хотя бы одна будет ОТРИЦАТЕЛЬНОЙ, т.е. При выполнении этих условий

2. Критерий оптимальности при решении задачи ЛП на min: . Это неравенство будет выполняться, если среди разностей Z_j - C_j,будет хотя бы одна ПОЛОЖИТЕЛЬНАЯ. В этом случае и соответственно будет выполняться неравенство .

Из сказанного вытекают ПРАВИЛА НАПРАВЛЕННОГО ПЕРЕХОДА:

1) если при решении задачи ЛП на max несколько разностей будут ОТРИЦАТЕЛЬНЫМИ, то выбирают НАИМЕНЬШУЮ отрицательную разность, которая и укажет индекс вектора j, который нужно ввести в базис;

2) если при решении задачи ЛП на min несколько разностей будут ПОЛОЖИТЕЛЬНЫМИ, то выбирают НАИБОЛЬШУЮ положительную разность, которая и укажет индекс вектора j, который нужно ввести в базис.

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

1. По условиям задачи состовляется экономико-математическая модель задачи ЛП в общем виде (определяются Z и ограничения).

2. Осуществляется переход от общей задачи ЛП к канонической форме путем введения дополнительных переменных .

3. Составляется 1-я симплексная таблица

J	Б	С	Х						…
						…
						…
…	…	…	…	…	…	…	…	…	…	…
m						…
m+1			Z=0			…			…

J – столбец индексов

Б – столбец векторов базиса,

С – вектор-столбец коэффициентов Z, соответствующих бизисным векторам,

Х – исходное базисное решение,

m+1 – индексная строка, в которой размещаются разности для исходного базисного

решения Z = 0; поэтому индексную строку занимают коэффициенты целевой

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

Два последних столбца содержат коэффициенты единичных веторов е_j, функции цели Z, образующих базис.

4. Анализируется содержание индексной строки:

1) если требуется найти то согласно критерию оптимальности ПЛАН БУДЕТ ОПТИМАЛЬНЫМ, если все числа индексной строки НЕОТРИЦАТЕЛЬНЫ; если же хотя бы одно отрицательное, то следует осуществлять направленный переход для получения ;

2) если требуется найти то согласно критерию оптимальности ПЛАН БУДЕТ ОПТИМАЛЬНЫМ, если все числа С_i индексной строки НЕПОЛОЖИТЕЛЬНЫ; если же хотя бы одно положительное, то следует осуществлять направленный переход для получения

В обоих случаях для определения вектора, который нужно ввести в базис для осуществления направленного перехода, расчитывается величина которая и укажет его индекс. Столбец, соответствующий этому индексу, называется ВЕДУЩИМ.

5. Определяется число Индекс i, которому соответствует эта величина, укажет вектор, который следует ИСКЛЮЧИТЬ из базиса. Строка, соответствующая этому индексу, называется ВЕДУЩЕЙ.

Элемент, находящийся на пересечении ведущей строки и ведущего столбца, называется РАЗРЕШАЮЩИМ ЭЛЕМЕНТОМ.

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

- деления чисел ведущей строки на разрешающий элемент,

- умножения чисел ведущей строки на числа, противоположные знаку числам ведущего столбца,

- суммирования чисел столбцов с полученными произведениями и занесения результатов суммирования в новую (вторую) симплексную таблицу.

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

III. Пример решения задачи ЛП (выработки оптимального плана) симплексным методом.

Исходные данные:

1. Планируется выпустить 2 вида продукции х₁ и х₂.

2. Для производства продукции I-го вида требуется 12 кг сырья 1-го вида, 4 кг сырья 2-го вида и 2 кг сырья 3-го вида.

3. Для производства продукции II-го вида требуется 3 кг сырья 1-го вида, 6 кг сырья 2-го вида и 14 кг сырья 3-го вида.

4. Наличие сырья 1-го вида - 264 кг, второго - 148 кг, третьего - 280 кг.

5. Прибыль от реализации единицы I-й продукции 6 руб_, от реализации единицы II-й продукции 4 руб.

Найти: оптимальный план выпуска продукции, максимизирующий суммарную прибыль.

Решение:

1. Формулировка экономико-математической задачи (составление модели ЛП), исходя из исходных данных. Суммарный расход сырья 1-го вида составляет 12х₁ + 3х₂, 2-го вида - 4х₁ + 6х₂, 3-го вида - 2х₁ + 14х₂. Поскольку запасы сырья нормированы, то получают СИСТЕМУ ОГРАНИЧЕНИЙ

в виде 3-х НЕРАВЕНСТВ.

Целевая функция (максимилизация прибыли) примет вид

2. Переход к канонической форме за счет введения 3-х (три вида сырья) дополнительных переменных х₃, х₄, х₅. Модель примет вид (х₃, х₄, х₅ - по числу неравенств)

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

При этом е_i - базисный вектор; с₃, с₄, с₅ - коэффициент Z, соответствующие е₁. е₂. е₃

Таблица 1

Б	С	Х исходное базисное решение	Прибыль х 1 С1 = 6 А1	Прибыль х 2 С2 = 4 А2	С3 = 0 е1	С4 = 0 е2	С5 = 0 е3
е1
е2
е3
Индексная строка	Z0 = 0	-6	-4

4. Анализ индексной строки показывает, что исходное базисное решение НЕОПТИМАЛЬНО, так как в строке есть два ОТРИЦАТЕЛЬНЫХ элемента -6 и -4, которые соответсвуют векторам А₁ и А₂. Минимальный отрицательный элемент в индексной строке -6. Следовательно, вектор А₁ необходимо ввести в базис для улучшения решения (плана). Столбец С₁ = 6 ведущий, так как 6 максимальная , то есть .

5. Определение вектора, который следует исключить из базиса. Составляются отношения компоненты вектора Х (264, 148, 280) к положительным компонентам вектора А₁ (12, 4, 2): 264/12 = 22, 148/4 = 37, 280/2 = 140. Находится среди этих отношений минимальное число которое соответствует индексу i =1 (1-я строка)

Следовательно, из базиса надо исключить вектор е₁. Первая строка, соответствующая этому вектору, будет ведущей. Число 12, стоящее на пересечении ведущего столбца и ведущей строки - это разрешающий элемент.

6. Преобразование таблицы 1:

1) деление чисел ведущей строки на разрешающий элемент

- 1-я строка табл. 2.

2) преобразование столбца Х:

- значение Х = 22 умножается на числа ведущего столбца А₁ с обратным знаком, то есть на 6, -4, -2 (исключая 12)

- суммирование чисел столбца Х (148, 280, 0) с полученными произведениями

е₂ е₃ Z

148+(-88) = 60, 280+(-44) = 236, 0+132 = 132

3) преобраазование столбца А₂:

- значение А₂ = ¼ умножается на числа ведущего столбца А₁ с обратным знаком, то есть на 6, -4, -2

- суммирование чисел столбца А₂(6, 14, -4) с полученными произведениями

е₂ е₃ Z

6 - 1 = 5,

4) преобраазование столбца е₁:

- значение е₁ = ½ умножается на числа ведущего столбца А₁ с обратными знаками 6, -4,

-2

- суммирование чисел столбца e₁(0, 0, 0) c полученными произведениями

е₂ е₃ Z

7. Формирование табл. 2 и её анализ:

1) занесение в табл. 2 полученных сумм: в столбец Х: 60, 236, 132; в столбец в столбец е₁: -1/3, -1/6, 1/2.

Таблица 2.

Б	С	Х	С1 = 6 А1	С2 = 4 А2	С3 = 0 е1	С4 = 0 е2	С5 = 0 е3
А1				¼	1/12
е2					-1/3
е3				27/2	-1/6
Индексная строка	Z1 = 132		-5/2	1/2

2) проверка индексной строки табл. 2:

а) наличие числа -5/2 говорит о том, что базисное решение (базисный план) Х =(22, 60, 236) неоптимально, так как в строке есть один отрицательный элемент (-5/2), который соответствует вектору А₂;

б) решение (план) можно улучшить за счет введения в базис вектора А₂;

в) столбец с₂ = 4 ведущий.

3) определение вектора, который следует исключить из базиса. Составляются отношения компонент вектора Х (22, 60, 236) к положительным компонентам вектора А₂(1/4, 5, 27/2):22/_1/4 = 88, 60/5 = 12, 236/_27/2 = 17,4. Выбор минимального числа которое соответствует индексу i = 1 (вторая строка). Следовательно, из базиса надо исключить вектор е₂. Вторая строка, соответствующая этому вектору, будет ведущей. Число 5, стоящее на пересечении ведущего столбца и ведущей строки - это разрешающий элемент.

8. Преобразование табл. 2:

1) деление чисел ведущей строки (второй) на

- 2-я строка табл. 3

Таблица 3.

Б	С	Х	С1 = 6 А1	С2 = 4 А2	С3 = 0 е1	С4 = 0 е2	С5 = 0 е3
А1					1/10	-1/20
А2					-1/15	1/5
е3					11/15	-27/10
Индексная строка	Z2 = 162			1/3	1/2

2) преобразование столбца Х:

- значение Х = 12 умножается на числа ведущего столбца А₂ с обратным знаком

исключая число 5 ведущего столбца (оно входит в ведущую строку)

- суммирование чисел столбца Х (22, 236, 132) с полученными произведениями

22-3=19, 236-162= 74, 132 + 30 = 162

3) преобразование столбца е₁:

- значение е₁ = умножается на числа ведущего столбца А₂ с обратным знаком ,

- суммирование чисел столбца е₁ с полученными произведениями

4) преобразование столбца е₂:

- значение е₂ = 1/5 умножается на числа ведущего столбца А₂ с обратными знаками

- суммирование полученных произведений с числами столбца е₂ (0, 0, 0)

-1/20 + 0 = -1/20, -27/10 + 0 = -27/10, ½ + 0 = ½

9. Анализ индексной строки табл. 3 показывает, что все её числа неотрицательные. Следовательно, решение (план) Х = (19, 12, 74) является оптимальным, то есть предприятие получит максимальную прибыль в 162 руб., если примет план по выпуску 19 единиц продукции I-го вида и 12 единиц продукции II-го вида. При этом останется ресурс сырья III-го вида в количестве 74 кг.

Пример 2.