Линейное программирование. Определение оптимального решения задачи линейного программирования Прибыль от продажи пакета

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

1. наличия хотя бы одного критерия,
2. наличия не менее двух сравниваемых вариантов (необходимость осуществления выбора).

Каждый выбор лучшего варианта конкретен, поскольку производится на соответствие определённым критериям. Следовательно, говоря об оптимальном варианте, всегда нужно указывать эти критерии (то есть «оптимальный по …»). И то, что может быть оптимальным при одном критерии, не обязательно будет таковым при другом. Например, сцена, «оптимальная по площади», не обязательно будет «оптимальной по акустике».

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

Примечания

Wikimedia Foundation . 2010 .

• Оптиконевромиелит
• Оптиматы (фема)

Смотреть что такое "Оптимальное решение" в других словарях:

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

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

Оптимальное управление - Оптимальное управление это задача проектирования системы, обеспечивающей для заданного объекта управления или процесса закон управления или управляющую последовательность воздействий, обеспечивающих максимум или минимум заданной… … Википедия

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

решение - сущ., с., употр. часто Морфология: (нет) чего? решения, чему? решению, (вижу) что? решение, чем? решением, о чём? о решении; мн. что? решения, (нет) чего? решений, чему? решениям, (вижу) что? решения, чем? решениями, о чём? о решениях 1. Решением … Толковый словарь Дмитриева

оптимальное - найти оптимальное решение существование / создание … Глагольной сочетаемости непредметных имён

ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ПОЗИЦИОННОЕ - решение задачи оптимального управления математической теории, состоящей в синтезе оптимального управления в виде стратегии управления по принципу обратной связи, как функции текущего состояния (позиции) процесса (см. ). Последнее… … Математическая энциклопедия

ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ПРОГРАММНОЕ - решение задачи оптимального управления математической теории, в к рой управляющее воздействие u=u(t).формируется в виде функции времени (тем самым предполагается, что по ходу процесса никакой информации, кроме заданной в самом начале, в систему… … Математическая энциклопедия

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

Оптимальное управление - летательным аппаратом раздел динамики полёта, посвящённый развитию и использованию методов оптимизации для определения законов управления движением летательного аппарата и его траекторий, обеспечивающих максимум или минимум выбранного критерия… … Энциклопедия техники

Книги

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

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

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

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

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

1. пакет «Чистое стекло » стоимостью 3600 руб., в который входит комплекс работ по диагностике и осмотру автомобиля, очистка внутренней поверхности стекол автомобиля с применением специального спрея (плюс один флакон спрея в подарок); заливка в омывательный бачок стеклоочищающей жидкости (плюс одна бутыль стеклоочищающей жидкости в подарок);
2. 2) пакет «Свежий воздух » стоимостью 4300 руб., в который входит комплекс работ по диагностике и осмотру автомобиля, включая работы по очистке и дезинфекции кондиционера автомобиля с применением специального средства; очистка внутренней поверхности стекол автомобиля с применением специального спрея; заливка в омывательный бачок стеклоочищающей жидкости.

В табл. 1 представлен комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов).

Таблица 1. Комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов)

Работа	Пакет «Чистое стекло»	Пакет «Свежий воздух»
Проверка уровня моторного масла
Проверка уровня и плотности охлаждающей жидкости
Проверка уровня тормозной жидкости
Проверка состояния салонного фильтра
Визуальный контроль герметичности агрегатов
Визуальная проверка состояния тормозных дисков и колодок
Проверка тормозной системы на испытательном стенде
Корректировка давления в шинах
Функциональная проверка стеклоочистителей и стеклоомывателей
Проверка резиновых щеток стеклоочистителя на износ и наличие трещин
Проверка состояния радиатора охлаждения на предмет загрязнения
Проверка и корректировка фар
Проверка заряда аккумуляторной батареи
Короткий тест с помощью диагностической программы
Очистка и дезинфекция кондиционера
Итого

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

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

1. 1. Привлечение клиентов.
2. 2. Сбыт залежавшихся сезонных товаров (автохимия).
3. 4. Получение дополнительной прибыли.
4. По задумке менеджмента организации, количество пакетов ограничено :

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

Таким образом, ресурсы, выделяемые на проведение данной акции, ограничены. Ограничения по ресурсам на проведение сезонной акции представлены в табл. 2.

Таблица 2. Ограничения по ресурсам на проведение сезонной акции

