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

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

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

Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глаз» (теперь, впрочем, зачастую тоже). В середине 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

или или .

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

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

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

Прибыль производства от единицы продукции вида равна 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₁? ½

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

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

x₁ = min {8; ½; 2} = ½

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

Шаг 1.

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

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

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

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

x₁ =, x₁ = ,

x₃ = 8 — - x_2, x₃ =

x₅ = 2 — + 2x₂ x₅ =

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

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

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

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

Найдем ?F₁ = ½ • 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).

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

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

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

F = 2x₁ — 3x₂ + 1 > min

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

х₁ + х₂? 4,

2х₁ — х₂? 1,

х₁ — 2х₂? 1,

х₁? 0, х₂? 0.

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

Шаг 1.

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

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

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

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

х₁ = ,

х₂ = ,

х₅ = 4 + х₃ — х₄.

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

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

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

F = F (X) = - 1/3.

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

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

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

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

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

х₁ =? 0, х₄=0 х₁ =? 0 х₃? ?

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

х₅ = 4 + х₃ — х₄? 0 х₅ = 4 + х₃? 0 х₃? ?

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

х₃ = min {?; ?; ?} = ?.

Уравнения не ограничивают рост переменной х₃, поэтому и значение функции F неограниченно и отрицательно, т. е. F_min = - ?.

Вывод. Если на каком-либо шаге получаем, что во всех уравнениях системы бесконечные оценочные отношения той переменной, которая переводится в основные, то задача не имеет конечного оптимума (F_max = ?, если задача на отыскание максимума, и F_min = - ?, если задача на отыскание минимума).

1.7 Алгоритм табличного симплекс-метода

Пусть система приведена к каноническому виду.

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 =

Запишем расширенную систему.

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,

f — c₁x₁ — c₂x₂ — … — c_nx_n = 0.

Шаг 1. Получение начального решения.

Выбираются m переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом 1 только в одно уравнение и коэффициентом 0 в остальные уравнения системы.

Остальные n — m переменных называют свободными. Все свободные переменные полагаются равными 0, а базисные переменные — равные правым частям соответствующих ограничений системы.

Пусть m базисных переменных — это переменные x₁, x₂, …, x_m. Тогда начальное решение имеет X₀ имеет следующий вид:

X₀ = {x₁=b₁, x₂=b₂, …, x_m=b_m, x_m+1=0, …, x_n=0}

Если все b_i? 0,, то начальное решение является допустимым. Переход к шагу 2. В противном случае используют алгоритмы нахождения начального решения (Алгоритмы нахождения начального решения будут описаны в подпунктах 1.8.1. и 1.8.2.).

Шаг 2. Выражение функции f только через свободные переменные.

f = .

Переход к шагу 3.

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

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

В левой колонке симплекс-таблицы находятся базисные переменные, в колонке свободных членов — правые части соответствующих ограничений. В i-ой строке, j-м столбце стоит коэффициент при j-ой переменной в i-ом ограничении, i = 1,…, m, j = 1,…, n. В последней строке (f-строке) стоит коэффициент при j-ой переменной в целевой функции из расширенной системы. В предпоследнем столбце стоит значение свободного члена, входящего в целевую функцию.

Для проверки решения на оптимальность просматривается последняя f-строка:

· если коэффициенты, стоящие при свободных переменных неотрицательны, то полученное решение оптимально;

· полученное решение единственно, если все эти коэффициенты положительны;

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

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

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

Переход к шагу 4.

Шаг 4. Получение нового решения.

1. Выбор переменной, вводимой в список базисных переменных. Просматривается последняя строка симплекс-таблицы. Среди элементов этой строки выбирается максимальный по абсолютной величине (по модулю) отрицательный элемент. Столбец, в котором стоит этот элемент, называется разрешающим. Пусть, например, это p-й столбец. Переменная x_p стоящая в этом столбце, вводится в список базисных переменных.

2. Выбор переменной, выводимой из списка базисных переменных. Находят отношение элементов столбца свободных членов к элементам разрешающего столбца. При делении на противоположный по знаку элемент и на 0 результат полагают равным +?. Эти значения записываются в последний столбец симплекс-таблицы. Среди этих отношений находят минимальное. Строка, соответствующая минимальному отношению, называется разрешающей. Пусть, например, это q-я строка. Базисная переменная x_q, стоящая в этой строке, выводится из списка базисных переменных. Элемент симплекс-таблицы a_qp, стоящий на пересечении разрешающего столбца, называется разрешающим элементом.

