Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

симплекс линейный программирование алгебраический

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

Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глаз» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием.

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

Исходя из вышесказанного, следует актуальность темы курсового проекта.

Предметом исследования курсового проекта являются разновидности решения симплексного метода.

Объектом является процесс нахождения оптимального или эффективного решения (плана) задач линейного программирования.

Цель данного курсового проекта - научиться находить оптимальное решение в экономических задачах линейного программирования.

Задачи курсового проекта:

ь изучить теоретические основы задач линейного программирования;

ь рассмотреть работу симплексного метода и его разновидностей;

ь применить разновидности симплексного метода к решению прикладных задач;

ь написать программный модуль, реализующий работу симплекс-метода.

1. Линейное программирование. Симплексный метод

1.1 Линейное программирование

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л.В. Канторовичу. Год спустя, в 1939 г., Л.В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

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

Целевая функция (критерий задачи или критерий эффективности) - результат принятого решения, который описывается функцией. Аргументами целевой функции (F(x)) являются разные варианты решений, а значениями - числа.

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

Каждая модель служит для достижения следующих целей:

1) познавание объекта или процесса;

2) прогнозирование поведения объекта;

3) принятие наилучших решений.

Этапы построения математической модели:

1. Определение параметров модели (б) - фиксированные данные, на значения которых исследователь не влияет.

2. Формирование управляющих переменных (x_i). Изменяя их значения, получаем оптимальное решение.

3. Определение области допустимых решений (Х) - ОДР. Это ограничения на управляющие переменные.

4. Выявление неизвестных факторов (о). Эти факторы изменяются случайным образом и не могут изменяться исследователем.

5. Задание целевой функции (F). В общем виде целевая функция записывается F (б, x_i, о) > max (min).

Функциональные (основные) ограничения - ограничения в виде системы *x=(?,?,?)в, влияющие не непосредственно на решения, а на их совокупность *x.

Косвенные (дополнительные) ограничения - ограничения вида x_i ? 0, обеспечивающие неотрицательность.

Допустимые решения - варианты решений, которые удовлетворяют ограничениям.

Оптимальное решение - решение, которое по тем или иным параметрам лучше других. Оптимальное решение может быть не единственным или отсутствовать вообще. Если оптимальное решение не единственно, то значение F(x) для всех этих решений одинаково.

Эффективное решение - такое решение, что кроме него не существует другого, для которого значение F(x) были бы наилучшими.

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

1) быть единственным для данной задачи;

2) измеряться в единицах количества;

3) линейно зависеть от входных параметров.

Исходя из вышесказанного, можно сформулировать задачу ЛП в общем виде:

найти экстремум функции:

F_(x) = c₁x₁ + c₂x₂ + … + c_nx_n > max (min)

при ограничениях в виде равенств:

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

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n = b₂;

…

a_m1x₁ + a_m2x₂ + … + a_mnx_n = b_m;

при ограничениях в виде неравенств:

a_p1x₁ + a_p2x₂ + … + a_pnx_n < b_p;

a_r1x₁ + a_r2x₂ + … + a_rnx_n < b_r;

…

a_v1x₁ + a_v2x₂ + … + a_vnx_n < b_v;

и условиях неотрицательности входных параметров:

x₁ ? 0; x₂ ? 0; …; x_n ? 0.

В краткой форме задача ЛП может быть записана так:

L_(x) =

при условии

(или ? b_i) при j =1,2,…, m, x_i ? 0, i = ,

где x₁, …, x_n - входные переменные;

с₁, …, с_n; a₁₁, …, a_nv; b₁, …, b_v - числа положительные, отрицательные и равные нулю.

В матричной форме эта задача может быть записана так:

cx > max, при Ах ? b или Ах ? b; х ? 0

или или .

Задачи ЛП можно решить аналитически и графически.

Рассмотрим задачу и запишем ее с помощью математической модели.

Предприятие выпускает продукцию двух типов: и . Изготовляется она из четырех видов сырья: , , и . Запас сырья и расход его на единицу каждого вида продукции дан в таблице.



Вид сырья	Запас сырья	Расход сырья на единицу продукции вида
	19	2	3
	13	2	1
	15	0	3
	18	3	0

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

Для этой задачи целевая функция будет записана в следующем виде:

F(x) = 7П₁ + 5П₂ > max,

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

2П₁ + 3П₂ ? 19;

2П₁ + П₂ ? 13;

3П₂ ? 15;

3П₁ ? 18;

П₁ ? 0, П₂ ? 0

1.2 Основные сведения о симплекс-методе

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