Задействованные ресурсы	Расход ресурсов		Запас ресурсов
	пакет «Чистое стекло»	пакет «Свежий воздух»
Работа механика, ч
Спрей для очистки внутренней поверхности стекла, уп.
Стеклоомывающая жидкость, уп.
Жидкость для очистки и дезинфекции кондиционера, уп.

На проведение сезонной акции может быть выделено не более :

• 320 флаконов спрея для очистки внутренней поверхности стекла;
• 260 бутылей стеклоомывающей жидкости;
• 150 бутылей жидкости для очистки и дезинфекции кондиционера.

К тому же ограничено время работы механиков: в апреле 22 рабочих дня, продуктивный рабочий день механика - 7 ч в день. Следовательно, располагаемый фонд рабочего времени четырех механиков равен 616 ч (4 x 22 x 7).

Всего на один пакет «Чистое стекло » необходимо затратить:

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

На пакет «Свежий воздух » необходимо затратить:

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

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

• X 1 - количество пакетов «Чистое стекло»;
• Х 2 - количество пакетов «Свежий воздух»;
• A - количество часов механика;
• B - количество флаконов спрея для внутренней очистки стекол;
• C - количество бутылей стеклоомывающей жидкости;
• D - количество бутылей жидкости для очистки и дезинфекции кондиционеров.

1) во-первых, количество пакетов не может быть отрицательным: Х1, Х2 ≥ 0;

2) во-вторых, расход ресурсов не должен превышать имеющиеся запасы. Это можно выразить при помощи неравенств:

• по ресурсу А : 2,5 x Х 1 + 3,6 x Х 2 ≤ 616;
• по ресурсу В : 2 x Х 1 + 1 x Х 2 ≤ 320;
• по ресурсу С : 2 x Х 1 + 1 x Х 2 ≤ 260;
• по ресурсу D : 0 x Х 1 + 1 x Х 2 ≤ 150.

Затем следует определиться с целевой функцией (направлением для оптимизации). Логично было бы распределить квоту на оказание пакетов услуг таким образом, чтобы предприятие получило максимальную прибыль. Для этого нужно рассчитать, сколько прибыли приносит продажа одного пакета услуг, то есть сопоставить цену реализации пакета и стоимость затрачиваемых ресурсов. Как уже говорилось выше, стоимость пакета «Чистое стекло» составляет 3600 руб., а пакета «Свежий воздух » - 4300 руб. Данные суммы необходимо сопоставить с затратами на выполнение услуг :

• тарифная часовая ставка механика составляет 350 руб. за нормо-час (включая налоги и взносы с ФОТ);
• стоимость флакона жидкости для очистки внутренней поверхности стекла - 661 руб.;
• стоимость бутыли стеклоочищающей жидкости - 250 руб.;
• стоимость бутыли жидкости для очистки и дезинфекции кондиционеров - 1589 руб.

Расчет прибыли от реализации каждого из пакетов на основании имеющихся данных представлен в табл. 3.

Таблица 3. Прибыль от реализации пакетов услуг, руб.

Ресурс	Цена ресурса	Пакет «Чистое стекло»	Пакет «Свежий воздух»
Затраты на оплату труда механика
Затраты на спрей для очистки стекол
Затраты на стеклоомывающую жидкость
Затраты на жидкость для очистки и дезинфекции кондиционера
Итого затраты на пакет
Стоимость пакета
Прибыль от продажи пакета

Итак, продажа одного пакета «Чистое стекло » принесет предприятию 903 руб. прибыли, а пакета «Свежий воздух » - 540 руб.

Целевая функция (Z ) в данном случае примет вид:

Z = 903 x Х 1 + 540 x Х 2.

Задача - найти максимум целевой функции с учетом существующих ограничений:

• 2,5 x Х 1 + 3,6 x Х 2 ≤ 616;
• 2 x Х 1 + 1 x Х 2 ≤ 320;
• 2 x Х 1 + 1 x Х 2 ≤ 260;
• 1 x Х 2 ≤ 150;
• Х 1, Х 2 ≥ 0.

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

Для решения нашей задачи симплекс-методом ее нужно привести к так называемому стандартному виду : преобразовать неравенства нашей системы ограничений в равенства, добавив в левую часть каждого из уравнений неотрицательные числа (назовем их Х 3, Х 4, Х 5 и Х 6), которые называются балансовыми переменными (переменные Х 1 и Х 2 называются свободными). Получится следующая система уравнений:

• 2,5 x Х 1 + 3,6 x Х 2 + Х 3 = 616;
• 2 x Х 1 + 1 x Х 2 + Х 4 = 320;
• 2 x Х 1 + 1 x Х 2 + Х 5 = 260;
• 1 x Х 2 + Х 6 = 150;
• Х 1, Х 2, Х 3, Х 4, Х 5, Х 6 ≥ 0.

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

• построение первой симплекс-таблицы;
• последовательное преобразование симплекс-таблиц по определенному алгоритму, до выполнения определенных условий.

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

Z – 903 x Х 1 – 540 x Х 2 = 0.

Теперь строим первую симплекс-таблицу. Столбцами будут переменные Х 1–Х 6, а строками - имеющиеся ресурсы (А, В, С, D ). На пересечении строки и столбца находятся коэффициенты перед переменными по каждому виду ресурса в нашей системе ограничений. Так, по строке А (время работы механиков) в столбце Х 1 будет стоять коэффициент 2,5; в столбце Х 2 - 3,6; в столбце Х 3 - 1, а в Х 4–Х 6 - 0.

Также вводится дополнительный столбец (назовем его b ), в котором стоят ограничения по каждому из ресурсов. После этого вводится дополнительная строка Е , в которой содержатся коэффициенты в нашей целевой функции (Z – 903 x Х 1 – 540 x Х 2 = 0). Получилась следующая симплекс-таблица, представленная в табл. 4.

Таблица 4. Первая симплекс-таблица

Ресурс	X 1	X 2	X 3	X 4	X 5	X 6	b
A
B
C
D
Е

Значение функции Z равно числу, стоящему в правом нижнем углу табл. 4. Последующее преобразование симплекс-таблицы связано с выбором разрешающей строки и разрешающего столбца.

Разрешающим столбцом является тот столбец, у которого коэффициенты в целевой функции (строка Е) являются отрицательными и наибольшими по модулю. В данной таблице это будет столбец Х 1 , у которого по строке Е стоит значение –903. Следует заметить, что преобразование симплекс-таблиц будет происходить до тех пор, пока в строке Е не останется отрицательных значений.

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

Для нашей первой симплекс-таблицы разрешающей будет строка С , так как именно в ней наименьшее соотношение элемента столбца b и элемента разрешающего столбца Х 1 (260 / 2 = 130). Элемент таблицы, который находится на пересечении разрешающего столбца и разрешающей строки, называется разрешающим элементом (в табл. 4 ячейка данного элемента выделена цветом).

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

Преобразование осуществляется определенными методами :

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

Выполним предложенные преобразования. Чтобы приравнять разрешающий элемент к единице, разделим все элементы разрешающей строки на 2. Затем из элементов строки А С , умноженные на 2,5. Далее из элементов строки В отнимем элементы разрешающей строки С , умноженные на 2. Со строкой D никаких преобразований не производим (в разрешающем столбце итак стоит нулевое значение). К элементам строки Е С , умноженные на 903. Получилась вторая симплекс-таблица, которая представлена в табл. 5.

Таблица 5. Вторая симплекс-таблица

Ресурс	X 1	X 2	X 3	X 4	X 5	X 6	b
A
B
C
D
Е

Повторяем ту же процедуру, что и с табл. 4. Для начала находим разрешающий столбец (с наибольшим по модулю отрицательным коэффициентом перед целевой функцией). Разрешающим в данном случае будет столбец Х 2. Далее находим разрешающую строку. Это будет строка А , так как для нее выполняется условие минимальности соотношения элемента столбца b к соответствующему элементу разрешающего столбца Х 2 (291 / 2,35 = 123,83).

Элемент на пересечении строки А и столбца Х 2 будет разрешающим. Выполняем преобразование разрешающего элемента в единицу, а остальных элементов столбца Х 2 в нули. Все элементы строки А делим на 2,35. Со строкой В никаких преобразований не производим (в разрешающем столбце и так стоит нулевое значение). Из элементов строки С отнимем элементы разрешающей строки А , умноженные на 0,5 и деленные на 2,35. Из элементов строки D отнимем элементы разрешающей строки А , деленные на 2,35. К элементам строки Е прибавляем элементы разрешающей строки А , умноженные на 88,5 и деленные на 2,35. Получилась третья симплекс-таблица, которая представлена в табл. 6.

Таблица 6. Третья симплекс-таблица

Ресурс	X 1	X 2	X 3	X 4	X 5	X 6	b
A
B
C
D
Е