3. Выполнение симплекс-преобразования и переход к новой симплекс-таблице. Элемент a_ij новой симплекс-таблицы вычисляется с помощью следующего симплекс-преобразования (в алгебре это преобразование известно как прямой ход метода Гаусса для решения систем линейных алгебраических уравнений):

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

.

Новое решение имеет следующий вид: все свободные переменные в нем полагаются равными 0, а все базисные переменные — свободным членам, стоящим в одной строке с ними.

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

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

Изложенные выше вычисления проводились для случая, когда, начальное решение является допустимым. Если в начальном решении существуют b_i < 0, то допустимое начальное решение можно найти по следующему алгоритму.

Шаг 1. Выражение функции через свободные переменные,

Шаг 2. Составление симплекс-таблицы.

Шаг 3. Выбор переменной, вводимой в список базисных переменных.

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

Шаг 4. Выбор переменной, выводимой из списка базисных переменных.

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

Шаг 5. По формулам и проводят симплекс-преобразование и переходят к новой симплекс-таблице. Если в новой таблице все свободные члены неотрицательны, то найденное решение является допустимым и следует перейти к шагу 3 алгоритма симплекс-метода, в противном случае — к шагу 2 рассматриваемого алгоритма.

Понятие об М-методе (методе искусственного базиса)

М-метод или метод искусственного базиса используется для определения первоначального базисного решения, когда оно не является допустимым, т. е. в начальном решении существуют b_i < 0.

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

В каждое уравнение, дающее отрицательную компоненту в базисном решении, вводим свою новую неотрицательную искусственную переменную y₁, y₂, …, y_k, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения. Составляем новую линейную функцию T = F — M (y₁ + y₂ + … + y_k), где М — произвольно большое число, и ищем ее максимум (Т-задача). Выражение M (y₁ + y₂ + … + y_k) назовем М-функцией. Справедлива теорема:

1. Если в оптимальном решении Т-задачи искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходное задачи (т.е. T_max = F_max, если y₁ = y₂ = … = y_k = 0, т. е. минимум М-функции равен 0).

2. Если имеется оптимальное решение Т-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна.

3. Если Т_max= ?, то исходная система также неразрешим, причем либо F_max= ?, либо условия задачи противоречивы.

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

Рассмотрим работу М-метода, используя симплексные таблицы, на примере.

Найти максимум целевой функции:

F (x) = x₁ + 2x₂ > max

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

x₁ — x₂? — 1,

x₁ — x₂? — 3,

x₁? 3.

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

Имеем F (x) = x₁ + 2x₂ > max

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

x₁ — x₂ + x₃ = - 1,

x₁ — x₂ — x₄ = - 3,

x₁ + x₅ = 3.

X₁ = (0; 0; -1; 3; 5) — недопустимое базисное решение с одной отрицательной компонентой, поэтому в первое уравнение введем искусственную переменную y₁ с тем же знаком, что и свободный член:

x₁ — x₂ + x₃ — у₁ = - 1,

x₁ — x₂ — x₄ = - 3,

x₁ + x₅ = 3

— x₁ + x₂ — x₃ + у₁ = 1,

— x₁ + x₂ + x₄ = 3,

x₁ + x₅ = 3.

T = x₁ + 2x₂ — My₁ > max.

Составляем первую симплексную таблицу.

Последняя строка — это (-М) — функция, т. е. (-М_ф) у₁. Заполняем ее, умножая строку у₁ на коэффициент (-М). Проверяя выполнение критерия оптимальности при отыскании максимума (-М) — функции, определяем, что в последней строке имеется отрицательный элемент во втором столбце; значит он является разрешающим, переменная x₂ переходит в основные. Минимальное оценочное отношение в первой строке, она является разрешающей. Переменная у₁ переходит в состав неосновных переменных, обращается в нуль на следующем базисном решении и далее исключается из рассмотрения.

В соответствии с общим алгоритмом получаем таблицу:

Последняя строка показывает, что критерий оптимальности выполнен; max (-M_ф) = 0, значит min M_ф = 0, далее эту строку можно не рассматривать. Получено допустимое базисное решение (0; 1; 0; 2; 3), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом.