Для реализации симплексного метода - последовательного улучшения решения - необходимо освоить три основных элемента:

· способ определения какого-либо первоначального допустимого базисного решения задачи;

· правило перехода к лучшему (точнее, не худшему) решению;

· критерий проверки оптимальности найденного решения.

Симплекс-метод включает два этапа:

1) определение начального решения, удовлетворяющего ограничениям;

2) последовательное улучшение начального решения и получение оптимального решения задачи.

1.3 Геометрическая интерпретация симплексного метода

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

Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е., добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже»), чем предыдущие, по значениям линейной функции (увеличение ее при отыскании максимума F>max, уменьшение - при отыскании минимума F>min).

Рис. 1. Последовательный переход к вершинам многогранника

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

Пример:

F = 2x₁ + 3x₂ > max

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

2x₁ + 3x₂ ? 15, L₁: 2x₁ + 3x₂ = 15;

x₁ + 2x₂ ? 8, L₂: x₁ + 2x₂ = 8;

4x₁ ? 16, L₃: 4x₁ = 16;

4x₂ ? 12, L₄: 4x₂ = 12;

x₁ ? 0, x₂ ? 0. L₅: x₁ = 0; L₆: x₂ = 0.



Рис. 2. Графическое решение примера

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

1.4 Алгебраический смысл симплексного метода

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

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

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

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

2. Все переменные неотрицательные.

3. Целевую функцию следует максимизировать, или минимизировать.

f = c₁x₁ + c₂x₂ + … + c_nx_n > max

x₁ + a_1m+1x_m+1 + … + a_1nx_n = b₁,

x₂ + a_2m+1x_m+1 + … + a_2nx_n = b₂,

…

x_m + a_mm+1x_m+1 + … + a_mnx_n = b_m.

x_j ? 0, j =

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

1. Если требуется найти минимум целевой функции f то, умножая f на (-1), переходят к задаче максимизации; т.к. min f = - max (-f).

2. Если ограничение содержит неравенство со знаком ?, то от него переходя к равенству, добавляя в левую часть ограничения дополнительную неотрицательную переменную.

3. Если ограничение содержит неравенство со знаком ?, то от него переходят к равенству, вычитая из левой части дополнительную неотрицательную переменную.

4. Если в задаче какая-либо из переменных произвольна, то от нее избавляются, заменяя ее разностью двух других неотрицательных переменных.

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

Отыскание максимума линейной функции рассмотрим на примере с помощью аналитического симплекс-метода.

Решить симплекс-методом задачу:

F = 2x₁ + 3x₂ > max

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

x₁ + 3x₂ ? 18,

2x₁ + x₂ ? 16,

x₂ ? 5,

3x₁ ? 21,

x₁ ? 0, x₂ ? 0.

Прейдем к канонической форме задач ЛП, с помощью ввода дополнительных неотрицательных переменных. Все дополнительные переменные вводятся со знаком «+», т.к. все неравенства имеют вид «?». Получим систему ограничений:

x₁ + 3x₂ + х₃ = 18,

2x₁ + x₂ + x₄ = 16,

x₂ + x₅ = 5,

3x₁ + x₆ = 21.

Для нахождения первоначального базисного решения разобьем переменные на 2 группы - основные и неосновные (свободные).

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

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

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные переменные (по правилу): х₃, x₄, x₅, x₆,

неосновные переменные: x₁, x₂.

2. Выразим основные переменные через неосновные:

x₃ = 18 - x₁ - 3x₂,

x₄ = 16 - 2x₁ - x₂, (1)

x₅ = 5 - x₂,

x₆ = 21 - 3x₁.

Положив неосновные переменные равными нулю, т.е. x₁ = 0, x₂ = 0, получим первое базисное решение X₁ = (0; 0; 18; 16; 5; 21), которое является допустимым (т.к. нет отрицательных чисел).

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 2x₁ + 3x₂

F(X₁) = 2 • 0 + 3 • 0 = 0.

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

Шаг 3. Проверим, доставляет ли выбранное базисное решение оптимум целевой функции F.

Критерий оптимальности решения при нахождении максимума: если в выражении F отсутствуют положительные коэффициенты при неосновных переменных, то решение является оптимальным.

В соответствии с этим критерием данное базисное решение не оптимальное. Необходимо перейти к новому базисному решению.

Шаг 4. Переход к новому решению.

1. Определить вводимую переменную.

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