В полученной симплекс-таблице в строке Е , содержащей коэффициенты целевой функции, нет отрицательных значений, следовательно вычисление завершено. Значения переменных Х 1 и Х 2 расположены в столбце b на тех строках, в которых в столбцах Х 1 и Х 2 стоят единицы. Соответственно, Х 1 = 68,0851, а Х 2 = 123,8298. Значение целевой функции при таких переменных будет равно:

Z = 903 x 68,0851 + 540 x 123,8298 = 128 348,94.

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

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

Покажем это на наглядном примере. Для начала следует ввести все данные задачи в рабочий лист MS Excel (рис. 1).

Рис. 1. Ввод данных задачи оптимизации в MS Excel

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

• в ячейки B3:B6 Чистое стекло »;
• в ячейки C3:C6 вводятся нормативы расхода всех ресурсов на продажу одного пакета «Свежий воздух »;
• в ячейки D3:D6 заносят запасы (лимиты расхода) по каждому из ресурсов.

Для того чтобы посчитать общий расход ресурсов и соотнести его с запасами, необходимо ввести данные о количестве проданных пакетов (ячейки В16 и С16 ). Для начала проставим там единичные значения (как будто продано по одному сезонному пакету). Общий расход ресурсов рассчитывается в диапазоне ячеек A8:D13 , в котором количество проданных пакетов (ячейки В16 и С16 ) умножается на норматив расхода (диапазоны B3:B6 и C3:C6 ). В диапазоне D10:D13 рассчитывается суммарный расход по каждому из ресурсов.

Так, например, расход нормо-часов механиков по пакету «Чистое стекло» производится в ячейке В10 путем умножения значений ячейки В16 Чистое стекло ») на ячейку В3 Чистое стекло »). Расход нормо-часов механиков по пакету «Свежий воздух » производится в ячейке С10 путем умножения значений ячейки С16 (количество проданных пакетов «Свежий воздух ») на ячейку С3 (норматив выполнения работ по пакету «Свежий воздух »).

Итоговое значение расхода часов механиков рассчитывается в ячейке D10 путем сложения значений ячеек В10 и С10 (сумма в ячейке D10 не должна превышать лимит, установленный в ячейке D3 ).

Также на рабочем листе идет расчет прибыли от продажи пакетов (ячейки В18 и С18 ). Для этого размер прибыли от продажи одного пакета (значения проставлены в ячейках В17 и С17 ) умножается на количество проданных пакетов (ячейки В16 и С16 ). В ячейке D18 стоит итоговое значение прибыли.

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

Воспользуемся инструментом «Поиск решения » (находим в меню «Данные» - «Анализ»). Диалоговое окно представлено на рис. 2.



Рис. 2. Диалоговое окно инструмента «Поиск решения»

По условиям поставленной задачи необходимо установить в целевую ячейку D18 (общая прибыль от продажи пакетов) максимальное значение, изменяя ячейки В16:С16 (количество проданных пакетов «Чистое стекло » и «Свежий воздух »).

При этом должны быть прописаны все ограничения нашей задачи:

• В16 и С16 >= 0 (количество проданных пакетов неотрицательно);
• D10 <= D3 (расход нормо-часов механиков не превышает имеющийся фонд рабочего времени);
• D11 <= D4 (расход спрея для очистки стекол не превышает складских остатков);
• D12 <= D5 (расход стеклоочищающей жидкости не превышает складских остатков);
• D13 <= D6 (расход жидкости для очистки и дезинфекции кондиционеров не превышает складских остатков).

После ввода ограничений нажимаем кнопку «Выполнить ». Ячейки В16 и С16 заполняются автоматически. В целевой ячейке D18 получается значение прибыли. На рис. 3 представлены результаты вычислений.



Рис. 3. Результаты вычислений

Как видно из рис. 3, результаты вычислений получились аналогичными тем, что были достигнуты при помощи симплекс-таблиц. Однако эти данные, как уже говорилось выше, не могут быть приняты по причине своей нецелочисленности. Чтобы устранить данный недостаток, необходимо в диалоговом окне инструмента «Поиск решения» прописать дополнительные условия (рис. 4).



Рис. 4. Диалоговое окно инструмента «Поиск решения» с добавлением условия целочисленности

Результаты вычисления после добавления условия целочисленности показаны на рис. 5.



Рис. 5. Результаты вычисления после добавления условия целочисленности