Замечание. При решении задачи на отыскание минимума линейной целевой функции рекомендуется вместо Z_min находить (-Z)_max.

1.8 Алгоритм матричного симплекс-метода

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

Алгоритм решения следующий:

1) определить ведущий столбец;

2) определить ведущий элемент;

3) определить ведущую строку;

4) составить уравнения пересчета матрицы;

5) выполнить пересчет матрицы;

6) проверить результаты пересчета матрицы на оптимальность;

7) если найденное решение оптимально, то вычисления прекратить и сформулировать ответ. Если найденное решение не оптимально, то перейти к п. 1.

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

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

Все правильные столбцы должны содержать единицы в разных строках матрицы.

Ответ записывается следующим образом: каждому отрицательному коэффициенту в векторе решений ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе; для каждого нулевого коэффициента в векторе решений (т.е. для правильного столбца) ставится в соответствие значение свободного члена (из вектора b) из строки, содержащей единицу в столбце данной переменной. Фиктивные переменные в ответе не учитываются.

Ведущим столбцом может быть назначен любой столбец t матрицы, удовлетворяющий одному из условий:

· первый элемент, содержащий положительный элемент (кроме нуля) в строке (векторе) решений;

· столбец, содержащий наибольший положительный элемент в строке (векторе) решений;

· если столбец t удовлетворяет условию:

при решении задач на max;

при решении задач на min,

причем — коэффициент целевой функции в столбце j и — коэффициент в столбце j выбранной строки i матрицы А.

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

Критерием останова алгоритма поиска решений будет:

· для поиска max целевой функции — все коэффициенты вектора решений или равны нулю, или отрицательны;

· для поиска min целевой функции — все коэффициенты вектора решений или равны нулю, или положительны.

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

Рассмотрим работу симплексного метода на примере.

Найти максимум целевой функции:

F = x₁ + 2x₂ + x₃ + 2x₄ > max

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

x₁ + x₂ + 3x₄? 8;

2x₁ + 3x₂ + x₃? 14;

x₂ + 2x₃ + 4x₄ = 9.

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

x₁ + x₂ + 0x₂ + 3x₄ + x₅ 0x₆ = 8;

2x₁ + 3x₂ + x₃ + 0x₄ + 0x₅ — x₆ = 14;

0x₁ + x₂ + 2x₃ + 4x₄ + 0x₅ + 0x₆ = 9.

F (x) = x₁ + 2x₂ + x₃ + 2x₄ + 0x₅ + 0x₆ > max.

Оставим коэффициенты и получим условия задачи в матричном виде:

Таким образом, каноническая задача ЛП определена матрицей А, вектором свободных членов b = {8; 14; 9} и вектором решений c = {1; 2; 1; 2; 0; 0}.

Воспользуемся для расчета третьим способом. Четырем столбцам матрицы А соответствуют коэффициенты вектора решения больше нуля. Любой столбец может быть назначен ведущим.

По третьему правилу определим минимальные элементы в каждом столбце.

Для первого столбца: 8/1 14/2 > 1 • 14/2 = 7.

Для второго столбца: 8/1 14/3 9/1 > 2 • 14/3 = 28/3.

Для третьего столбца: 14/1 9/2 > 1 • 9/2 = 9/2.

Для четвертого столбца: 8/3 9/4 > 2 • 9/4 = 18/4.

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

Таким образом, ведущим элементом будет элемент a₂₂, ведущий столбец — второй, ведущая строка — вторая.

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

Ведущая строка (ее элементы обозначим буквой ц) будет пересчитываться по формуле:

где — новое значение элемента ведущей строки;

— текущее значение элемента ведущей строки;

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

где — новое значение элемента первой строки;

— новое значение элемента второй (ведущей) строки.

Такое преобразование строк матрицы носит название преобразования Жордана-Гаусса.

Для третьей строки:

Для четвертой строки (строки вектора решений):

Значение целевой функции f определим по формуле:

где — коэффициент целевой функции.

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

Для третьего столбца: 14 13/5 > 1/3 • 13/5 = 13/15.

Для четвертого столбца: 10/9 13/12 > 2 • 13/12 = 13/6.

Для шестого столбца: 10 13 > 2/3 • 10 = 20/3.

Ведущим элементом будет a₁₆.

Определим формулы для пересчета строк матрицы.

Для ведущей (первой) строки:

Для второй, третьей и четвертой строк соответственно:

Т.к. третий элемент вектора решений больше нуля, то вычисления необходимо повторить. В третьем столбце единственный элемент a₃₃ положительный и больший нуля, поэтому он и будет ведущим элементом.

Для ведущей (третьей) строки:

Для первой, второй и четвертой строк соответственно:

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

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

Ответ: X {0; 8; ½; 0}.

Т.к. пятая и шестая переменные — фиктивные, то в решении они не учитываются. Максимальное значение, равное 33/2, целевая функция принимает при следующих значениях аргументов: x₁ = 0; x₂ = 8; x₃ = ½; x₄ = 0.

Проверка:

F (x) = x₁ + 2x₂ + x₃ + 2x₄ = 1 • 0 + 2 • 8 + 1 • ½ + 2 • 0 = 0 + 16 + 0,5 + 0 = 16,5;

x₁ + x₂ + 3x₄? 8; 1 • 0 + 1 • 8 + 0 • 0,5 + 3 • 0? 8; 0 + 8 + 0 + 0? 8; 8? 8;

2x₁ + 3x₂ + x₃? 14; 2 • 0 + 3 • 8 + 1 • 0,5 + 0 • 0? 14; 24,5? 14;

x₂ + 2x₃ + 4x₄ = 9; 0 • 0 + 1 • 8 + 2 • 0,5 + 4 • 0 = 9; 0 + 8 + 1 + 0 = 9; 9 = 9.

Общие случаи решения задач ЛП матричным симплекс-методом

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

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

Если выполнены условия пункта 1.9 (все элементы последней строки или отрицательные, или нулевые при поиске максимума и, наоборот, — при поиске минимума), но количество правильных столбцов матричной модели меньше, чем количество условий ограничений, то определяют ведущий элемент по правилам пункта 1.9, но только в строках, которые не были ведущими.

Второй подход. Математическую модель приводят к правильному виду по правилам, изложенным в пункте 1.9, но в начало процедуры добавляют один шаг — применяют процедуру Жордана — Гаусса поочередно к тем столбцам, которые в последней строке матрицы содержат отрицательные коэффициенты, добиваясь при этом замены отрицательных значений коэффициентов на нулевые значения.

Рассмотрим пример, решив его вторым подходом.

Найти максимум целевой функции F (x) = - 2x₁ + 3x₂ > max

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

2x₁ — x₂? 6;

— x₁ + 3x₂? 6;

x₁ + 2x₂? 8;

x_j? 0,

Выполнив необходимые преобразования, получим матричную модель Первый элемент последней строки — отрицательный. Выполнив преобразование Жордана — Гаусса относительно элемента а₃₁, т.к. он имеет коэффициент, равный единице. Формула для пересчета последней строки:

Теперь для определения максимума целевой функции переходим к алгоритму, описанному в пункте 2.5.

Ведущим элементом будет а₂₂. Пересчитаем коэффициенты торой строки Формула для пересчета первой строки: .

Формула для пересчета третьей строки: .

Формула для пересчета четвертой строки: .

Ведущий элемент — а₃₅. Формула для пересчета четвертой строки:

.

Все коэффициенты последней строки отрицательные. Целевая функция достигает своего максимума, равного 6, в точке Х (0; 2).

Проверка:

F (x) = - 2 • 0 + 3 • 2 = 6.

Первое ограничение: 2 • 0 — 1 • 2? 6, — 2? 6.

Второе ограничение: — 1 • 0 + 3 • 2? 6, 6? 6.

Третье ограничение: 1 • 0 + 2 • 2? 8, 4? 8.

2. Решение задач симплекс-методом

Предприятию требуется составить план выпуска двух видов изделий четырьмя цехами так, чтобы от продаж изготовленной продукции предприятие получило наибольшую прибыль. Оба вида изделий последовательно обрабатываются в этих четырех цехах (таблица 1). В плане должно быть предусмотрено, что I цех может обрабатывать эту продукцию в течении 15 ч, II цех — 8 ч, III цех — 16 ч, IV цех — 12 ч.

Таблица 1. Обработка изделий в цехах

Предприятие от продажи изделия первого вида получило 2 руб. прибыли, от второго вида — 3 руб. прибыли.

2.1 Решение задачи с помощью симплекс-таблиц

Обозначим первый вид изделия за х₁, а второй — х₂.

Составим математическую модель этой задачи:

F = 2x₁ + 3x₂ > max

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

