Как решать симплекс метод в excel

Пример решения задачи симплексным методом в Excel

В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel, нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel» внизу окна:

Симплексный метод

Симплексный метод в Excel
Если данная команда отсутствует в списке, необходимо выполнить команду Сервис / Надстройки
Настройка Поиска решения в Excel
Функция Поиск решения в Excel

  • В диалоговом окне укажите:
    вид поиска (максимальное значение)
    в поле изменяя ячейки : $B$2:$D$2
    в поле Ограничения добавьте заданные ограничения
    Поле должно иметь следующее содержание:
    $B$2:$D$2>=0
    $G$6 Выполнить
  • Иногда задание звучит следующим образом: расчеты осуществить на ЭВМ, привести распечатку полученных результатов.

    MS Excel позволяет представить результаты поиска решения в форме отчета. Существует три типа таких отчетов:

    1. Результаты (Answer). В отчет включаются исходные и конечные значения целевой и влияющих ячеек, дополнительные сведения об ограничениях.
    2. Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.
    3. Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.

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

    ПРОИЗВОДИТЕЛЬНОСТЬ БАБУШЕК м 2 . /мин
    Баба Аня Белла Петровна Баба Варя Баба Галя Домна Ивановна Евгения Карловна Площадь работ
    Мытье окон 2 0 0 1 0 0 46
    Мытье полов 0 1 0 0 0 0 300
    Протирка столов 0 0 2 0 0.2 1 50
    Чистка дорожек 0 0 0 2 0 4 100

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

    Как решать симплекс метод в excel

    БлогNot. Преобразование Жордана-Гаусса и симплекс-метод в Excel

    Преобразование Жордана-Гаусса и симплекс-метод в Excel

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    заполним коэффициентами системы ячейки листа от A1 до D4 включительно, выберем разрешающий элемент a1,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$1 показывает разрешающий элемент, а ссылка на текущий элемент не закреплена. Остаётся только растянуть формулу на ячейки A6:D9 :

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

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

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

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

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

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

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

    переменные x2 и x4 — базисные, а x1 и x3 — свободные. Базисные переменные между собой независимы, а свободные можно сделать, например, нулями и получить < x2=2, x4=1 > – базисное решение системы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    23.03.2014, 08:18; рейтинг: 31895

    Ссылка на основную публикацию