Полученные данные удовлетворяют всем заданным условия. Если руководство предприятия выделит на проведение сезонной акции 69 пакетов «Чистое стекло » и 122 пакета «Свежий воздух », то за счет имеющихся в распоряжении ресурсов будет получена максимальная прибыль, которая составит 128 187 руб.

Заключение

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

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

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

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

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

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

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

В табл. 1 представлен комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов).

Таблица 1. Комплекс работ по диагностике и осмотру автомобиля (количество нормо-часов)
Работа	Пакет «Чистое стекло»	Пакет «Свежий воздух»
Проверка уровня моторного масла
Проверка уровня и плотности охлаждающей жидкости
Проверка уровня тормозной жидкости
Проверка состояния салонного фильтра
Визуальный контроль герметичности агрегатов
Визуальная проверка состояния тормозных дисков и колодок
Проверка тормозной системы на испытательном стенде
Корректировка давления в шинах
Функциональная проверка стеклоочистителей и стеклоомывателей
Проверка резиновых щеток стеклоочистителя на износ и наличие трещин
Проверка состояния радиатора охлаждения на предмет загрязнения
Проверка и корректировка фар
Проверка заряда аккумуляторной батареи
Короткий тест с помощью диагностической программы
Очистка и дезинфекция кондиционера
Итого

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

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

1. Привлечение клиентов.

2. Сбыт залежавшихся сезонных товаров (автохимия).

4. Получение дополнительной прибыли.

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

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

во-вторых , срок проведения акции органичен одним месяцем (апрелем);

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

Таким образом, ресурсы, выделяемые на проведение данной акции, ограничены. Ограничения по ресурсам на проведение сезонной акции представлены в табл. 2.

Таблица 2. Ограничения по ресурсам на проведение сезонной акции
Задействованные ресурсы	Расход ресурсов		Запас ресурсов
	пакет «Чистое стекло»	пакет «Свежий воздух»
Работа механика, ч
Спрей для очистки внутренней поверхности стекла, уп.
Стеклоомывающая жидкость, уп.
Жидкость для очистки и дезинфекции кондиционера, уп.

На проведение сезонной акции может быть выделено не более :

• 320 флаконов спрея для очистки внутренней поверхности стекла;

• 260 бутылей стеклоомывающей жидкости;

• 150 бутылей жидкости для очистки и дезинфекции кондиционера.

К тому же ограничено время работы механиков: в апреле 22 рабочих дня, продуктивный рабочий день механика — 7 ч в день. Следовательно, располагаемый фонд рабочего времени четырех механиков равен 616 ч (4 × 22 × 7).

Всего на один пакет «Чистое стекло » необходимо затратить:

• 2,5 ч работы механика;

• 2 флакона спрея для очистки внутренней поверхности стекла (один использовать, один — в подарок);

• 2 бутыли стеклоомывающей жидкости (одну использовать, одну — в подарок).

На пакет «Свежий воздух » необходимо затратить:

• 3,6 ч работы механика;

• 1 флакон спрея для очистки внутренней поверхности стекла;

• 1 бутыль стеклоомывающей жидкости и одну бутыль жидкости для очистки и дезинфекции кондиционера.

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

X 1 — количество пакетов «Чистое стекло»;

Х 2 — количество пакетов «Свежий воздух»;

A — количество часов механика;

B — количество флаконов спрея для внутренней очистки стекол;

C — количество бутылей стеклоомывающей жидкости;

D — количество бутылей жидкости для очистки и дезинфекции кондиционеров.

1) во-первых, количество пакетов не может быть отрицательным: Х1, Х2 ≥ 0;

2) во-вторых, расход ресурсов не должен превышать имеющиеся запасы. Это можно выразить при помощи неравенств:

по ресурсу А : 2,5 × Х 1 + 3,6 × Х 2 ≤ 616;

по ресурсу В : 2 × Х 1 + 1 × Х 2 ≤ 320;

по ресурсу С : 2 × Х 1 + 1 × Х 2 ≤ 260;

по ресурсу D : 0 × Х 1 + 1 × Х 2 ≤ 150.

Затем следует определиться с целевой функцией (направлением для оптимизации). Логично было бы распределить квоту на оказание пакетов услуг таким образом, чтобы предприятие получило максимальную прибыль. Для этого нужно рассчитать, сколько прибыли приносит продажа одного пакета услуг, то есть сопоставить цену реализации пакета и стоимость затрачиваемых ресурсов. Как уже говорилось выше, стоимость пакета «Чистое стекло» составляет 3600 руб., а пакета «Свежий воздух » — 4300 руб. Данные суммы необходимо сопоставить с затратами на выполнение услуг :