2х₁ + 3х₂? 15,

х₁ + 2х₂? 8,

4х₁? 16,

4х₂? 12,

х₁? 0, х₂? 0.

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

2х₁ + 3х₂ + х₃ = 15,

х₁ + 2х₂ + х₄ = 8,

4х₁ + х₅ = 16,

4х₂ + х₆ = 12.

После введения добавочных переменных систему уравнений и целевую функцию запишем в виде расширенной системы:

2х₁ + 3х₂ + х₃ = 15,

х₁ + 2х₂ + х₄ = 8,

4х₁ + х₅ = 16,

4х₂ + х₆ = 12,

F — 2x₁ — 3x₂ = 0.

Шаг 1.

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

основные: х₃, х₄, х₅, х₆;

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

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

х₃ = 15 — 2х₁ — 3х₂,

х₄ = 8 — х₁ — 2х₂,

х₅ = 16 — 4х₁,

х₆ = 12 — 4х₂.

3. Запишем первое базисное решение, положив неосновные переменные равными нулю: Х₁ = (0; 0; 15; 8; 16; 12).

Шаг 2.

Выразим F через неосновные переменные и вычислим ее значение:

F = 2x₁ + 3x₂.

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

Шаг 3. Заполним симплекс-таблицу.

Т.к. существует отрицательный коэффициент в последней (оценочной) строке, то решение не оптимально.

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

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

Выбираем максимальный по модулю коэффициент в оценочной строке. В данном случае — это коэффициент (- 3). Второй столбец — разрешающий. Переменная х₂ вводится в состав основных.

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

Шаг 3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.

Т.к. существует отрицательный коэффициент в оценочной строке, то решение не оптимально.

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

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

Отрицательный коэффициент а₅₁ = -2. Первый столбец — разрешающий. Переменная х₁ вводится в состав основных.

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

Найдем оценочное отношение. Минимальное оценочное отношение равно 2. Вторая строка является разрешающей. Переменная х₄ выводится из состава основных переменных.

Шаг 3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.

Т.к. существует отрицательный коэффициент в оценочной строке, то решение не оптимально.

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

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

Отрицательный коэффициент а₅₆ = -¼. Шестой столбец — разрешающий. Переменная х₆ вводится в состав основных.

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

Найдем оценочное отношение. Минимальное оценочное отношение равно 4. Третья строка является разрешающей. Переменная х₅ выводится из состава основных переменных.

Шаг 3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.

Критерий оптимальности выполнен, т.к. в последней строке нет отрицательных значений. F_max = 14, оптимальное базисное решение: Х = (4; 2; 1; 0; 0; 4).

В результате решения получаем ответ:

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

2.2 Решение задачи матричным симплекс-методом

Составим математическую модель данной задачи:

F = 2x₁ + 3x₂ > max

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

2х₁ + 3х₂? 15,

х₁ + 2х₂? 8,

4х₁? 16,

4х₂? 12,

х₁? 0, х₂? 0.

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

2х₁ + 3х₂ + х₃ + 0х₄ + 0х₅ + 0х₆ = 15,

х₁ + 2х₂ + 0х₃ + х₄ + 0х₅ + 0х₆ = 8,

4х₁ + 0х₂ + 0х₃ + 0х₄ + х₅ + 0х₆ = 16,

0х₁ + 4х₂ + 0х₃ + 0х₄ + 0х₅ + х₆ = 12.

F (x) = 2x₁ + 3x₂ + 0х₃ + 0х₄ + 0x₅ + 0x₆ > max.

Оставим коэффициенты и получим условия задачи в матричном виде:

Воспользуемся для расчета третьим способом. Двум столбцам матрицы А соответствуют коэффициенты вектора решения больше нуля. Любой столбец может быть назначен ведущим.

Определим минимальные элементы в каждом столбце.

Для первого столбца: 15/2 8/1 16/4 > 2 • 4 = 8.

Для второго столбца: 15/3 8/2 12/4 > 3 • 3 = 9.

Из двух величин выберем максимальное. В данном случае это 9.

Таким образом, ведущим элементом будет элемент a₄₂, ведущий столбец — второй, ведущая строка — четвертая.

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

Пересчитаем элементы ведущей строки по формуле и получим матрицу в виде:

В остальных строках матрицы коэффициент при второй переменной должен быть равен 0. В итоге получим:

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

