Решение задачи с помощью Excel и симплекс-методом. Решение ЗЛП симплекс-методом в Excel

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

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

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

Порядок выполнения работы :

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

II. Оформление исходных данных.

Откройте табличный процессор Excel и введите заголовок Табличный способ решения задач линейного программирования .
Заполните начальную симплекс-таблицу.

Шапка таблицы: столбец базисных переменных (B ), столбец свободных членов, имеющиеся переменные.

Следующая строка таблицы соответствует первому ограничению. Базисная переменная , найденная в первом ограничении, свободный член, коэффициенты при переменных соответствующего ограничения. Аналогичным образом заполняются 2 и 3 строки.

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

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

Запишите значение целевой функции , начальный опорный план, опираясь на столбец свободных членов (рис. 27).

Рис. 27 . Значение целевой функции и начальный опорный план.

III. Нахождение оптимального плана и оптимального значения целевой функции.

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

Рис. 28 . Выбор ведущего столбца.

Рис. 29 . Составление отношений.

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

Рис. 30 . Результат отношений.

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

Рис. 31 . Выбор ведущей строки.

На пересечении ведущей строки и ведущего столбца получается ведущий элемент (рис. 32).

Рис. 32 . Ведущий элемент.

Рис. 33 . Новый базис.

Для получения 1 в ячейке С13 необходимо каждый элемент ведущей строки поделить на ведущий элемент.

В ячейку С13 запишите формулу = С5/2 (рис 34), нажмите Enter.

Рис. 34 . Получение 1 в ячейке С13.
Растяните формулу (рис. 35).

Рис. 35 . Первая строка второй симплексной таблицы.
Затем получите нуль в ячейке С14.

Для этого во второй симплексной таблице 1 (ячейка С13) умножьте на элемент предыдущей таблицы, соответствующий элементу ячейки С14, взятый с противоположным знаком и сложите с этим же элементом.

Так как элемент, соответствующий элементу ячейки С14 равен 1 (ячейка С6), то это означает, что все элементы первой строки второй симплексной таблицы умножаются на (-1) и складывается с соответствующими элементами первой симплексной ьаблицы. Запишите в ячейку С14 формулу =C13*(-1)+C6 (рис. 36).

Рис. 36 . Элемент С14 второй симплексной таблицы.
Аналогичным образом получите остальные элементы базисного столбца (рис. 37 и рис. 38).

Рис. 37 . Элемент С15 второй симплексной таблицы.

Рис. 38 . Элемент С16 второй симплексной таблицы.

Растяните формулы базисного столбца по строкам, получите вторую симплексную таблицу (рис. 39).

Рис. 39 . Первая и вторая симплексные таблицы.

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

Рис. 40 . Значение целевой функции и опорного плана второй симплексной таблицы.

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

Рис. 41 . Первая, вторая и третья симплексные таблицы.

Задание. Воспользуйтесь материалами лабораторной работы №3. Выполните проверку, используя программу MathCad.

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

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

прибавление к обеим частям уравнения системы другого уравнения той же системы, умноженного на число, отличное от нуля;
перестановка местами уравнений в системе;
удаление из системы уравнений вида 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).

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

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

создание оптимизационной модели на листе MS EXCEL
настройку Поиска решения;
простой пример (линейная модель).

Установка Поиска решения

Команда Поиск решения находится в группе Анализ на вкладке Данные .

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

На вкладке Файл выберите команду Параметры , а затем - категорию Надстройки ;
В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти;
В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК.

Примечание . Окно Надстройки также доступно на вкладке Разработчик . Как включить эту вкладку .

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

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

О моделях

Этот раздел для тех, кто только знакомится с понятием Оптимизационная модель.

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

Ниже приведен небольшой ликбез по этой теме.

Надстройка Поиск решения помогает определить лучший способ сделать что-то :