Чтобы новое опорное решение, с одной стороны, улучшая (не ухудшало) F, а с другой - было бы опорным, необходимо учитывать ограничения на рост переменной x₂ (из системы ограничений). Ведь нужно сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными. Т.е. дополнительно выполняться следующие неравенства:

x₃ = 18 - x₁ - 3x₂ ? 0, x₁ = 0 x₃ = 18 - 3x₂ ? 0,

x₄ = 16 - 2x₁ - x₂ ? 0, x₄ = 16 - x₂ ? 0,

x₅ = 5 - x₂ ? 0, x₅ = 5 - x₂ ? 0,

x₆ = 21 - 3x₁ ? 0, x₆ = 21,

x₂ ? 18/3

x₂ ? 16

x₂ ? 5

Каждое уравнение системы (1), кроме последнего, определяет оценочное отношение - границу роста переменной x₂, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при x₂ при условии, что эти числа имеют разные знаки.

При оценке переменной, переводимой в основные, возможны случаи:

1) x_i = , если b_j и a_ij имеют разные знаки и b_j ? 0, a_ij ? 0;

если b_j и a_ij одного знака и b_j ? 0, a_ij ? 0;

2) x_i = ?, если a_ij = 0;

если b_j = 0 и a_ij > 0;

3) x_i = 0, если b_j = 0 и a_ij < 0.

Так, последнее уравнение системы не ограничивает рост переменной x₂, т.к. данная переменная в него не входит (или входит с нулевым коэффициентом, т.е. a_ij = 0).

2. Определить выводимую переменную.

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

В данном примере наибольшее возможное значение для x₂ определяется как минимум.

x₂ = min {18/3; 16; 5; ?} = 5.

При x₂ = 5 переменная x₅ - обращается в нуль и переходит в неосновные.

Уравнение, где достигается наибольшее возможное значение переменной x₂, называется разрешающим.

В данном случае это третье уравнение. Выделим его рамкой.

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

Шаг 1.

1. Определим состав основных переменных:

основные: x₂, x₃, x₄, x₆;

неосновные: x₁, x₅.

2. Выразим основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для x₂):

3.

x₂ = 5 - x₅, x₂ = 5 - x₅,

x₃ = 18 - x₁ - 3 (5 - x₅), x₃ = 3 - x₁ - 3x₅,

x₄ = 16 - 2x₁ - (5 - x₅), x₄ = 11 - 2x₁ + x₅,

x₆ = 21 - 3x₁ x₆ = 21 - 3x₁.

4. Получим второе базисное решение (положив неосновные переменные равными нулю): Х₂ = (0; 5; 3; 11; 0; 21), которое является допустимым.

Шаг 2. Выразим F через неосновные переменные.

F = 2x₁ + 3x₂ = 2x₁ + 3 (5 - x₅) = 15 + 2x₁ - 3x₅. (2)

Определим ее значение при выбранном решении:

F₂ = F(X₂) = 15.

Изменение значения целевой функции (т.е. ?F) можно определить как произведение наибольшего возможного значения переменной, переводимой в основные (в этом случае это х₂), на ее коэффициент в выражении для F (это число 3).

В данном случае ?F₁ = 5 • 3 = 15.

F₂ = F₁ + ?F₁ = 0 + 15 = 15.

Шаг 3. Проверка оптимальности решения.

Т.к. в выражении для F присутствуют положительные коэффициенты (в (2) перед х₁), то данное решение не оптимальное, т.е. F₂ не максимальное.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

В (2) положительный коэффициент перед х₁, т.е. х₁ вводим в новый состав основных переменных. Определим допустимое значение х₁.

x₂ = 5 - x₅ ? 0 т.к. х₅ =0 x₂ = 5 ? 0 x₁ ? ?

x₃ = 3 - x₁ + 3x₅ ? 0 x₃ = 3 - x₁ ? 0 x₁ ? 3

x₄ = 11 - 2x₁ + x₅ ? 0 x₄ = 11 - 2x₁ ? 0 x₁ ? 11/2

x₆ = 21 - 3x₁ ? 0 x₆ = 21 - 3x₁ ? 0 x₁ ? 7

2. Определим выводимую переменную.

x₁ = min {?; 3; 11/2; 7} = 3

При x₁ = 3 переменная х₃ обращается в 0. Второе уравнение - разрешающее. х₃ - переходит в неосновные. Найдем ?F₂: ?F₂ = 3 • 2 = 6.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₂, х₄, х₆;

неосновные: х₃, х₅.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

х₁ = 3 - x₃ + 3x₅ х₁ = 3 - x₃ + 3x₅

x₂ = 5 - x₅ x₂ = 5 - x₅ (3)