Для первого столбца: 3 2 4 > 2 • 2 = 4.

Ведущим элементом будет a₂₁.

Пересчитаем строки матрицы.

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

Для шестого столбца: 8 4 12 > ¼ • 4 = 1.

Ведущий элемент — а₃₆.

Пересчитаем строки матрицы.

Т.к. вектор решения содержит нулевые и отрицательные значения, то найдено оптимальное решение. F_max = 14, оптимальное базисное решение: X {4; 2; 1; 0; 0; 4}.

В результате решения получаем ответ:

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

Сравнение матричного симплекс-метода с табличным.

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

1) в последней (оценочной) строке против всех основных переменных ставим нуль;

2) предыдущая разрешающая строка пересчитывается делением на разрешающий элемент;

3) расставляем нули и единицы в столбцах соответствующим основным переменным:

· 1 — против «своей основной переменой»,

· 0 — против «чужой переменной»;

4) для заполнения других коэффициентов пользоваться формулой:

где p — номер разрешающего столбца,

q — номер разрешающей строки.

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

2.3 Решение задачи М-методом (методом искусственного базиса)

Найти максимум целевой функции:

F (x) = x₁ + 2x₂ > max

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

x₁ — x₂? — 1,

x₁ — x₂? — 3,

x₁? 3.

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

Имеем: F (x) = x₁ + 2x₂ > max

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

x₁ — x₂ + x₃ = - 1,

x₁ — x₂ — x₄ = - 3,

x₁ + x₅ = 3.

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

х₃ = - 1 — х₁ + х₂,

х₄ = - 3 — х₁ + х₂,

х₅ = 3 — х₁.

Положив неосновные переменные равными нулю, получим базисное решение: X₁ = (0; 0; -1; 3; 5), которое является недопустимым, т.к. базисное решение имеет одну отрицательную компоненту. Поэтому в первое уравнение введем искусственную переменную y₁ с тем же знаком, что и свободный член:

x₁ — x₂ + x₃ — у₁ = - 1,

x₁ — x₂ — x₄ = - 3,

x₁ + x₅ = 3

— x₁ + x₂ — x₃ + у₁ = 1,

— x₁ + x₂ + x₄ = 3,

x₁ + x₅ = 3.

T = x₁ + 2x₂ — My₁ > max.

Составляем первую симплексную таблицу.

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

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

В соответствии с общим алгоритмом получаем таблицу:

Последняя строка показывает, что критерий оптимальности выполнен; max (-M_ф) = 0, значит min M_ф = 0, далее эту строку можно не рассматривать. Получено допустимое базисное решение: Х₁ = (0; 1; 0; 2; 3), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом.

Т.к. существует отрицательный коэффициент в оценочной строке, то решение не оптимально.

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

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

Максимальный отрицательный коэффициент а₄₁ = -3. Первый столбец — разрешающий. Переменная х₁ вводится в состав основных.

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

Найдем оценочное отношение. Минимальное оценочное отношение равно 3. Третья строка является разрешающей. Переменная х₅ выводится из состава основных переменных.

3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.

Т.к. существует отрицательный коэффициент в оценочной строке, то решение не оптимально.

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

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

Отрицательный коэффициент а₄₃ = -2. Третий столбец — разрешающий. Переменная х₃ вводится в состав основных.

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

Найдем оценочное отношение. Минимальное оценочное отношение равно 2. Вторая строка является разрешающей. Переменная х₄ выводится из состава основных переменных.

3. Выполним симплекс-преобразования и перейдем к новой симплекс-таблице.

Критерий оптимальности выполнен, т.к. в последней строке нет отрицательных значений. F_max = 15, оптимальное базисное решение: Х = (3; 6; 2; 0; 0).

Заключение

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

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

В результате выполнения проекта пришли к следующим выводам:

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

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

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

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

1.

Введение

в исследование операций. 6-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2001. — 912 с.: ил. — Парал. тит. англ.

2. Исследование операций в экономике: Учебное пособие для вузов/ Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман; Под ред. проф. Н. Ш. Кремера. — М.: ЮНИТИ, 2001. — 407 с.

3. Линейное программирование. Ашманов С. А. — М.: Наука. Главная редакция физико-математической литературы, 1981. — 340 с.

4. Малеко Е. М. Математические методы и модели исследования операций: Учеб. пособие. — Магнитогорск: МаГУ, 2003. — 100 с.

5. Математические методы в программировании: Учебник. — М.: ИД «ФОРУМ»: ИНФРА-М, 2006. — 224 с.: ил. — (Профессиональное образование). — (Учимся программировать).

6. Математическое программирование: Учебное пособие. — 2-е издание, переработанное и дополненное / Кузнецов Ю. Н., Кузубов В. И., Волощенко А. Б. — М.: Высшая школа, 1980. — 300 с.

7. Справочник по математике для инженеров и учащихся втузов. Бронштейн И. Н., Семендяев К. А. — М.: Наука. Главная редакция физико-математической литературы, 1981.

Приложение

Dim KolBazPer, KolPer, nomerMinus, numStroki, numStolbca As Integer

Dim flag As Boolean

Sub delay (zaderjka)

PauseTime = zaderjka ' Установка задержки

Start = Timer 'Старт таймера

Do While Timer < Start + PauseTime

DoEvents ' Позволяет выполнять действия в процессе задержки

Loop

End Sub

Private Sub Clear_Click ()

'Гасим кнопку вычисление

Vichislenie. Enabled = False

'Форматирование

Range («A:Z»).Clear

Range («A:Z»).Select

Selection. ColumnWidth = 8.63

Range («A1»).Select

End Sub

Sub ПоискРазрешающейСтроки ()

For i = 3 To KolBazPer + 2

If Worksheets («Лист1»).Cells (i, nomerMinus).Value * Worksheets («Лист1»).Cells (i, KolPer + 2).Value > 0 Then

OcOtn = Cells (i, KolPer + 2).Value / Cells (i, nomerMinus).Value

Cells (i, KolPer + 3) = OcOtn

End If

If (Worksheets («Лист1»).Cells (i, nomerMinus).Value * Worksheets («Лист1»).Cells (i, KolPer + 2).Value < 0) _

Or (Worksheets («Лист1»).Cells (i, nomerMinus).Value = 0) _

Or ((Worksheets («Лист1»).Cells (i, KolPer + 2).Value = 0) _

And (Worksheets («Лист1»).Cells (i, nomerMinus).Value > 0)) Then

OcOtn = «Бесконечность»

Cells (i, KolPer + 3) = OcOtn

End If

If ((Worksheets («Лист1»).Cells (i, KolPer + 2).Value = 0) _

And (Worksheets («Лист1»).Cells (i, nomerMinus).Value < 0)) Then

OcOtn = 0

Cells (i, KolPer + 3) = OcOtn

End If

Next i

If Worksheets («Лист1»).Cells (3, KolPer + 3) = «Бесконечность» Then

min = 10 000

Else

min = Worksheets («Лист1»).Cells (3, KolPer + 3) 'минимальный элемент — первый

End If

nomerMinus = 3 'строка минимального элемента третья

For i = 3 To KolBazPer + 2

'проверка следующего элемента на минимальность

If (Worksheets («Лист1»).Cells (i, KolPer + 3) < min) And _

(Worksheets («Лист1»).Cells (i, KolPer + 3) <> «Бесконечность») Then

min = Worksheets («Лист1»).Cells (i, KolPer + 3)

nomerMinus = i

End If

Next i

numStroki = nomerMinus

Range (Cells (nomerMinus, 1), Cells (nomerMinus, KolPer + 3)).Select

Selection. Interior. Color = vbGreen

End Sub

Sub ПоискРазрешающегоСтолбца ()

Dim s, i, j, min As Integer

s = 0

For j = 2 To KolPer + 1

If Worksheets («Лист1»).Cells (KolBazPer + 3, j) < 0 Then 'Проверка строки на отрицательный элемент

s = s + 1 'сумма отрицательных элементов

If s = 1 Then 'если отриц. элемент =1, запомнить номер столбца

nomerMinus = j

End If

End If

Next j

If s = 1 Then 'если отриц. элемент =1, окрасить столбец в зеленый

numStolbca = nomerMinus

Range (Cells (2, nomerMinus), Cells (KolBazPer + 3, nomerMinus)).Select

Selection. Interior. Color = vbGreen

ElseIf s = 0 Then

MsgBox «Найдено оптимальное решение. F =» & Worksheets («Лист1»).Cells (KolBazPer + 3, KolPer + 2), vbOK, «Ответ»

flag = True

Else

'Нахождение максимального отрицательного элемента, если в индексной строке их несколько