"Что-то" может включать в себя выделение денег на инвестиции, загрузку склада, доставку товара или любую другую предметную деятельность, где требуется найти оптимальное решение.
"Лучший способ" или оптимальное решение в этом случае означает: максимизацию прибыли, минимизацию затрат, достижение наилучшего качества и пр.

Вот некоторые типичные примеры оптимизационных задач:

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

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

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

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

Подготовка оптимизационной модели в MS EXCEL

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

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

Приведем алгоритм работы с Поиском решения , который советуют сами разработчики (www.solver.com ):

Определите ячейки с переменными модели (decision variables);
Создайте формулу в ячейке, которая будет рассчитывать целевую функцию вашей модели (objective function);
Создайте формулы в ячейках, которые будут вычислять значения, сравниваемые с ограничениями (левая сторона выражения);
С помощью диалогового окна Поиск решения введите ссылки на ячейки содержащие переменные, на целевую функцию, на формулы для ограничений и сами значения ограничений;
Запустите Поиск решения для нахождения оптимального решения.

Проделаем все эти шаги на простом примере.

Простой пример использования Поиска решения

Необходимо загрузить контейнер товарами, чтобы вес контейнера был максимальным. Контейнер имеет объем 32 куб.м. Товары содержатся в коробках и ящиках. Каждая коробка с товаром весит 20кг, ее объем составляет 0,15м3. Ящик - 80кг и 0,5м3 соответственно. Необходимо, чтобы общее количество тары было не меньше 110 штук.

Данные модели организуем следующим образом (см. файл примера ).

Переменные модели (количество каждого вида тары) выделены зеленым.
Целевая функция (общий вес всех коробок и ящиков) – красным.
Ограничения модели: по минимальному количеству тары (>=110) и по общему объему (<=32) – синим.
Целевая функция рассчитывается по формуле =СУММПРОИЗВ(B8:C8;B6:C6) – это общий вес всех коробок и ящиков, загруженных в контейнер.
Аналогично рассчитываем общий объем - =СУММПРОИЗВ(B7:C7;B8:C8) . Эта формула нужна, чтобы задать ограничение на общий объем коробок и ящиков (<=32).
Также для задания ограничения модели рассчитаем общее количество тары =СУММ(B8:C8) .
Теперь с помощью диалогового окна Поиск решения введем ссылки на ячейки содержащие переменные, целевую функцию, формулы для ограничений и сами значения ограничений (или ссылки на соответствующие ячейки).
Понятно, что количество коробок и ящиков должно быть целым числом – это еще одно ограничение модели.

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

Резюме

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

Поиску решения не удалось найти решения (Solver could not find a feasible solution)

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

Примечание . О влиянии нелинейности модели на результаты расчетов можно прочитать в последнем разделе статьи .

В любом случае (линейном или нелинейном), Вы должны сначала проанализировать модель на непротиворечивость ограничений, то есть условий, которые не могут быть удовлетворены одновременно. Чаще всего это связано с неправильным выбором соотношения (например, <= вместо >=) или граничного значения.
Если, например, в рассмотренном выше примере, значение максимального объема установить 16 м3 вместо 32 м3, то это ограничение станет противоречить ограничению по минимальному количеству мест (110), т.к. минимальному количеству мест соответствует объем равный 16,5 м3 (110*0,15, где 0,15 – объем коробки, т.е. самой маленькой тары). Установив в качестве ограничения максимального объема 16 м3, Поиск решения не найдет решения.

При ограничении 17 м3 Поиск решения найдет решение.

Некоторые настройки Поиска решения

Метод решения
Рассмотренная выше модель является линейной, т.е. целевая функция (M – общий вес, который может быть максимален) выражена следующим уравнением M=a1*x1+a2*x2, где x1 и x2 – это переменные модели (количество коробок и ящиков), а1 и а2 – их веса. В линейной модели ограничения также должны быть линейными функциями от переменных. В нашем случае ограничение по объему V=b1*x1+b2*x2 также выражается линейной зависимостью. Очевидно, что другое ограничение - Максимальное количество тары (n) – также линейно x1+x2 Линейные задачи обычно решаются с помощью Симплекс метода. Выбрав этот метод решения в окне Поиска решения можно также проверить на линейность саму модель. В случае нелинейной модели Вы получите следующее сообщение:

В этом случае необходимо выбрать метод для решения нелинейной задачи. Примеры нелинейных зависимостей: V=b1*x1*x1; V=b1*x1^0,9; V=b1*x1*x2, где x – переменная, а V – целевая функция.

Кнопки Добавить, Изменить, Удалить
Эти кнопки позволяют добавлять, изменять и удалять ограничения модели.

Кнопка Сбросить
Чтобы удалить все настройки Поиска решения нажмите кнопку Сбросить – диалоговое окно очистится.

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

Точность
При создании модели исследователь изначально имеет некую оценку диапазонов варьирования целевой функции и переменных. Принимая во внимание вычислений в MS EXCEL, рекомендуется, чтобы эти диапазоны варьирования были значительно выше точности вычисления (она обычно устанавливается от 0,001 до 0,000001). Как правило, данные в модели нормируют так, чтобы диапазоны варьирования целевой функции и переменных были в пределах 0,1 – 100 000. Конечно, все зависит от конкретной модели, но если ваши переменные изменяются более чем на 5-6 порядков, то возможно следует «загрубить» модель, например, с помощью операции логарифмирования.

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

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

Скачать заметку в формате или , примеры в формате

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

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

Условия и ограничения. Себестоимость одной бочки масла – $100, а одного автомата – $150. Месячный бюджет на производство - $1800. Вы храните продукцию в 21-кубометровом подвале. Автомат занимает ½ м 3 , бочка масла 1½ м 3 . Сколько автоматов и бочек масла вам нужно продать за месяц, чтобы получить максимальную прибыль?

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

Представим области допустимых значений графически. Во-первых, количество пушек и бочек масла должно быть неотрицательным. Во-вторых, максимально можно произвести $1800/$150 = 12 автоматов или $1800/$100 = 18 бочек масла (рис. 1). Общее название этого треугольника – политоп – фигура с плоскими сторонами (например, бриллиант). В-третьих, подвал может вместить не более 21/(½) = 42 автоматов или 21/(1½) = 14 бочек масла (рис. 2).

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

(195 – 150) * N автоматов + (150 – 100) * N бочек масла = С,

где С – константа.

Например, при С = 450, линия будет проходить через координаты (0;10) и (9;0). Графически идея максимизации прибыли реализуется перемещением линии уровня параллельно самой себе в направлении увеличения значений по осям Х и Y (рис. 3). Любопытно, что для политопа оптимум всегда лежит в одной из вершин (или единственного решения не существует вовсе). На этом свойстве основан алгоритм симплексного метода. Решение задачи в Excel начинают с создания области модели (рис. 4). Формула целевой функции в ячейке В1 =СУММПРОИЗВ(C4:D4;C10:D10).

Рис. 3. Линия уровня и функция для оптимизации прибыли: а) некое произвольное начальное положение; б) линия уровня в оптимальном положении

У вас всё готово, чтобы нажать кнопку ДАННЫЕ –> Поиск решения . (Если вы не видите этой кнопки, установите надстройку Поиск решения; см. , глава 1). В открывшемся окне Параметры поиска решения задайте выделенные опции и нажмите Найти решение .

Рис. 5. Окно Поиск решения

Excel обновит лист и внесет на него результаты расчета (рис. 6).

Что произойдет, если добавить нелинейность? Допустим ваш посредник предлагает $500, если число автоматов в месяц будет более 5. Просто добавьте функцию ЕСЛИ в ячейку с прибылью (В1). Теперь целевая функция выглядит так: =СУММПРОИЗВ(C4:D4;C10:D10)+ЕСЛИ(C4>5;500;0). Жмем Поиск решения . Неудача, Excel сообщает об ошибке – условия линейности не выполнены (рис. 7).

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

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