тарифная часовая ставка механика составляет 350 руб. за нормо-час (включая налоги и взносы с ФОТ);

стоимость флакона жидкости для очистки внутренней поверхности стекла — 661 руб.;

стоимость бутыли стеклоочищающей жидкости — 250 руб.;

стоимость бутыли жидкости для очистки и дезинфекции кондиционеров — 1589 руб.

Расчет прибыли от реализации каждого из пакетов на основании имеющихся данных представлен в табл. 3.

Таблица 3. Прибыль от реализации пакетов услуг, руб.
Ресурс	Цена ресурса	Пакет «Чистое стекло»	Пакет «Свежий воздух»
Затраты на оплату труда механика
Затраты на спрей для очистки стекол
Затраты на стеклоомывающую жидкость
Затраты на жидкость для очистки и дезинфекции кондиционера
Итого затраты на пакет
Стоимость пакета
Прибыль от продажи пакета

Итак, продажа одного пакета «Чистое стекло » принесет предприятию 903 руб. прибыли, а пакета «Свежий воздух » — 540 руб.

Целевая функция (Z ) в данном случае примет вид.

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

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

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

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

Рассмотрим симплексный метод на конкретном примере задачи о составлении плана.

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

Рассмотрим задачу о плане производства, предварительно построив модель и приведя ее к специальному виду.

Задача.

Для изготовления изделий А и В склад может отпустить сырья не более 80 единиц. Причем на изготовление изделия А расходуется две единицы, а изделия В - одна единица сырья. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий А требуется изготовить не более 50 шт., а изделий В - не более 40 шт. Причем, прибыль от реализации одного изделия А - 5 руб., а от В - 3 руб.

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

x 1 ≤50
x 2 ≤40
2x 1 +x 2 ≤80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max

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

x 1 +x 3 =50
x 2 +x 4 =40
2x 1 +x 2 +x 5 =80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max
-F = -5x 1 - 3x 2 → min.

Эта задача имеет специальный вид (с базисом, правые части неотрицательны). Ее можно решить симплекс-методом.

I этап. Запись задачи в симплекс-таблицу. Между системой ограничений задачи (3.10) и симплекс-таблицей взаимно-однозначное соответствие. Строчек в таблице столько, сколько равенств в системе ограничений, а столбцов - столько, сколько свободных переменных. Базисные переменные заполняют первый столбец, свободные - верхнюю строку таблицы. Нижняя строка называется индексной, в ней записываются коэффициенты при переменных в целевой функции. В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена; если есть, то записываем его с противоположным знаком. На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблицы к другой должно увеличиваться по модулю. Итак, нашей системе ограничений соответствует таблица 3.4, и можно переходить ко II этапу решения.

Таблица 3.4

базисные			свободные

II этап . Проверка опорного плана на оптимальность.

Данной таблице 3.4 соответствует следующий опорный план:

(х 1 , х 2 , х 3 , х 4 , х 5) = (0, 0, 50, 40, 80).

Свободные переменные х 1 , х 2 равны 0; х 1 = 0, х 2 = 0. А базисные переменные х 3 , х 4 , х 5 принимают значения х 3 = 50, х 4 = 40, х 5 = 80 - из столбца свободных членов. Значение целевой функции:

-F = - 5х 1 - 3х 2 = -5 · 0 - 3 · 0 = 0.

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

Возможны различные ситуации.

1. В индексной F -строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятому с противоположным знаком. Переходим к IV этапу.

2. В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция F →∞ неограниченно убывает.

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

III этап . Улучшение опорного плана.

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

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

В нашем примере, элемент 2 - разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей (табл. 3.5).

Таблица 3.5

Выбрав разрешающий элемент, делаем перечет таблицы по правилам:

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

Таблица 3.6

2. На месте разрешающего элемента 2 записываем обратное ему число ½.

3. Элементы разрешающей строки делим на разрешающий элемент.

4. Элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком.

5. Чтобы заполнить оставшиеся элементы таблицы 3.6, осуществляем пересчет по правилу прямоугольника. Пусть мы хотим посчитать элемент, стоящий на месте 50.

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

Итак, . Записываем 10 на место, где было 50. Аналогично:
, , , .

