Решение производственной задачи табличным симплекс-методом. Преобразование Жордана-Гаусса и симплекс-метод в Excel

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

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

Исходные данные задачи на симплекс-метод

Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.

Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:

Фонд времени работы станков (мин.) задан в матрице B:

Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:

Цель производственной задачи

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

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

(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )

(2) Запишем ограничения плана в виде системы уравнений:

(3) Тогда целевая прибыль:

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

(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).

(5) Примем следующий опорный план :

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Занесем данные в симплекс-таблицу :

В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;

(7) Выбираем в последней строке наибольшее (по модулю ) отрицательное число.

Вычислим b = Н / Элементы_выбранного_столбца

Среди вычисленных значений b выбираем наименьшее .

Пересечение выбранных столбца и строки даст нам разрешающий элемент. Меняем базис на переменную соответствующую разрешающему элементу (X5 на X1 ).

• Сам разрешающий элемент обращается в 1.
• Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
• Для элементов разрешающего столбца – они просто обнуляются.
• Остальные элементы таблицы пересчитываем по правилу прямоугольника.

a ij (*) = a ij – (A * B / РЭ)

Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .

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

Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.

(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.

ОТВЕТ:

X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.

P = 48 * 32 + 33 * 20 = 2 196 руб.

Галяутдинов Р.Р.

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

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

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

Рисунок 1

Остальные ячейки таблицы (кроме столбца "Отношение") пересчитываются по так называемому правилу прямоугольника , смысл которого проще всего понять на примере. Пусть нужно пересчитать элемент обведенный на Рис.1 красным контуром. Мысленно проводим от него вертикальную и горизонтальную линии до пересечения, с разрешающей строкой и разрешающим столбцом. Элементы стоящие в местах пересечения обведены синими контурами (Смотри Рис.1 ). Новое значение "красного" элемента будет равно нынешнему значению элемента минус произведение "синих" деленное на разрешающий ("серый") элемент (Смотри Рис.1 ). То есть: 18 - (64 * -1) / 4 = 34 , здесь знаком "* " показана операция умножения.
Записываем новое значение на прежнее место (Смотри Рис.2 красный контур).

Рисунок 2

Пользуясь данным правилом, заполняем все пустые элементы таблицы (кроме столбца "Отношение") Смотри Рис.3 . После этого определим новый разрешающий столбец. Для этого проанализируем строку "Q" и так как наша задача на максимум, то найдем в ней максимальный положительный элемент , он и определит разрешающий столбец. В нашем случае это 3/2 . Все элементы разрешающего столбца показаны красным шрифтом (Смотри Рис.3 ). Если после очередной итерации в строке "Q" не окажется положительных элементов - это значит что оптимальное решение достигнуто, итерации прекращаются. Если бы наша задача была на минимум, то разрешающий столбец определялся бы по минимальному отрицательному элементу, и если после очередной итерации в строке "Q" не окажется отрицательных элементов, значит достигнуто оптимальное решение.

Рисунок 3

Теперь заполним столбец "Отношение". Для этого нужно соответствующий (стоящий в той же строке) элемент столбца "Решение" разделить на соответствующий элемент разрешающего столбца (Смотри Рис.3 ). Обратите внимание , что данная операция проводится только для положительных элементов разрешающего столбца и строка "Q" в данной операции не участвует. Если после некоторой итерации в разрешающем столбце не окажется положительных элементов, то данная задача неразрешима ввиду неограниченности целевой функции, итерации прекращаются.

После заполнения столбца "Отношение" определим новую разрешающую строку. Она определяется минимальным элементом из столбца "Отношение". В нашем случае это 32 , все элементы разрешающей строки показаны красным шрифтом (Смотри Рис.3 ). На этом очередная итерация заканчивается, на следующей итерации переменная x 2 будет выведена из базиса (об этом нам говорит новая разрешающая строка), ее место займет переменная x 1 (об этом нам говорит новый разрешающий столбец) и все вычисления повторятся снова.

В общем случае линейное уравнение имеет вид:

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

Общая характеристика разрешенной системы уравнений

Пример 20.1

Дать характеристику системе уравнений .

Решение :

1. Входит ли в состав противоречивое уравнение? (Если коэффициенты, в этом случае уравнение имеет вид: и называется противоречивым .)

• Если система содержит противоречивое, то такая система несовместна и не имеет решения

2. Найти все разрешенные переменные . (Неизвестная называется разрешенной для системы уравнений, если она входит в одно из уравнений системы с коэффициентом +1, а в остальные уравнения не входит (т.е. входит с коэффициентом, равным нулю).

3. Является ли система уравнений разрешенной? (Система уравнений называется разрешенной , если каждое уравнение системы содержит разрешенную неизвестную, среди которых нет совпадающих)

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

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

В общем случае разрешенная система уравнений имеет вид:

На данном этапе главное понять что такое разрешенная неизвестная (входящая в базис и свободная).

Общее Частное Базисное решения

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

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

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

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

Теорема (1)

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

Пример 1. Найти общее, базисное и какое-либо частное решение системы уравнений:

Решение :

1. Проверяем является ли система разрешенной?

• Система является разрешенной (т.к. каждое из уравнений содержит в себе разрешенную неизвестную)

2. Включаем в набор разрешенные неизвестные — по одному из каждого уравнения .

3. Записываем общее решение в зависимости от того какие разрешенные неизвестные мы включили в набор .

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

Ответ: частное решение (один из вариантов)

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

Элементарные преобразования линейных уравнений

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

Теорема (2)

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

Теорема (3)

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

Следствие из Теорем (2 и 3)

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

Формулы пересчета коэффициентов системы

Если у нас есть система уравнений и мы хотим преобразовать ее в разрешенную систему уравнений в этом нам поможет метод Жордана-Гаусса.

Преобразование Жордана с разрешающим элементом позволяет получить для системы уравнений разрешенную неизвестную в уравнении с номером . (пример 2).

Преобразование Жордана состоит из элементарных преобразований двух типов:

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

Пример 2 Пересчитаем коэффициенты системы

При делении уравнения с номером на , его коэффициенты пересчитываются по формулам:

Чтобы исключить из уравнения с номером , нужно уравнение с номером умножить на и прибавить к этому уравнению.

Теорема (4) О сокращении числа уравнений системы.

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

Теорема (5) О несовместимости системы уравнений.

Если система уравнений содержит противоречивое уравнение, то она несовместна.

Алгоритм метода Жордана-Гаусса

Алгоритм решения систем уравнений методом Жордана-Гаусса состоит из ряда однотипных шагов, на каждом из которых производятся действия в следующем порядке:

1. Проверяется, не является ли система несовместной. Если система содержит противоречивое уравнение, то она несовместна.
2. Проверяется возможность сокращения числа уравнений. Если в системе содержится тривиальное уравнение, его вычеркивают.
3. Если система уравнений является разрешенной, то записывают общее решение системы и если необходимо — частные решения.
4. Если система не является разрешенной, то в уравнении, не содержащем разрешенной неизвестной, выбирают разрешающий элемент и производят преобразование Жордана с этим элементом.
5. Далее заново переходят к пункту 1

Пример 3 Решить систему уравнений методом Жордана-Гаусса.

Найти : два общих и два соответствующих базисных решения

Решение :

Вычисления приведены в нижеследующей таблице:

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

В первых трех строках таблицы помещены коэффициенты при неизвестных и правые части исходной системы. Результаты первого преобразования Жордана с разрешающим элементом равным единице приведены в строках 4, 5, 6. Результаты второго преобразования Жордана с разрешающим элементом равным (-1) приведены в строках 7, 8, 9. Так как третье уравнение является тривиальным, то его можно не учитывать.

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

Метод базируется на элементарных преобразованиях (переводящих систему в эквивалентную), к которым относятся:

• прибавление к обеим частям уравнения системы другого уравнения той же системы, умноженного на число, отличное от нуля;
• перестановка местами уравнений в системе;
• удаление из системы уравнений вида 0 = 0.

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

Шаг метода состоит в следующем:

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

Алгоритмизировать это можно так:

Для СЛАУ в матричном виде A*x=b (матрица A размерности m*n , совсем необязательно квадратная) составляется следующая таблица:

В таблице выбран разрешающий элемент a r,s ≠0 , тогда r - разрешающая строка, s - разрешающий столбец.

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

1. вычисляются элементы разрешающей строки: a" r,j =a r,j /a r,s - то есть, r-строка таблицы делится на разрешающий элемент;

2. все элементы разрешающего столбца, кроме a r,s , равного единице, становятся равны нулю;

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

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

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

Возможны следующие случаи:

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

2. Получается тождество 0 = 0 - уравнение является линейной комбинацией остальных и строка нулей может быть вычеркнута из системы.

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

Запрограммируем метод в Excel одной формулой, изменять которую должно быть не слишком трудоёмко. Например, для решения СЛАУ

заполним коэффициентами системы ячейки листа от A1 до D4 включительно, выберем разрешающий элемент a 1,1 =1 , а первый шаг метода сделаем в ячейке A6 , куда загоним "универсальную" формулу для преобразования Жордана-Гаусса:

ЕСЛИ(СТРОКА($A$1)=СТРОКА(A1);A1/$A$1;
ЕСЛИ(СТОЛБЕЦ($A$1)=СТОЛБЕЦ(A1);0;(A1*$A$1-
ДВССЫЛ(АДРЕС(СТРОКА(A1);СТОЛБЕЦ($A$1)))*
ДВССЫЛ(АДРЕС(СТРОКА($A$1);СТОЛБЕЦ(A1))))/$A$1))

На следующем шаге разрешающим элементом может быть, например, a 2,2 =1 (ячейка B7). Нам останется скопировать формулу из A6 в A11 (по пустой строке оставляем, чтоб визуально разделить шаги метода), войти в режим редактирования формулы (двойной щелчок по ячейке или выбрать её и нажать клавишу F2) и поправить (аккуратно перетащить мышкой за границу) все закреплённые ссылки с ячейки A1 на B7 .

Конечно, можно заменить везде в формуле закреплённую ссылку $A$1 на конструкцию вида ДВССЫЛ(ЯЧЕЙКА) , образующую динамический адрес ссылки. Скажем, ДВССЫЛ(F8) , а в ячейке F8 будет автоматически формироваться адрес ячейки разрешающего элемента по заданным пользователем номеру строки и столбца. Тогда для этих номеров строки и столбца придётся предусмотреть отдельные ячейки, например, так:

Увы, всё это ничего не даст - вместо $A$1 мы просто вынуждены будем закрепить в формуле ДВССЫЛ($F$8) и всё равно потом перетаскивать столько же ссылок при копировании формулы. Кроме того, "вручную" введённые номера строки и столбца придётся ещё и проверять на допустимость (хотя бы как на рисунке), так что, не будем умножать сущностей.

Посмотреть метод в работе можно на двух первых листах приложенного файла Excel (2 разных примера).

На преобразовании Жордана-Гаусса основан и такой универсальный метод решения линейных задач оптимизации, как симплекс-метод . Описания его обычно страшны, длинны и перегружены теоремами. Попробуем сделать простое описание и разработать пригодный для расчёта в Excel алгоритм. На самом деле, симплекс-метод уже встроен в стандартную надстройку Пакет анализа, и программировать его "вручную" не нужно, так что наш код имеет, скорее, учебную ценность.

Сначала минимум теории.

Если вектор-столбцы СЛАУ линейно независимы, соответствующие им переменные являются базисными , а остальные – свободными . Например, в СЛАУ

переменные x 2 и x 4 - базисные, а x 1 и x 3 - свободные. Базисные переменные между собой независимы, а свободные можно сделать, например, нулями и получить { x 2 =2, x 4 =1 } – базисное решение системы.

Выбирая различные разрешающие элементы, можно получить решения СЛАУ с различными базисами. Любое неотрицательное базисное решение СЛАУ называется опорным .

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

Алгоритм симплекс-метода состоит в следующем:

1. Задача ЛП преобразуется к каноническому виду:

Это всегда можно сделать следующим образом: к задаче, записанной в стандартной постановке

добавляются дополнительные балансовые переменные , число которых соответствует числу ограничений-неравенств m (ограничения на неотрицательность значений неизвестных не учитываются). После этого неравенства со знаком " ≤ " превращаются в равенства, например, система ограничений вида

2*x 1 +3*x 2 ≤20
3*x 1 +x 2 ≤15
4*x 1 ≤16
3*x 2 ≤12
x 1 ,x 2 ≥0

примет вид

2*x 1 +3*x 2 +x 3 =20
3*x 1 +x 2 +x 4 =15
4*x 1 +x 5 =16
3*x 2 +x 6 =12
x 1 ,x 2 ,...,x 6 ≥0

То есть, "экономический" смысл балансовых переменных очень прост – это "остатки" неиспользованных ресурсов каждого вида.

Если в исходной задаче искался не минимум, а максимум, целевая функция Z заменятся на Z 1 = -Z . Решения задач совпадают, при этом min Z = - max Z 1 . Например, цель

Z(x 1 ,x 2)=2*x 1 +5*x 2 (max)

переписывается в виде

Z 1 (x 1 ,x 2)=-2*x 1 -5*x 2 (min)

Если в исходной задаче были уравнения-неравенства со знаками " ≥ " вместо " ≤ ", обе части каждого такого неравенства умножаются на -1 , а знак неравенства меняется на противоположный, например,

3*x 1 +x 2 +x 4 ≥15

превращается в

3*x 1 -x 2 -x 4 ≤15

Канонический вид модели получен, для него выписывается симплекс-таблица :

В левом столбце записываются базисные переменные (БП), если они ещё не выделены – пусто.

2. С помощью шагов Жордана–Гаусса ищется первоначальный опорный план, т.е. СЛАУ приводится к базисному виду с неотрицательными свободными членами b i >0 . При этом целевая функция Z должна быть выражена только через свободные неизвестные (нулевые коэффициенты в Z-строке стоят только под переменными x i , которые есть в базисе). При выборе разрешающего элемента a r,s в строку r столбца БП выписываем переменную x s , если там уже была переменная – вычеркиваем её (выводим из базиса).

3. Выписываем под столбцами x i опорный план X * : под свободными переменными - нули, под базисными – соответствующие базисной переменной коэффициенты из столбца b .

Ниже выписываем вектор R по правилу: под базисными переменными – нули, под свободными R i =Z i .

Если все R i ≥0 , найдено оптимальное решение X * и значение цели Z min = -q , иначе нужен новый план, а у вас он есть, товарищ Жюков? (п. 4).

4. Для выбора разрешающего столбца s выбираем максимальную по модулю отрицательную компоненту вектора R , разрешающий столбец s выбран. Затем анализируем коэффициенты s-го столбца матрицы системы ограничений. Если все a i,s ≤0 , решения нет и Z min стремится к минус бесконечности, иначе переходим к п.5.

5. Для выбора разрешающей строки r составляем неотрицательные отношения b i /A i,s ≥0 , i=1,2,...,m , и выбираем среди них наименьшее. Если минимум достигается для нескольких строк, за разрешающую можно принять любую из них, при этом, в новом опорном плане значения некоторых базисных переменных станут равными 0, т.е., получаем вырожденный опорный план.

6. Выполняем преобразование Жордана-Гаусса с разрешающим элементом a r,s и переходим к п.3

Геометрически симплекс-методу соответствует кратчайший обход вершин n-мерного выпуклого многогранника, образующего область допустимых решений задачи:

Здесь мы перешли от опорного плана C , представляющего собой одну из вершин многомерного многоугольника, к оптимальному плану E=X * .

Запрограммировать это всё в Excel нелегко, но можно. В прилагаемом документе приведены 3 примера, реализующие решение задач симплекс-методом. Правда, при выполнени шага менять уже придётся 3 формулы, на листе первого примера на симплекс-метод они выделены жёлтым цветом: расчёт отношений для выбора разрешающей строки в ячейке I2 , заполнение столбца БП в ячейке A12 , шаг преобразования Жордана-Гаусса в ячейке B12 . Как и в примере на преобразование Жордана-Гаусса, изменение формул связано только с необходимостью сослаться на новую строку, содержащую адрес ячейки с разрешающим элементом (для первого шага - ячейка C9).

. Алгоритм симплекс-метода

Пример 5.1. Решить следующую задачу линейного программирования симплекс-методом:

Решение:

I итерация:

х3 , х4 , х5 , х6 х1 ,х2 . Выразим базисные переменные через свободные:

Приведем целевую функциюк следующему виду:

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

Таблица 5.3

Исходная симплекс-таблица

				Оценочные отношения

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

3 этап: проверка совместности системы ограничений ЗЛП.

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

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

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

6 этап: проверка оптимальности.

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

Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1 » и колонка «х2 ». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2 » содержит наименьший элемент (–3) в сравнении с колонкой «х1

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

Таблица 5.4

Исходная симплекс-таблица

В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5 », следовательно, она будет разрешающей.

Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5 » и колонки «х2 ».

Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х5 и х2 , в новой симплекс-таблице (таблице 5.5) их меняем местами.

9.1. Преобразование разрешающего элемента.

Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:

Полученный результат вписываем в аналогичную клетку таблицы 5.5.

9.2. Преобразование разрешающей строки.

Элементы разрешающей строки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей строки приведены в таблице 5.5.

9.3. Преобразование разрешающей колонки.

Элементы разрешающей колонки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, а результат берется с обратным знаком. Полученные результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей колонки приведены в таблице 5.5.

9.4. Преобразование остальных элементов симплекс-таблицы.

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

К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «х3 » и колонки «», условно обозначим его «х3 ». В таблице 5.4 мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т.е. в клетке «х3 »), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «х3 » будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы 5.4), а в числителе произведение двух других неиспользованных вершин, т.е.:

«х3 »: .

Аналогично преобразуются значения других клеток:

«х3 х1 »: ;

«х4 »: ;

«х4 х1 »: ;

«х6 »: ;

«х6 х1 »: ;

«»: ;

«х1 »: .

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

II итерация:

1 этап: составление симплекс-таблицы.

Таблица 5.5

Симплекс-таблица II итерации

				Оценочные отношения

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):

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

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

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

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.5, такой колонкой является только одна колонка: «х1 ». Следовательно, ее принимаем в качестве разрешенной.

8.2. Определение разрешающей строки.

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

Таблица 5.6

Симплекс-таблица II итерации

				Оценочные отношения
				3/1=3 – min

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.

III итерация

По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:

Таблица 5.7

Симплекс-таблица III итерации

				Оценочные отношения

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.

6 этап: проверка оптимальности найденного базисного решения.

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

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.7, такой колонкой является только одна колонка: «х5 ». Следовательно, ее принимаем в качестве разрешенной.

8.2. Определение разрешающей строки.

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

Таблица 5.8

Симплекс-таблица III итерации

				Оценочные отношения
				5/5=1 – min

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.

IV итерация

1 этап: построение новой симплекс-таблицы.

По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:

Таблица 5.9

Симплекс-таблица IV итерации

				Оценочные отношения
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение, согласно таблице 5.9 решение следующее:

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.

6 этап: проверка оптимальности найденного базисного решения.

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

7 этап: проверка альтернативности решения.

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

Ответ: оптимальное значение целевой функции рассматриваемой задачи =24, которое достигается при.

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

Решение:

I итерация:

1 этап: формирование исходной симплекс-таблицы.

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

В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3 , х4 , х5 , х6 , тогда свободными переменными будут х1 ,х2 . Выразим базисные переменные через свободные.