К сожалению, с эволюционным алгоритмом все же возникают некоторые проблемы:

Время работы существенно больше, чем при симплекс-методе
Нет никакой гарантии, что он найдет оптимальное решение. Все, что в его силах - это контроль лучшего решения в популяции, пока не закончится время, либо популяция не изменится в достаточной степени для продолжения, либо вы принудительно не остановите «Поиск решения» нажатием кнопки ESC.
Эволюционный поиск решения работает довольно медленно. А если области допустимых значений сложные, он часто ругается, не найдя даже места, с которого начать.
Если вы хотите заставить эволюционный алгоритм хорошо работать в Excel, вам придется определить жесткие границы для каждой переменной решения. Даже если ваше решение более или менее неограниченное, вам все же нужны ограничения.

Принимая во внимание последний пункт, для решения задачи с автоматами и маслом вам нужно добавить ограничение, согласно которому оба решения не должны быть больше 25 (рис. 8). Установив основные параметры модели, кликните на кнопку Параметры . Проработав около минуты, эволюционный алгоритм выдал ожидаемое решение – 6 автоматов и 9 бочек масла. Поскольку без бонуса оптимально сделать лишь три автомата, а бонус выплачивается при производстве более 5 автоматов, очевидно, что оптимальным будет выбор 6 автоматов.

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

отношение по шкале Брикс/кислотность должно оставаться в пределах 11,5–12,5;
уровень кислотности должен оставаться между 0,75–1%;
уровень вяжущего вкуса должен быть 4 или ниже;
цвет должен находиться в рамках 4,5–5,5.

Шеф сообщил вам, что на январь и февраль он ожидает спросу на уровне 600 000 галлонов сока в месяц, а в марте – 700 000 галлонов. И еще, имеется договор со штатом Флорида, предоставляющий налоговые льготы при условии, что компания покупает не менее 40% сока каждый месяц у фермеров, выращивающих сорт Valencia . Договор следует соблюсти.

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

Создайте оптимизационную модель (рис. 10). Формулы можно изучить на соответствующем листе, приложенного Excel-файла. Кликните Поиск решения , и введите параметры (рис. 11). Нажмите Найти решение .

Рис. 11. Заполненное окно Поиск решения для задачи смешивания

Запустив Поиск решения , вы находите оптимальную стоимость закупок - $1,23 млн. (рис. 12). Обратите внимание, что заказ флоридской Valencia проходит по нижней границе условия. Очевидно, эта сделка - не лучший вариант, но приходится смириться. Второй по популярности сорт - это Verna из Мексики, которая чертовски дешева, но ровно настолько же ужасна.

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

Обратите внимание, что в ячейках В26:29 и F26:F29 теперь не константы, а формулы. Ваша новая цель – минимизация процента снижения качества в ячейках G26:G29. Точнее, вы бы хотели минимизировать максимальное из значений в ячейках G26:G29. Однако, если в ячейку D2 поместить формулу =МАКС(G26:G29), модель не будет работать. Напоминаю, функция МАКС не является линейной. Здесь доступна маленькая хитрость – можно внести дополнительное условие в модель: $G$26:$G$29<=$D$2 (рис. 14), а ячейку D2 оставить пустой. Т.е., ячейка D2 будет оптимизироваться не благодаря наличию в ней формулы, а последовательными циклами, запускаемыми этим дополнительным условием.

Нажмите Найти решение . Симплексный алгоритм будет пытаться приблизить D2 к 0 как целевую функцию модели, в то время как ограничения по вкусу и цвету будут пытаться увеличить ее насколько возможно, чтобы получить пригодную для работы смесь. Где же остановится значение D2? Самое меньшее из возможных значений - максимальный процент из четырех сниженных в диапазоне G26:G29. Мы видим (рис. 15, ячейки С26:Е29), что снижение расходов на 5% потребовало выйти за ограничения качества по всем четырем параметрам.