Таблица 3.7

Имеем новую таблицу 3.7, базисными переменными теперь являются переменные {x 3 ,x 4 ,x 1 }. Значение целевой функции стало равно -200, т.е. уменьшилось. Чтобы проверить данное базисное решение на оптимальность надо перейти опять ко II этапу. Процесс, очевидно, конечен, критерием остановки являются пункт 1 и 2 II этапа.

Доведем решение задачи до конца. Для этого проверим индексную строку и, увидев в ней отрицательный элемент -½, назовем соответствующий ему столбец разрешающим и, согласно III этапу, пересчитаем таблицу. Составив отношения и выбрав среди них минимальное = 40, определили разрешающий элемент 1. теперь пересчет осуществляем согласно правилам 2-5.

Таблица 3.8

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

IV этап . Выписывание оптимального решения.

Если симплекс-метод остановился согласно пункту 1 II этапа, то решение задачи выписывается следующим образом. Базисные переменные принимают значения столбца свободных членов соответственно. В нашем примере х 3 = 30, х 2 = 40, х 1 = 20. Свободные переменные равны 0, х 5 = 0, х 4 = 0. Целевая функция принимает значение последнего элемента столбца свободных членов с противоположным знаком: -F = -220 → F = 220, в нашем примере функция исследовалась на min, и первоначально F → max, поэтому фактически знак поменялся дважды. Итак, х * = (20, 40, 30, 0, 0), F * = 220. Ответ к задаче:

Необходимо в план выпуска включить 20 изделий типа А , 40 изделий типа В, при этом прибыль будет максимальной и будет равна 220 руб.

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

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

Пример . Решить следующую задачу ЛП в канонической форме симплекс-методом.
f(x)=x 1 +9x 2 +5x 3 +3x 4 +4x 5 +14x 6 → min
x 1 +x 4 =20
x 2 +x 5 =50
x 3 +x 6 =30
x 4 +x 5 +x 6 =60
x i ≥ 0, i = 1,…,6
Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид равенств, а все свободные члены неотрицательны. Так что мы имеем задачу в канонической форме.
Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число "шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).
Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП.
Решение. Чтобы найти начальное допустимое базисное решение, т.е. чтобы определить базисные переменные, систему (5.6) нужно привести к "диагональному" виду. Применяя метод Гаусса (метод последовательного исключения неизвестных), получаем из (5.6):
x 2 +x 1 +x 3 =40
x 4 +x 1 =20
x 5 -x 1 -x 3 =10
x 6 +x 3 =30
Следовательно, базисными являются переменные x 2 , x 4 , x 5 , x 6 , им придаем значения, равные свободным членам соответствующих строк: x 2 =40, x 4 =20, x 5 =10, x 6 =30, . Переменные x 1 и x 3 являются небазисными: x 1 =0, x 3 =0 .
Построим начальное допустимое базисное решение
x 0 = (0,40,0,20,10,30) (5.9)
Для проверки на оптимальность найденного решения x 0 нужно из целевой функции исключить базисные переменные (с помощью системы (5.8)) и построить специальную симплекс таблицу.
После исключения переменных целевую функцию удобно записать в виде:
f(x) = -7x 1 – 14x 3 +880 (5.10)
Теперь при помощи (5.8) –(5.10) составляем начальную симплекс-таблицу:

В нулевую строчку записаны коэффициенты с обратным знаком соответствующих переменных при целевой функции. Критерий оптимальности (для задачи на поиск минимума): допустимое базисное решение(x 0 ) оптимально, если в нулевой строчке нет ни одного строго положительного числа (не считая значения целевой функции (880)). Это правило распространяется и на следующие итерации (таблицы). Элементы нулевой строки будем называть оценками столбцов.
Так что начальное допустимое базисное решение (5.9) неоптимально: 7>0, 14>0 .
В нулевом столбике записаны значения базисных переменных. Они обязательно должны быть неотрицательными (см. уравнение (5.7)). От первой по четвертую строки написаны коэффициенты переменных из системы (5.8).
Так как x 0 неоптимально, то надо перейти к другой вершине многогранника допустимых решений (построить новое д.б.р.). Для этого нужно найти ведущий элемент и провести определенное преобразование (симплексное преобразование).
Сначала находим ведущий элемент таблицы, который стоит в пересечении ведущего столбика (столбец с наибольшей положительной оценкой) и ведущей строки (строки, соответствующей минимальному соотношению элементов нулевого столбика к соответствующим элементам (строго положительным) ведущего столбика).
В таблице 1 ведущий столбик - третий столбик, и ведущая строка - четвертая строка (min{40/1,30/1}=30/1) обозначены стрелками, а ведущий элемент - кружочком. Ведущий элемент показывает, что базисную переменную x 6 нужно заменить на небазисную x 3 . Тогда новыми базисными переменными будут x 2 , x 3 , x 4 , x 5 , , а небазисными -x 1 , x 6 , . Это и означает переход к новой вершине многогранника допустимых решений. Чтобы найти значения координат нового допустимого базисного решения x 00 нужно строить новую симплекс-таблицу и провести в ней элементарные преобразования:
а) все элементы ведущей строки поделить на ведущий элемент, превратив этим самым ведущий элемент в 1 (для простоты выкладок);
б) с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения неизвестных);
В результате в нулевом столбце получены значения новых базисных переменных x 2 , x 3 , x 4 , x 5 , (см. таблицу 2) - базисные компоненты новой вершины x 00 (небазисные компоненты x 1 =0, x 6 =0, ).