min = Worksheets («Лист1»).Cells (KolBazPer + 3, 2) 'минимальный элемент — первый

nomerMinus = 2 'столбец минимального элемента второй

For i = 2 To KolPer + 1

'проверка следующего элемента на минимальность

If Worksheets («Лист1»).Cells (KolBazPer + 3, i) < min Then

min = Worksheets («Лист1»).Cells (KolBazPer + 3, i)

nomerMinus = i

End If

Next i

numStolbca = nomerMinus

Range (Cells (2, nomerMinus), Cells (KolBazPer + 3, nomerMinus)).Select

Selection. Interior. Color = vbGreen

End If

End Sub

Sub НоваяСТ ()

Dim RazRelem

For i = 3 To KolBazPer + 3

For j = 2 To KolPer + 2

Worksheets («Лист2»).Cells (i, j).Value = Worksheets («Лист1»).Cells (i, j).Value

Next j

Next i

RazRelem = Cells (numStroki, numStolbca).Value

For i = 3 To KolBazPer + 3

For j = 2 To KolPer + 2

With Worksheets («Лист2»)

If numStroki = i Then

Cells (i, j).Value =.Cells (i, j).Value / RazRelem 'вычисление разрешающей строки

Else

Cells (i, j).Value =.Cells (i, j).Value — ((.Cells (i, numStolbca).Value *.Cells (numStroki, j).Value) / RazRelem) 'пересчет таблицы

End If

End With

Next j

Next i

End Sub

Sub НахождениеМаксимума ()

Do

'Снятие окраски

Range (Cells (1, 1), Cells (KolBazPer + 3, KolPer + 3)).Select

Selection. Interior. Color = vbWhite

ПоискРазрешающегоСтолбца

delay (1)

If Not flag Then ПоискРазрешающейСтроки

delay (1)

If Not flag Then НоваяСТ

delay (1)

Loop While flag = False

End Sub

Private Sub Vichislenie_Click ()

НахождениеМаксимума

'Гасим кнопку вычисление

Vichislenie. Enabled = False

End Sub

Private Sub VvodParam_Click ()

flag = False

'Зажигаем кнопку вычисление

Vichislenie. Enabled = True

' Ввод параметров таблицы

KolBazPer = CInt (InputBox («Введите количество базисных переменных:», «Ввод параметров»))

KolPer = CInt (InputBox («Введите количество переменных:», «Ввод параметров»))

'Оформление шапки

Range («A1:A2»).Select

ActiveCell. FormulaR1C1 = ««

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

WrapText = True

MergeCells = True

End With

Columns («A:A»).ColumnWidth = 14

Range (Cells (1, 2), Cells (1, KolPer + 1)).Select

Selection. Merge

Range («B1»).Value = «Коэффициенты при переменных»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

WrapText = True

MergeCells = True

End With

Range (Cells (1, KolPer + 2), Cells (2, KolPer + 2)).Select

ActiveCell. FormulaR1C1 = «Свободные члены»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

WrapText = True

MergeCells = True

End With

Columns (KolPer + 2).ColumnWidth = 14

Range (Cells (1, KolPer + 3), Cells (2, KolPer + 3)).Select

ActiveCell. FormulaR1C1 = «Оценочное отношение»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

WrapText = True

MergeCells = True

End With

Columns (KolPer + 3).ColumnWidth = 14

Range (Cells (KolBazPer + 3, 1), Cells (KolBazPer + 3, 1)).Select

Selection. Value = «F»

With Selection

HorizontalAlignment = xlCenter

VerticalAlignment = xlCenter

MergeCells = True

End With

Dim j As Integer

For j = 2 To KolPer + 1

Cells (2, j) = «Х» & j — 1

Next j

'Начертание границ таблицы

Range (Cells (1, 1), Cells (KolBazPer + 3, KolPer + 3)).Select

Selection. Borders (xlDiagonalDown).LineStyle = xlNone

Selection. Borders (xlDiagonalUp).LineStyle = xlNone

With Selection. Borders (xlEdgeLeft)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders (xlEdgeTop)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders (xlEdgeBottom)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders (xlEdgeRight)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders (xlInsideVertical)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

With Selection. Borders (xlInsideHorizontal)

LineStyle = xlContinuous

Weight = xlThin

ColorIndex = xlAutomatic

End With

Range («A1»).Select

End Sub