Вы представили данные шефу, который увидел, что сокращение расходов на 5% не стоит снижения качества сока, поэтому он согласовал ваш первый вариант. Но, когда вы принесли его в отдел снабжения, сотрудники возмутились. Как можно было так раздробить поставки!? Снабженцы настаивают, чтобы вы укрупнили партии: не более 4 поставщиков ежемесячно! И вы садитесь за новую модель. К сожалению, использовать функции ЕСЛИ или СЧЁТ вы не можете, так как хотите остаться в рамках линейной модели. Поэтому вам снова приходится прибегнуть к ухищрениям (рис. 16). Вы добавляете в модель область С33:Е43, которую определяете, как бинарную (значения в ней могут быть только 0 или 1), и оставляете ее пустой. А также область F33:H43, где каждая ячейка равна произведению значения из областей С33:Е43 на G5:G15. В параметры Поиск решения (рис. 17) вы добавляете еще одно условие $С$15:$Е$15 <= $F$33:$H$43 и еще одну область переменных – $C$33:$E$43.

Как в этом случае будет работать оптимизационный алгоритм? Когда он стартует все значения в областях С5:Е15, С33:Е43 и F33:H43 равны нулю. Допустим, что алгоритм пытается в ячейку С7 поместить значение 240. Сработает условие С7 <= F35, которое приведет к увеличению значения в F35, которое, в свою очередь, определяется формулой F35 = C35*$G7. Поскольку G7 – константа, а С35 – бинарная переменная, последней присваивается значение 1. Условие С7 <= F35 выполнено, т.к., 240 <= 1200. Таким образом вы моделируете неудобное условие «если… то»: «если заказ сделан, то бинарная переменная включается».

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

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

Инженеры сообщили, что на производстве появились новые «снижатели кислотности». Данная технология способна нейтрализовать 20% кислоты в соке, протекающем через прибор. Это не только снижает процент кислоты, но и повышает индекс Брикс/кислотность на 25%. Но для «снижателя» нужна энергия и расходные материалы стоимостью $20 за 1000 галлонов сока. Не весь сок, поступающий от поставщиков, нужно прогонять через этот процесс, однако, если поставка по какому-нибудь заказу прогоняется через ионообменник, то должен быть обработан весь ее объем. Постройте модель с участием ионообменника для снижения стоимости.

Проблема с новым правилом заключается в том, что естественный способ его моделирования - нелинейный, что приведет к использованию медленного алгоритма оптимизации. Но, как и в предыдущем примере, можно ввести бинарную переменную в области С25:Е35, которая бы «включалась» при необходимости понизить кислотность партии (рис. 18). Поскольку, нельзя использовать произведение «индикатор понижения кислотности (бинарный) * объем партии», вы создаете область С37:Е47, которая вам пригодятся для уравнивания объемов, подлежащих снижению кислотности, без прямого участия в формулах самих этих объемов. Итак, области С25:Е35 и С37:Е47 не содержат формул. В области G25:I35 используются формулы =С25:Е35*G5:G15 (это ограничение партии общим доступным объемом сока), а в области К25:М35 =Е5:E15-GG5:15*(1-Е25:E35). Это условие заработает только если партия подлежит снижению кислотности.

Также в модели со «снижателем кислотности» были изменены формулы в ячейках С16:Е16 (теперь они учитывают затраты на снижение кислотности по формуле «индикатор (бинарный) * объем партии * $20) и в ячейках С50:Е51 (теперь они учитывают повышение коэффициента Брикс/кислотность на 25% и снижение кислотности на 20% для обработанных партий). В параметрах Поиска решения появились новые переменные и дополнительные условие (рис. 19). К сожалению, нажав кнопку Найти решение , вы узнаете, что надстройка Поиск решения не может справиться с задачей (рис. 20). Модель стали слишком сложной.

