Алгоритмы по математике

Формы модели ЗЛП и их эквивалентность

Стандартная форма ЗЛП имеет канонический вид, если в каждом уравнении системы ограничений существует переменная с коэффициентом +1, причем в других ограничениях и в целевой функции этой переменной нет, т. е. коэффициент равен 0. Каноническая форма называется допустимой, если все, иначе — недопустимой.

Алгоритм перехода к стандартной форме ЗЛП

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

, где

Сориентировать целевую функцию, учитывая соотношение

.

Используя уравновешивающие переменные, преобразовать имеющиеся неравенства в уравнения.

Алгоритм перехода к каноническому виду стандартной формы ЗЛП

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

, где

Сориентировать целевую функцию, учитывая соотношение

В системе ограничений каждое уравнение без переменной, создающей канонический вид, записать в виде двух неравенств ().

Используя уравновешивающие переменные, преобразовать неравенства в уравнения.

При необходимости уравнения можно умножить на (-1).

Графический метод решения ЗЛП

Алгоритм решения ЗЛП графическим методом

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

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

Построить линию уровня целевой функции .

3. Построить градиент

где .

Градиент перпендикулярен линии уровня.

4. Линию уровня перемещаем до крайней точки допустимой области по направлению градиента (при задании целевой функции на максимум) или антиградиента (при).

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

Вычислить значение F.

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

Симплексные преобразования при изменении базисных переменных

Условием для решения ЗЛП симплекс-методом является наличие модели задачи, записанной в каноническом виде стандартной формы.

Для удобства решения задачи составляют таблицу

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

Алгоритм основного симплекс-метода (все, но существуют)

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

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

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

Элемент, стоящий на пересечении разрешающих строки и столбца, называется разрешающим элементом (выделяется ?).

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

Заполняются базисные столбцы (на пересечении базисной переменной в строке и столбце стоит 1, а остальные элементы в столбце равны 0).

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

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

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

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

Если выполняется критерий оптимальности: коэффициенты, коэффициенты (при неискусственных переменных) целевой функции, то получен оптимальный план. Иначе — переход к пункту 2 данного алгоритма.

Алгоритм двойственного симплекс-метода (если все, но существуют)

1. Записать в нулевую таблицу исходную каноническую стандартную форму.

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

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

4. Далее решение аналогично основному симплекс-методу, начиная с пункта 4.

Алгоритм смешанного симплекс-метода (существуют и)

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

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

Решение ЗЛП методом искусственного базиса

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

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

Устойчивость решений ЗЛП при изменении параметров

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

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

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

Формулы расчета симплекс-таблицы с помощью обращенного базиса и симплекс-множителей

Решение двойственных задач линейного программирования

Общий вид прямой задачи:

Общий вид двойственной задачи

Правила построения двойственной задачи:

1. Число неизвестных двойственной задачи равно числу ограничений прямой задачи. Число ограничений двойственной задачи равно числу переменных прямой задачи.

2. Если целевая функция прямой задачи ориентирована на максимум, то целевая функция двойственной задачи ориентирована на минимум. В прямой задаче на максимум ограничения необходимо записать со знаками «» или ««.

3. Матрица коэффициентов двойственной задачи является транспонированной матрицей коэффициентов прямой задачи.

4. Коэффициенты целевой функции двойственной задачи являются свободными членами ограничений прямой задачи.

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

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

Решение парных матричных игр с нулевой суммой

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

Нижняя цена игры

— гарантированный минимальный выигрыш первого игрока («максиминная стратегия»).

Верхняя цена игры

— гарантированный максимальный проигрыш второго игрока «минимаксная стратегия».

Если, то имеем игру с седловой точкой. Иначе — цена игры C:

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

Алгоритм решения игры графическим методом

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

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

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

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

Алгоритм сведения матричной игры к ЗЛП

1. По теореме о цене игры

и

Зная, что, ,

предполагают

2. Получают прямую и двойственную задачу линейного программирования

;

3. Решив ЗЛП, определить цену игры можно по формуле

а вероятности .

Решение статистической игры

Игры, в которых один противник «природа», а другой — человек или один из игроков действует не сознательно, а в соответствии с определенными законами, называются играми с «природой» или статистическими играми.

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