x₄ = 11 - 2 (3 - x₃ + 3x₅) + x₅ x₄ = 5 + 2х₃ - 5х₅

x₆ = 21 - 3 (3 - x₃ + 3x₅) x₆ = 12 + 3х₃ - 9х₅

3. Получим третье базисное решение (неосновные переменные равны 0): Х₃ = (3; 5; 0; 5; 0; 12), которое является допустимым.

Шаг 2. Выразим F через неосновные переменные.

F = 2x₁ + 3x₂ = 2 (3 - x₃ + 3x₅) + 3 (5 - x₅) = 21 - 2х₃ + 3х₅ (4)

F₃ = F(X₃) = 21.

Действительно, F₃ = F₂ + ?F₂ = 15 + 6 = 21.

Шаг 3. Проверка решения на оптимальность.

Критерий оптимальности не выполняется, т.к. коэффициент при х₅ в (4) положителен. Т.е. F₃ не максимальное.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

В (9) положительный коэффициент перед х₅, т.е. х₅ вводим в новый состав основных переменных. Определим допустимое значение х₅.

х₁ = 3 - x₃ + 3x₅ ? 0 х₃ = 0 х₁ = 3 + 3x₅ ? 0 x₅ ? ?

x₂ = 5 - x₅ ? 0 x₂ = 5 - x₅ ? 0 x₅ ? 5

x₄ = 5 + 2х₃ - 5х₅ ? 0 x₄ = 5 - 5х₅ ? 0 x₅ ? 1

x₆ = 12 + 3х₃ - 9х₅ ? 0 x₆ = 12 - 9х₅ ? 0 x₅ ? 4

2. Определим выводимую переменную.

х₅ = min {?; 5; 1; 4/3} = 1

При x₅ = 1 переменная х₄ обращается в 0. Третье уравнение - разрешающее. х₄ - переходит в неосновные. Найдем ?F₃: ?F₃ = 1 • 3 = 3.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₂, х₅, х₆;

неосновные: х₃, х₄.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

3. Получим четвертое базисное решение (положим неосновные переменные равными 0): Х₄ = (6; 4; 0; 0; 1; 3), которое является допустимым.

Шаг 2. Выразим F через неосновные переменные.

F = 2x₁ + 3x₂ = 2 () + 3 () = 24 - (5)

F₄ = F(X₄) = 24.

Действительно, F₄ = F₃ + ?F₃ = 21 + 3 = 24.

Шаг 3. Проверка решения на оптимальность.

Критерий оптимальности выполнен, т.к. коэффициенты при х₃ и х₄ в (5) отрицательные и удовлетворяют условию. Т.е. F₃ является максимальным.

Ответ: F_max = 24, х* =

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

При отыскании минимума линейной функции Z возможны два пути:

1) отыскать максимум функции F, полагая F = - Z и учитывая, что Z_min = - F_max;

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

Рассмотрим это на следующем примере.

Z = 18y₁ + 16y₂ + 5y₃ + 21y₄ > min

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

у₁ + 2у₂ + 3у₄ ? 2,

3у₁ + у₂ + у₃ ? 3

y_i ? 0, i = 1, 2, 3, 4.

Введем дополнительные неотрицательные переменные у₅ и у₆ со знаком «-», т.к. неравенства имеют вид «?». Получим систему уравнений:

у₁ + 2у₂ + 3у₄ - у₅ = 2,

3у₁ + у₂ + у₃ - у₆ = 3.

Если на первом шаге в качестве основных взять дополнительные переменные, то получим недопустимое базисное решение: (0; 0; 0; 0; -2; -3). В данном случае в качестве основных удобно взять переменные у₃ и у₄, коэффициенты при у₃ и у₄ положительны, поэтому в качестве первоначального получим допустимое базисное решение.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: у₃, у₄

неосновные: у₁, у₂, у₅, у₆.

2. Выразим основные переменные через неосновные:

у₁ + 2у₂ + 3у₄ - у₅ = 2, у₃ = 3 - 3у₁ - у₂ + у₆,

3у₁ + у₂ + у₃ - у₆ = 3. у₄ =

3. Получим первое базисное решение Y₁ = (0; 0; 3; 2/3; 0; 0), которое является допустимым.

Шаг 2. Выразим Z через неосновные переменные и определим ее значение при выбранном базисном решении.

Z₁ = 18y₁ + 16y₂ + 5y₃ + 21y₄ = 18y₁ + 16y₂ + 5 (3 - 3у₁ - у₂ + у₆) + 21 ()= = 29 - 4y₁ - 3y₂ + 7y₅ + 5у₆.