Рис. 19. Параметры Поиска решения в модели со «снижателем кислотности»

Рис. 20. Поиск решения не справляется с задачей

Вам нужно загрузить и установить OpenSolver (как это сделать см. , глава 1). OpenSolver «подхватит» установки, введенные только что в окне Поиск решения . Поэтому просто нажмите кнопку Solver . Полученное решение – $1 235 927 более чем на $ 100 000 лучше предыдущего минимума – $1 338 913.

До сих пор мы считали, что поставляемая продукция имеет точно указанные параметры. Резонно предположить, что эти параметры подвержены вариации, характеризуемой среднеквадратичным отклонением (рис. 21; подробнее см. ). Самое известное и широко используемое распределение случайной величины - это нормальное распределение, иначе называемое «колоколообразной кривой». Скажем, в случае с соком из Египта среднее значение отношения Брикс/кислотность будет 13, а среднеквадратичное отклонение (также называемой стандартным отклонением) - 0,9 (рис. 21). В данном примере 13 - это центр распределения вероятности, 68% заказов будут в пределах ±0,9 от 13, а 95% будут в пределах ±1,8 от 13.

Ваша цель - предложить план смешивания стоимостью меньше $1,25 миллиона, который наилучшим образом соответствует ожиданиям по качеству в свете вариабельности поставок.

Мы используем среднее и среднеквадратичное отклонение характеристик, чтобы применить имитационное моделирование по методу Монте-Карло (если вы слышите это название впервые, рекомендую ). В этом методе вместо включения параметров распределения (среднего значения и среднеквадратичного отклонения) в модель напрямую, создается большое число сценариев, основанных на этих самых параметрах распределения.

Сценарий - это один из возможных ответов на вопрос: «Если это - распределения, основанные на статистике, на что же будет похож конкретный заказ?» Каждый сценарий включает сорок параметров десяти сортов сока (рис. 22). Чтобы получить один такой параметр, воспользуйтесь функцией НОРМ.ОБР (подробнее о функции см. ). Например, в ячейке В33 отношение Брикс/кислотность для сорта Hamlin определяется формулой =НОРМ.ОБР(СЛЧИС();H5;N5). Введите аналогичные формулы в область В33:СW76, сгенерировав 100 сценариев. Поиск решения не сможет работать с этими формулами, так как они нелинейны, поэтому скопируйте их в буфер и вставьте, но уже, как значения.

Цель минимизировать значение в ячейке D2. Т.е., найти решение, которое менее всего снижает границы качества для 100 сценариев. Как и в примерах на рис. 13–15, в ячейке D2 нет формулы. Оптимизация выполняется заданием параметров в окне Поиск решения. Все, что нужно - это поместить во все сценарии границы качества, а не просто ожидаемые значения характеристик. Таким образом, в отношение Брикс/кислотность вы добавляете условия B78:CW80 >= B26 и =< F26, затем проделываете то же самое с кислотностью, вяжущей составляющей вкуса и цветом (рис. 24). Нажмите Найти решение . Решение найдется довольно быстро. Если вы генерировали случайные значения сами, а не использовали те, что находятся в файле для загрузки, ваше решение может отличаться. Для моей сотни сценариев наилучшим показателем, который мне удалось получить, является изменение качества на 133%.

Рис. 24. Настройка Поиска решения для модели с вариабельностью характеристик

Если вы хотите расширить свои знания в области линейного программирования, рекомендую книгу The AIMMS optimization modeling book . Не пропустите две главы про трюки и подсказки – они поистине гениальны.

Написано по материалам книги Джона Формана . – М.: Альпина Паблишер, 2016. – С. 129–186. Насчет секретности разработки и Второй мировой – это, похоже, личное мнение автора книги. См. Википедию . – Прим. Багузина .

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

Пример 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 этап: проверка допустимости найденного базисного решения.

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

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

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

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

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

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

Решение:

I итерация:

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

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

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