Если известно распределение вероятностей состояний «природы»

то используют критерий Байеса

(максимум математического ожидания выигрыша) или

(минимум математического ожидания риска).

Если распределение вероятностей состояний «природы» неизвестно, то используют:

а) принцип «недостаточного основания Лапласа», где каждое состояние природы равновероятно, т. е. р₁=р₂=…= р_n=1/n;

б) максиминный критерий Вальда: ;

в) критерий минимального риска Сэвиджа: ;

г) критерий Гурвица:

где

при =0 — крайний оптимизм, при =1 — крайний пессимизм

Решение транспортной задачи методом потенциалов

Исходные данные

— вектор запасов поставщиков (столбец), — вектор потребностей потребителей (строка), — матрица тарифов (транспортные затраты при перевозке единицы груза из пункта в пункт).

Если

то имеем закрытую модель задачи. Если

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

Опорный план строится тремя методами: северо-западного угла, минимального элемента и аппроксимации Фогеля:

а) метод северо-западного угла: заполнение клеток таблицы начинается с левой верхней клетки («северо-западной»), в которую ставят максимально возможное число, т. е. минимальное из чисел запасов и потребностей для этой клетки. При этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая «северо-западная» клетка и т. д. Число заполненных клеток равно m+n-1. Если на каком-либо шаге вычеркиваются одновременно поставщик и потребитель, то в клетку, соответствующую данному методу, ставится 0-поставка;

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

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

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

1) вычисляют потенциалы поставщиков и потребителей из условия для всех занятых клеток (при условии);

2) определяют оценки всех свободных клеток.

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

1) цикл изображают в таблице в виде замкнутой ломаной линии. В любой занятой клетке цикла возможен поворот линии на 90⁰;

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

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

Решение транспортной задачи методом дифференциальных рент

Алгоритм решения транспортной задачи методом дифференциальных рент

1) В каждом столбце отметить клетку с минимальным тарифом.

2) В эти отмеченные клетки максимально распределить груз. Сначала в клетки, единственные отмеченные в строке и столбце, потом единственные в столбце или в строке с минимальными тарифами.

3) Необходимо получить оценки поставщиков:

а) если поставщик не все вывез, то его оценка «+n», где n — количество оставшегося груза у данного поставщика;

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

в) если все запасы поставщика исчерпаны и в отмеченных клетках столбцов потребитель удовлетворен с учетом всего столбца, то оценка «0». Знак нуля: если отмеченная клетка в строке связана в столбце с отмеченной клеткой только в отрицательной строке, то знак у нуля «-». В остальных случаях знак «+».

4) Для каждого столбца найти ренту: разницу между отмеченным тарифом в «отрицательной» строке и минимальным тарифом в «положительной» строке.

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

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

Замечания:

1) Сумма всех оценок в каждой таблице должна быть равна 0.

2) При подсчете общей стоимости перевозки использовать исходные тарифы, а не те, которые получились в последней таблице.

Решение транспортной задачи с дополнительными ограничениями

Если даны дополнительные ограничения в транспортной задаче

то в таблице данные изменятся

а) если, то

б) если, то

в) если, то столбец разбивается на два столбца:

и

В найденном решении поставки в этих столбцах суммируются.

Метод динамического программирования

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

I. Задача об оптимальном распределении ресурсов состоит в том, что предприятие имеет возможность выделить С ден.ед. n филиалам (в зависимости от вложенной суммы филиал дает прирост прибыли) с целью максимизации прибыли предприятия.

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

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

1. Составляется таблица, где вводят последовательность функций — максимальная прибыль фирмы, если х средств выделить одновременно

Очевидно, что

2. Выполняется «обратный ход»:

а) по определению

б) средства в объеме x распределяются между первым и вторым филиалами: второму в объеме x₂ ден.ед., тогда средств выделяется первому филиалу. Общая прибыль двух филиалов

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

г) аналогично находится

и т.д.

3. Выполняется «прямой ход»:

находится и оптимальное такое, что, после чего результаты вычислений просматриваются в обратном порядке. Зная, находят — объем финансирования остальных n-1 филиалов, а следовательно, и и, и т. д. до нахождения и .