Z₁ = Z(Y₁) = 29.

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

Шаг 3. Проверим, доставляет ли выбранное базисное решение оптимум целевой функции Z.

Критерий оптимальности решения при нахождении минимума: если в выражении Z отсутствуют отрицательные коэффициенты при неосновных переменных, то решение является оптимальным.

В соответствии с этим критерием данное базисное решение не оптимальное. Необходимо перейти к новому базисному решению.

Шаг 4. Переход к новому решению.

1. Определить вводимую переменную.

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

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

у₃ = 3 - 3у₁ - у₂ + у₆ ? 0 у₂=0, у₅=0, у₆=0 у₃ = 3 - 3у₁ ? 0(1)

у₄ = ? 0 у₄ = ? 0,

у₁ ? 1

у₁ ? 2

Каждое уравнение системы (1), кроме последнего, определяет оценочное отношение - границу роста переменной у₁, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при у₁ при условии, что эти числа имеют разные знаки.

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

2. Определить выводимую переменную.

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

В данном примере наибольшее возможное значение для у₁ определяется как минимум.

у₁ = min {1; 2} = 1.

При у₁ = 1 переменная у₃ - обращается в нуль и переходит в неосновные. Первое уравнение является разрешающим.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: у₁, у₄

неосновные: у₂, у₃, у₅, у₆.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

у₁ =

у₄ =

3. Получим второе базисное решение (положив неосновные переменные равными 0): Y₂ = (1; 0; 0; 1/3; 0; 0), которое является допустимым.

Шаг 2. Выразим Z через новые неосновные переменные и определим ее значение при выбранном базисном решении.

Z₂ = 18y₁ + 16y₂ + 5y₃ + 21y₄ = 18 () + 16y₂ + 5y₃ + +21 () = . (2)

Z₂ = Z(Y₂) = 25.

Изменение значения целевой функции (т.е. ?Z) можно определить как произведение наибольшего возможного значения переменной, переводимой в основные (в этом случае это y₁), на ее коэффициент в выражении для Z (это число (- 4)).

В данном случае ?Z₁ = 1 • (- 4) = - 4. Z₂ = Z₁ + ?Z₁ = 29 - 4 = 25.

Шаг 3. Проверка решения на оптимальность.

Критерий оптимальности не выполняется, т.к. коэффициент при у₂ в (2) отрицателен. Т.е. Z₂ не минимальное.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

В (2) отрицательный коэффициент перед у₂, т.е. у₂ вводим в новый состав основных переменных. Определим допустимое значение у₂.

у₁ = ? 0 у₃=0, у₅=0, у₆=0 у₁ = ? 0

у₄ = ? 0 у₄ = ? 0,

у₂ ? 3

у₂ ? 3/5

2. Определим выводимую переменную.

у₂ = min {3; 3/5} = 3/5

При у₂ = 3/5 переменная у₄ обращается в 0. Второе уравнение - разрешающее. у₄ - переходит в неосновные. Найдем ?Z₂: ?Z₂ = 3/5 • (- 5/3) = -1

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: у₁, у₂

неосновные: у₃, у₄, у₅, у₆.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

у₁ =

у₂ =

3. Получим третье базисное решение (положив неосновные переменные равными нулю): Y₃ = (4/5; 3/5; 0; 0; 0; 0), которое является допустимым.

Шаг 2. Выразим Z через новые неосновные переменные и определим ее значение при выбранном базисном решении.

Z₃ = 18y₁ + 16y₂ + 5y₃ + 21y₄ = 18 () + +16 () + 5y₃ + 21y₄ = 24 + у₃ + 3у₄ + 6у₅ + 4у₆. (3)

Z₃ = Z(Y₃) = 24.

Действительно, Z₃ = Z₂ + ?Z₂ = 25 - 1 = 24.

Шаг 3. Проверка решения на оптимальность.

Критерий оптимальности выполнен, т.к. коэффициенты при у₃, у₄, у₅ и у₆ в (3) положительные и удовлетворяют условию. Т.е. Z₃ является минимальным.

Ответ: Z_min = 24, х* =

1.6 Особые случаи симплексного метода

Рассмотрим особые случаи, которые могут возникнуть при решении задачи ЛП симплексным методом.

Неединственность оптимального решения (альтернативный оптимум)

Рассмотрим этот случай на примере:

F = 3x₁ + 3x₂ > max

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

х₁ + x₂ ? 8,

2x₁ - x₂ ? 1,