Как показывает таблица 2, новое базисное решение x 00 =(0,10,30,20,40,0) неоптимально (в нулевой строке есть неотрицательная оценка 7). Поэтому с ведущим элементом 1 (см. таблицу 2) строим новую симплекс-таблицу, т.е. строим новое допустимое базисное решение

Таблице 3 соответствует допустимое базисное решение x 000 =(10,0,30,10,50,0) и оно оптимально, т.к. в нулевой строчке нет положительных оценок. Поэтому f(x 000)=390 есть минимальное значение целевой функции.
Ответ: x 000 =(10, 0, 30, 10, 50, 0) - точка минимума, f(x 000)=390 .

Условно стандартная задача линейного программирования

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

1. Найти оптимальный план прямой задачи:
   а) графическим методом ;
   б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
2. Построить двойственную задачу .
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план двойственной задачи по первой теореме двойственности , используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).
6. Найти оптимальное целочисленное решение:
   а) графическим методом ;
   б) Методом Гомори .
   Сравнить значения функций целочисленного и нецелочисленного решений

Вопросы для самоконтроля

1. Как строится симплекс-таблица?
2. Как отражается смена базиса в таблице?
3. Сформулируйте критерий остановки симплекс-метода.
4. Как организовать пересчет таблицы?
5. С какой строки удобно начинать пересчет таблицы?

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

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

Рассмотрим следующую задачу линейного программирования в канонической форме:

(1)

(2)

(3)

Метод искусственного базиса

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

Пусть требуется найти максимум функции

при условиях

где первы n элементы нули. Переменные называются искусственными . Векторы столбцы

(28)

образуют так называемый искусственный базис m -мерного векторного пространства.

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

Теорема 4. Если в оптимальном плане расширенной задачи (24)−(26) значения искусственных переменных , то является оптимальным планом задачи (21)−(23).

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

Значение целевой функции при опорном плане (27):

Замечаем, что F(X) и состоят из двух независимых частей, одна из которых зависим от M , а другая − нет.

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

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

Итерационный процесс ведут по m +2 строке до тех пор, пока элементы m +2 строки, соответствующие переменным не станут неотрицательными. При этом, если искусственные переменные исключены из базиса, то найденный план расширенной задачи отвечает некоторому опорному плану исходной задачи.

m +2 строки, столбца x 0 отрицателен, то исходная задача не имеет решения.

Если же не все искусственные переменные исключены из базиса и элемент m +2 строки, столбца x 0 равен нулю, то опорный план исходной задачи является вырожденным и базис содержит минимум один из векторов искусственного базиса.

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

Если в ходе итераций m +2 строка больше не содержит отрицательных элементов, то итерационный процесс продолжают с m +1 строкой, до тех пор, пока не найден оптимальный план расширенной задачи или не выявлен неразрешимость задачи.

Таким образом, процесс нахождения решения задачи линейного программирования (21)−(23) методом искусственного базиса включает следующие основные этапы:

• Составляют расширенную задачу (24)−(26).
• Находят опорный план расширенной задачи.
• Используя симплекс метод исключают искусственные векторы из базиса. В результате находят опорный план исходной задачи или фиксируют ее неразрешимость.
• Используя найденный опорный план ЗЛП (21)−(23), или находят оптимальный план исходной задачи, или устанавливают ее неразрешимость.

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