II. Пусть известны: возраст оборудования на начало планового периода лет, остаточная стоимость оборудования s (t) ден.ед., цена нового оборудования p ден.ед., стоимость продукции, произведенной за 1 год на оборудовании возраста и издержки на обслуживание оборудования возраста. Для расчета оптимальной стратегии предприятия по замене оборудования вводят функцию — максимальная прибыль за последние i лет планового периода. Очевидно, что

Алгоритм решения задачи о замене оборудования

1. Определить из условия задачи

и справа таблицу дополнить столбцом .

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

числом, т.о.,

3. Начиная с индекса i = 2, расчет по строкам производится в соответствии с формулами

т.е. в следующей последовательности:

а) вычислить

где берется из уже заполненной строки;

б) вычислить

Получаемые значения вносить в соответствующие клетки строки, но начиная с первого, оставшиеся клетки заполнить значением m_i;

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

г) аналогично продолжить заполнение таблицы до последней строки, т. е. перейти к п. а) данного алгоритма.

4. Дойдя до последнего шага (i=n), попадаем в начало планового периода, начинают «прямой ход»: задавая t₀ и длительность планового периода, находим и строим последовательность оптимальных управлений, начиная с первого года и заканчивая последним.

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

III. Пусть спрос потребителей на продукцию составляет на 1-й, 2-й, 3-й этапы d₁, d₂, d₃ единиц соответственно. К началу первого этапа на складе имеется y₁ единицы продукции. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h₁, h₂, h₃. Затраты на производство х_j единиц на j-ом этапе определяются функцией,. Для нахождения оптимального количества производимой на каждом этапе продукции, чтобы заявки были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими, решение проводят по алгоритму.

Алгоритм решения задачи о производстве и хранении продукции

1. Составляется таблица значений функции затрат на производство

где

2. Выполняется «обратный ход»: составляются функциональные уравнения

минимальные затраты за первые k месяцев, ограничения по величине запаса к концу k-го месяца

балансовое уравнение

а из него получают ограничении

а) для k=1: составляются ограничения

а также таблица значений функции

б) для k=2: в зависимости от значений переменой

составляются ограничения

а также вспомогательные таблицы значений функции

Для каждого значения выбирается минимальное значение и соответствующее ему значение ;

в) для k=3: составляются ограничения

(причем),

а также таблица значений функции

3. Выполняется «прямой ход»:

а) для определяют, из балансового уравнения

выражают ;

б) зная, из таблицы значений определяют, а из балансового уравнения

выражают ;

) зная, из таблицы значений определяют ;

г) суммарные затраты за весь период .

Задачи планирования на сетях

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

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

Граф можно задать матрицей смежности вершин S, строки и столбцы которой соответствуют вершинам графа, причем элементы матрицы s_ij равны числу дуг/ребер, идущих из х_i в х_j.

Графический способ упорядочения вершин (алгоритм Фалкерсона)

1. Находятся вершины графа, в которые не входит ни одна дуга. Такие вершины образуют первую группу.

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

3. Устанавливается следующая группа вершин, в которые не входит ни одна дуга.

4. Если процесс упорядочения не окончен, то переход п. 2.

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

Алгоритм решения задачи о максимальном потоке

1. Построить начальный поток

2. На основе заданной сети построить новую сеть:

а) каждая дуга, для которой остаётся в новой сети с первоначальной r_ij;

б) каждая дуга, для которой, заменяется на две: одна — того же направления с пропускной способностью r_ij-; а вторая — противоположенного направления с пропускной способностью .

3. Если в новой сети можно найти ненулевой поток из I в S, то этот поток прибавляется к начальному. В результате получается новый поток и переходят к п. 2. Если ненулевой поток найти невозможно, то поток максимальной мощности построен.

Алгоритм расчета параметров сетевого графика

1) Изобразить события сетевого графика четырехсекторными кругами;

2) перемещаясь по сетевому графику от истока к стоку по возрастанию номеров событий, найти все ранние сроки наступления событий по формулам:

(исток) и, где

3) перемещаясь по сетевому графику от стока к истоку по мере убывания номеров событий, найти поздние сроки наступления событий

(сток) и ,

4) определить резерв времени каждого события ;

5) выделить критический путь — последовательность работ и событий, не имеющих резервов времени;

6) вычислить свободный резерв времени и полный резерв времени каждой работы .