x₁ - 2x₂ ? 2,

x₁ ? 0, x₂ ? 0.

Приведем задачу к каноническому виду, путем ввода дополнительных неотрицательных переменных. Получим систему равенств:

х₁ + x₂ + х₃ = 8,

2x₁ - x₂ - х₄ = 1,

x₁ - 2x₂ + х₅ = 2,

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные переменные: х₃, x₄, x_5,

неосновные переменные: x₁, x₂.

2. Выразим основные переменные через неосновные:

x₃ = 8 - x₁ - x₂,

x₄ = 1 - 2x₁ + x₂,

x₅ = 2 - x₁ + 2x₂

Положив неосновные переменные равными нулю, т.е. x₁ = 0, x₂ = 0, получим первое базисное решение X₁ = (0; 0; 8; 1; 2), которое является допустимым (т.к. нет отрицательных чисел).

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 3x₁ + 3x₂

F(X₁) = 3 • 0 + 3 • 0 = 0.

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

Шаг 3. Проверим, доставляет ли выбранное базисное решение оптимум целевой функции F.

Критерий оптимальности решения при нахождении максимума: если в выражении F отсутствуют положительные коэффициенты при неосновных переменных, то решение является оптимальным.

В соответствии с этим критерием данное базисное решение не оптимальное. Необходимо перейти к новому базисному решению.

Шаг 4. Переход к новому решению.

1. Определить вводимую переменную.

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

Чтобы новое опорное решение, с одной стороны, улучшая (не ухудшало) F, а с другой - было бы опорным, необходимо учитывать ограничения на рост переменной x₁ (из системы ограничений). Ведь нужно сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными. Т.е. дополнительно выполняться следующие неравенства:

x₃ = 8 - x₁ - x₂ ? 0, х₂ =0 x₃ = 8 - x₁ ? 0 x₁ ? 8

x₄ = 1 - 2x₁ + x₂ ? 0, x₄ = 1 - 2x₁ ? 0 x₁ ? 1/2

x₅ = 2 - x₁ + 2x₂ ? 0 x₅ = 2 - x₁ ? 0 x₁ ? 2

2. Определим выводимую переменную.

x₁ = min {8; 1/2; 2} = 1/2

При x₁=1/2 переменная х₄ обращается в 0. Второе уравнение - разрешающее. x₄ - переходит в неосновные.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₃, х₅,

неосновные: х₂, х₄.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

x₁ = , x₁ = ,

x₃ = 8 - - x_2, x₃ =

x₅ = 2 - + 2x₂ x₅ =

Положив неосновные переменные равными нулю, получим второе базисное решение X₂ = (1/2; 0; 15/2; 0; 3/2), которое является допустимым (т.к. нет отрицательных чисел).

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 3x₁ + 3x₂ = 3 () + 3x₂ = . (1)

F₂ = F(X₂) = 3/2.

Найдем ?F₁ = 1/2 • 3 = 3/2.

F₂ = F₁ + ?F₁ = 0 + 3/2 = 3/2.

Шаг 3. Проверка оптимальности решения.

Т.к. в выражении для F присутствуют положительные коэффициенты (в (1) перед х₂₎, то данное решение не оптимальное, т.е. F₂ не максимальное.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

В (1) положительный коэффициент перед х₂, т.е. х₂ вводим в новый состав основных переменных. Определим допустимое значение х₂.

x₁ = ? 0, х₄ = 0 x₁ = ? 0 х₂ = ?

x₃ = ? 0, x₃ = ? 0 х₂ = 5

x₅ = ? 0 x₅ = ? 0 х₂ = ?

2. Определим выводимую переменную.

х₂ = min {?; 5; ?} = 5

При x₂=5 переменная х₃ обращается в 0. Второе уравнение - разрешающее. х₃ - переходит в неосновные.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₂, х₅,

неосновные: х₃, х₄.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

3.

x₁ =

x₂ =

x₅ = 9 - x₃ - x₄.

Положив неосновные переменные равными нулю, получим третье базисное решение X₃ = (5; 3; 0; 0; 9), которое является допустимым (т.к. нет отрицательных чисел).

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 3x₁ + 3x₂ = 3 () + 3 () = 24 - х₃. (2)

F₃ = F(X₃) = 24.

Найдем ?F₂ = 5 • 9/2 = 45/2.

F₃ = F₂ + ?F₂ = 3/2 + 45/2 = 48/2 = 24.

Шаг 3. Проверка оптимальности решения.

Т.к. в выражении для F отсутствуют положительные коэффициенты при неосновных переменных, то критерий оптимальности выполнен. Х₃ - оптимальное базисное решение, F_max = F(X₃) = 24.

Однако в выражении (2) для F отсутствует неосновная переменная х₄ (формально она входит с нулевым коэффициентом), поэтому изменение этой переменной не повлечет за собой изменение линейной функции. Например, можно перевести в основные переменную х₄; х₄ = min {15; ?; 9} = 9. Переменная х₅ перейдет в неосновные, однако изменения линейной функции не произойдет: ?F₃ = 9 • 0 = 0. Действительно на следующем шаге получим новое базисное решение Х₄ = (6; 2; 0; 9; 0), F_max = F(X₃) = 24. Учитывая, что переменная х₃ = 0 (в базисном решении Х₄ она осталась неосновной), а переменная х₄ удовлетворяет неравенству 0 ? х₄ ? 9, из системы уравнений можно получить все множество оптимальных решений задачи.

Появление вырожденного базисного решения

Рассмотрим появление вырожденного базисного решения на примере:

F = 2x₁ - x₂ > max

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

х₁ - х₂ ? 2,

3х₁ - 2х₂ ? 6,

6х₁ - 4х₂ ? 14,

х₁ ? 0, х₂ ? 0

Приведем систему неравенств к каноническому виду, путем ввода дополнительных неотрицательных переменных.

х₁ - х₂ + x₃ = 2,

3х₁ - 2х₂ + x₄ = 6,

6х₁ - 4х₂ + x_{5 =} 14,

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные переменные: х₃, x₄, x_5,

неосновные переменные: x₁, x₂.

2. Выразим основные переменные через неосновные:

x₃ = 2 - x₁ + x₂,

x₄ = 6 - 3x₁ + 2x₂,

x₅ = 14 - 6x₁ + 4x₂.

Положив неосновные переменные равными нулю получим первое базисное решение: Х₁ = (0; 0; 2; 6; 14), которое является допустимым.

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 2x₁ - x₂

F₁ = F(X₁) = 2 • 0 + 0 = 0.

Шаг 3. Проверка оптимальности решения.

Т.к. в выражении для F присутствуют положительные коэффициенты, то данное решение не оптимальное, т.е. F₁ не максимальное.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Положительный коэффициент в F перед х₁, т.е. х₁ вводим в новый состав основных переменных. Определим допустимое значение х₁.

x₃ = 2 - x₁ + x₂ ? 0, x₂ = 0 x₃ = 2 - x₁ ? 0, x₁ ? 2,

x₄ = 6 - 3x₁ + 2x₂ ? 0, x₄ = 6 - 3x₁ ? 0, x₁ ? 2,

x₅ = 14 - 6x₁ + 4x₂ ? 0 x₅ = 14 - 6x₁ ? 0 x₁ ? 14/6.

2. Определим выводимую переменную.

х₁ = min {2, 2, 14/6} = 2.

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

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₄, х₅,

неосновные: х₂, х₃.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

x₁ = 2 + x₂ - x₃, x₁ = 2 + x₂ - x₃,

x₄ = 6 - 3 (2 + x₂ - x₃) + 2x₂, x₄ = - x₂ + 3x₃,

x₅ = 14 - 6 (2 + x₂ - x₃) + 4x₂, x₅ = 2 - 2x₂ + 6x₃.

Положив неосновные переменные равными нулю, получим второе базисное решение: Х₂ = (2; 0; 0; 0; 2), которое является допустимым, но вырожденным, т.к. основная компонента x₄ = 0.

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 2x₁ - x₂ = 2 (2 + x₂ - x₃) - x₂ = 4 + х₂ - 2х₃

F₂ = F(X₂) = 4.

Шаг 3. Проверка оптимальности решения.

Т.к. в выражении для F присутствуют положительные коэффициенты, то данное решение не оптимальное, т.е. F₂ не максимальное.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Положительный коэффициент в F перед х₂, т.е. х₂ вводим в новый состав основных переменных. Определим допустимое значение х₂.

x₁ = 2 + x₂ - x₃ ? 0, x₃ = 0 x₁ = 2 + x₂ ? 0 x₂ ? ?

x₄ = - x₂ + 3x₃ ? 0, x₄ = - x₂ ? 0 x₂ ? 0

x₅ = 2 - 2x₂ + 6x₃ ? 0, x₅ = 2 - 2x₂ ? 0 x₂ ? 1

2. Определим выводимую переменную.

х₂ = min {?, 0, 1} = 0.

При x₂=0 переменная х₄ обращается в 0. Второе уравнение - разрешающее; х₄ - переходит в неосновные.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₂, х₅,

неосновные: х₃, х₄.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

х₂ = 3х₃ - х₄, х₂ = 3х₃ - х₄,

x₁ = 2 + 2х₃ - х₄, x₁ = 2 + 2х₃ - х₄,

x₅ = 2 - 2 (3х₃ - х₄) + 6x₃, x₅ = 2 - 2х₄.

Положив неосновные переменные равными нулю, получим третье базисное решение: Х₃ = (2; 0; 0; 0; 2), которое является допустимым, но вырожденным.

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 2x₁ - x₂ = 2 (2 + 2х₃ - х₄) - (3х₃ - х₄) = 4 + х₃ - х₄.

F₃ = F(X₃) = 4.

Шаг 3. Проверка оптимальности решения.

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

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Положительный коэффициент в F перед х₃, т.е. х₃ вводим в новый состав основных переменных. Определим допустимое значение х₃.

х₂ = 3х₃ - х₄ ? 0, х₄ = 0 х₂ = 3х₃ ? 0 х₃ ? 0

x₁ = 2 + 2х₃ - х₄ ? 0, x₁ = 2 + 2х₃ ? 0 х₃ ? 2

x₅ = 2 - 2х₄ ? 0 x₅ = 2 ? 0 х₃ ? ?

2. Определим выводимую переменную.

х₃ = min {0, 2, ?} = 0.

При x₃=0 переменная х₂ обращается в 0. Второе уравнение - разрешающее; х₂ - переходит в неосновные.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₃, х₅,

неосновные: х₂, х₄.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

х₃ = , х₃ = ,

x₁ = 2 + 2 () - х₄, x₁ = 2 + ,

x₅ = 2 - 2х₄ x₅ = 2 - 2х₄.

Положив неосновные переменные равными нулю, получим четвертое базисное решение: Х₄ = (2; 0; 0; 0; 2), которое является допустимым, но вырожденным.

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 2x₁ - x₂ = 2 (2 + ) - x₂ = 4 + .

F₄ = F(X₄) = 4.

Шаг 3. Проверка оптимальности решения.

Изменение целевой функции на этом шаге не произошло.

Шаг 4. Переход к новому решению.

1. Определим вводимую переменную.

Положительный коэффициент в F перед х₂, т.е. х₂ вводим в новый состав основных переменных. Определим допустимое значение х₂.

х₃ = ? 0, х₄ = 0 х₃ = , х₂ ? 0,

x₁ = 2 + ? 0, x₁ = 2 + , х₂ ? 2,

x₅ = 2 - 2х₄ ? 0 x₅ = 2 х₂ ? ?

2. Определим выводимую переменную.

х₂ = min {0, 2, ?} = 0.

При x₂=0 переменная х₃ обращается в 0. Первое уравнение - разрешающее; х₃ - переходит в неосновные.

Шаг 1.

1. Определим состав основных и неосновных переменных:

основные: х₁, х₂, х₅,

неосновные: х₃, х₄.

2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:

х₂ = 3х₃ - х₄, х₂ = 3х₃ - х₄,

x₁ = 2 + x₁ = 2 + 2х₃ - х₄,

x₅ = 2 - 2х₄ x₅ = 2 - 2х₄

Положив неосновные переменные равными нулю, получим пятое базисное решение: Х₅ = (2; 0; 0; 0; 2), которое является допустимым, но вырожденным.

Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении:

F = 2x₁ - x₂ = 2 (2 + 2х₃ - х₄) - (3х₃ - х₄) = 4 + х₃ - х₄.

F₄ = F(X₄) = 4.

Шаг 3. Проверка оптимальности решения.

Изменение целевой функции на этом шаге не произошло.

Выполненный шаг хотя и не вызвал увеличения значения линейной функции, не является лишним, т.к. привел к новому базисному решению. Наличие «пустых» шагов (?F = 0) может привести к так называемому «зацикливанию», т.е. возвращение к ранее найденному допустимому базисному решению (с тем же набором основных и неосновных переменных), и в этом случае процесс бесконечен.

Вывод. Если на каком-либо шаге наибольшее возможное значение переменной достигается в нескольких уравнениях одновременно (совпадают их оценочные отношения), то разрешающим является любое из них. На следующем шаге получаем вырожденное базисное решение, переход к очередному базисному решению может не изменить целевую функцию (?F = 0).

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

Отсутствие конечного оптимума (Fmax = ? или Fmin = -?)

Рассмотрим отсутствие конечного оптимума на примере: