Примеры решения задач по математическому программированию

Оглавление:

Примеры решения задач по математическому программированию

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

Если что-то непонятно вы всегда можете написать мне в воцап и я вам помогу!

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

Математическое программирование — раздел математики, посвященный теории и методам решения задач поиска экстремумов функций на множестве ограничений. Оно объединяет различные математические методы и дисциплины исследования операций: линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование, геометрическое программирование, целочисленное программирование и др.

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

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

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

Примеры решения задач по математическому программированию

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

Примеры задач:

Задача 1.1.

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

Примеры решения задач по математическому программированию

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

Решение:

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

Примеры решения задач по математическому программированию

станко-часов фрезерного оборудования.

Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство

Примеры решения задач по математическому программированию

Аналогичные рассуждения относительно возможного использования токарного, сварочного и шлифовального оборудования приведут к следующим неравенствам:

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Таким образом, приходим к следующей математической задаче: дана система

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

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

Так как функция (3) линейная, а система (2) содержит только линейные неравенства, то задача (1)—(3) является задачей линейного программирования.

Задача 1.2.

Продукцией городского молочного завода являются молоко, кефир и сметана, расфасованные в бутылки. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 ма-шино-ч. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 ч. Всего для производства цельномолочной продукции завод может использовать 136 000 кг молока. Основное оборудование может быть занято в течение 21,4 машино-ч, а автоматы по расфасовке сметаны — в течение 16,25 ч. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции не имеется никаких ограничений.

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

Решение:

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

Примеры решения задач по математическому программированию

тонн молока.

Так как завод может использовать ежедневно не более 136 000 т молока, то должно выполняться неравенство

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Задача 1.3.

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

Решение:

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Общая величина отходов по всем вариантам раскроя ткани составит

Примеры решения задач по математическому программированию

Таким образом, приходим к следующей математической задние: найти минимум функции

Примеры решения задач по математическому программированию

при условии, что ее переменнее удовлетворяют системе уравнений

Примеры решения задач по математическому программированию

и условию неотрицательности

Примеры решения задач по математическому программированию

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

Возможно эта страница вам будет полезна:

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

Общая и основная задачи математического программирования

К оглавлению…

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

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

Определение 1.2. Функция (8) называется целевой функцией (или линейной формой) задачи (8) — (11), а условия (9) — (II) — ограничениями данной задачи,

Определение 1.3. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (9) и (II), где Примеры решения задач по математическому программированию

Определение 1.4. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (10) и (11), где Примеры решения задач по математическому программированию

Определение 1.5. Совокупность чисел Примеры решения задач по математическому программированию удовлетворяющих ограничениям задачи (9) — (11), называется допустимым решением (или планом).

Определение 1.6. План Примеры решения задач по математическому программированию, при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции (8) при плане Примеры решения задач по математическому программированию будем обозначать через Примеры решения задач по математическому программированию. Следовательно, Примеры решения задач по математическому программированию— оптимальный план задачи, если для любого Примеры решения задач по математическому программированию выполняется неравенство Примеры решения задач по математическому программированию [соответственно Примеры решения задач по математическому программированию ].

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

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

В том случае, когда требуется найти минимум функции

Примеры решения задач по математическому программированию

можно перейти к нахождению максимума функции

Примеры решения задач по математическому программированию

поскольку

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

преобразуется в ограничение-равенство

Примеры решения задач по математическому программированию

а ограничение-неравенство

Примеры решения задач по математическому программированию

в ограничение-равенство

Примеры решения задач по математическому программированию

В то же время каждое уравнение системы ограничений

Примеры решения задач по математическому программированию

можно записать в виде неравенств:

Примеры решения задач по математическому программированию

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

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

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

Примеры задач с решением:

Свойства основной задачи математического программирования. Геометрическое истолкование задачи математического программирования

К оглавлению…

Рассмотрим основную задачу линейного программирования. Как было отмечено в § 1.2, она состоит в определении максимального значения функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

Перепишем эту задачу в векторной форме: найти максимум функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

где Примеры решения задач по математическому программированию — скалярное произведение; Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных член ах системы уравнений задачи:

Примеры решения задач по математическому программированию

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

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

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

Свойства основной задачи линейного программирования (15)—(17) тесным образом связаны со свойствами выпуклых множеств.

Определение 1.9. Пусть

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

где Примеры решения задач по математическому программированию — произвольные неотрицательные числа, сумма которых равна 1:

Примеры решения задач по математическому программированию

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

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

Теорема 1.1. Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто).

Определение 1.12. Непустое множество планов основной задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений — вершиной.

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

Теорема 1.3. Если система векторов

Примеры решения задач по математическому программированию

разложении (16) линейно независима и такова, что

Примеры решения задач по математическому программированию

где все Примеры решения задач по математическому программированию то точка

Примеры решения задач по математическому программированию

является вершиной многогранника решений.

Теорема 1.4. Если

Примеры решения задач по математическому программированию

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

Сформулированные теоремы позволяют сделать следующие выводы.

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

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

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

Каждое из неравенств (20), (21) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми

Примеры решения задач по математическому программированию

В том случае, если система неравенств (20), (21) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей — выпуклое, то областью допустимых решений задачи (19) — (21) является выпуклое множество, которое называется многоугольником решений (введенный ранее термин «многогранник решений» обычно употребляется, если Примеры решения задач по математическому программированию). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

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

Заканчивая рассмотрение геометрической интерпретации

Примеры решения задач по математическому программированию

задачи (9)—(21), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 1.1 —1.4. Рис. 1.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке Примеры решения задач по математическому программированию. Из рис. 1.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка Примеры решения задач по математическому программированию. На рис. 1.3 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рис. 1.4 — случай, когда система ограничений задачи несовместна.

Отметим, что нахождение минимального значения линейной функции при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь

Примеры решения задач по математическому программированию

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

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

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

Примеры задач с решением:

Нахождение решения задачи математического программирования

К оглавлению…

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

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

К оглавлению…

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

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

Здесь

Примеры решения задач по математическому программированию

заданные постоянные числа

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

где

Примеры решения задач по математическому программированию

Так как

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Положим

Примеры решения задач по математическому программированию

Так как векторы Примеры решения задач по математическому программированию — единичные, то

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

Теорема 1.5 (признак оптимальности опорного плана). Опорный план Примеры решения задач по математическому программированию задачи (22)— (24) является оптимальным, если Примеры решения задач по математическому программированию для любого Примеры решения задач по математическому программированию.

Теорема 1.6. Если Примеры решения задач по математическому программированию для некоторого Примеры решения задач по математическому программированию и среды чисел Примеры решения задач по математическому программированию нет положительных Примеры решения задач по математическому программированию то целевая функция (22) задачи (22)—(24) не ограничена на множестве ее планов.

Теорема 1.7. Если опорный план Примеры решения задач по математическому программированию задачи (22) — (24) не вырожден и Примеры решения задач по математическому программированию, но среди чисел Примеры решения задач по математическому программированию есть положительные (не все Примеры решения задач по математическому программированию), то существует опорный план Примеры решения задач по математическому программированию такой, что Примеры решения задач по математическому программированиюПримеры решения задач по математическому программированию.

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

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

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

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

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

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

Примеры решения задач по математическому программированию

Значение Примеры решения задач по математическому программированию равно скалярному произведению вектора Примеры решения задач по математическому программированию на вектор Примеры решения задач по математическому программированию:

Примеры решения задач по математическому программированию

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

1) Примеры решения задач по математическому программированию для Примеры решения задач по математическому программированию. Поэтому в данном случае числа 0 для всех Примеры решения задач по математическому программированию от I до Примеры решения задач по математическому программированию;

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

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

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

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

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

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

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

либо на основании их определения.

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

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

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

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

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

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

1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;

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

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

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

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

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

Итак, нахождение оптимального плана симплексным методом включает следующие этапы:

  1. Находят опорный план.
  2. Составляют симплекс-таблицу.
  3. Выясняют, имеется ли хотя бы одно отрицательное число Примеры решения задач по математическому программированию. Если нет, то найденный опорный план оптимален. Если же среди чисел Примеры решения задач по математическому программированию имеются отрицательные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.
  4. Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом Примеры решения задач по математическому программированию, а направляющая строка — минимальным из отношений компонент столбца вектора Примеры решения задач по математическому программированию к положительным компонентам направляющего столбца.
  5. По формулам (25) — (28) определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов Примеры решения задач по математическому программированию но векторам нового базиса и числа Примеры решения задач по математическому программированию. Все эти числа записываются в новой симплекс-таблице.
  6. Проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установления неразрешимости процесс решения задачи заканчивают.

Примеры задач с решением:

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

К оглавлению…

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

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

где

Примеры решения задач по математическому программированию

и среди векторов

Примеры решения задач по математическому программированию

нет Примеры решения задач по математическому программированию единичных.

Определение 1.13. Задача, состоящая в определении максимального значения функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

где Примеры решения задач по математическому программированию — некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей по отношению к задаче (32) — (34).

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

Примеры решения задач по математическому программированию

определяется системой единичных векторов

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Теорема 1.8. Если о оптимальном плане

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

расширенной задачи (35) — (37) значения искусственных переменных

Примеры решения задач по математическому программированию

то

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

является оптимальным планом задачи (32) — (34),

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

При опорном плане

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

а значения

Примеры решения задач по математическому программированию

равны

Примеры решения задач по математическому программированию

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

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

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

Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.

Итерационный процесс по Примеры решения задач по математическому программированию-й строке ведут до тех пор, пока:

1) либо все искусственные векторы не будут исключены из базиса;

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

Примеры решения задач по математическому программированию

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

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

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

Следовательно, процесс нахождения решения задачи (32) — (34) методом искусственного базиса включает следующие основные этапы:

  1. Составляют расширенную задачу (35) — (37).
  2. Находят опорпый план расширенной задачи.
  3. С помощью обычных вычислений симплекс метода исключают искусственные векторы из базиса. В результате либо находят опорный план исходной задачи (32) — (34), либо устанавливают ее неразрешимость.
  4. Используя найденный опорный план задачи (32) — (34), либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.

Примеры задач с решением:

Модифицированный симплекс-метод

К оглавлению…

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Определим компоненты вектора Примеры решения задач по математическому программированию и чисел Примеры решения задач по математическому программированию в случае решения основной задачи линейного программирования модифицированным симплекс-методом.

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

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

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

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Пусть

Примеры решения задач по математическому программированию

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

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

  1. Находят опорный план задачи.
  2. Вычисляют матрицу Примеры решения задач по математическому программированию обратную матрице Примеры решения задач по математическому программированию, составленной из компонентов векторов исходного базиса.
  3. Находят вектор Примеры решения задач по математическому программированию.
  4. Вычисляют числа Примеры решения задач по математическому программированию. Если все Примеры решения задач по математическому программированию не отрицательны, то исследуемый опорный план является оптимальным. Если же среди чисел Примеры решения задач по математическому программированию имеются отрицательные, то выбирают среди них наибольшее по абсолютной величине. Пусть это Примеры решения задач по математическому программированию.
  5. Вычисляют компоненты вектора Примеры решения задач по математическому программированию в исходном базисе. Если среди компонент вектора Примеры решения задач по математическому программированию нет положительных, то целевая функция задачи не ограничена на множестве планов. Если же среди компонент вектора Примеры решения задач по математическому программированию имеются положительные, то переходят к новому опорному плану.
  6. По известным правилам симплекс-метода находят разрешающую строку и вычисляют положительные компоненты нового опорного плана, а также матрицу Примеры решения задач по математическому программированию обратную матрице Примеры решения задач по математическому программированию, составленной из компонент векторов нового базиса.
  7. Проверяют новый опорный план на оптимальность и в случае необходимости проводят вычисление начиная с этапа 3.

Примеры задач с решением:

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

К оглавлению…

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

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

Пакет прикладных программ (ППП) представляет собой набор программ, позволяющий решать определенный класс задач и ориентированный на определенный тип машин. Рассмотрим более подробно наиболее часто используемые для нахождения решения задач линейного программирования пакеты прикладных программ: ППП «Линейное программирование-2» (ППП ЛП2) и ППП «Линейное программирование в АСУ» (ППП ЛП АСУ).

  • Использование П П П ЛП2 для нахождения решения задач линейного программирования. ППП ЛП2 предназначается для решения задач под управлением дисковой операционной системы ДОС ЕС; при этом используется алгоритм модифицированного симплекс-метода. Применение ППП ЛП2 позволяет находить решения задач линейного программирования с 200 ограничениями на машинах с оперативной памятью 32 К бант и с 1500 ограничениями на машинах с памятью 64 Кбайт. При этом в машину вводятся с перфокарт лишь отличные от нуля исходные данные задачи.

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

Наряду с возможностями нахождения решения различных задач использование Г1ПП ЛП2 позволяет проводить анализ полученного решения. Этот анализ может быть самым широким, что определяется пользователем. Например, можно определить, в каких интервалах могут изменяться коэффициенты целевой функции задачи, так чтобы данная задача имела один и тот же оптимальный план. Далее, можно выявить устойчивость оптимального плана задачи относительно изменения свободных членов системы ограничений, а также других параметров задачи.

Чтобы найти решение конкретной задачи линейного программирования с использованием ППП ЛП2, нужно определенным образом подготовить исходные данные задачи, ввести их в ЭВМ и осуществить управление процессом решения задачи, обеспечив выдачу необходимых результатов.

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

  1. Составляют математическую модель задачи.
  2. В соответствии с требованиями ППП ЛП2 элементам математической модели присваивают определенные имена.
  3. Переписывают математическую модель задачи с учетом введенных имен.
  4. Составляют матрицу исходных данных.
  5. Записывают исходные данные на специальном бланке.
  6. Определяют управляющую программу решения задачи.
  7. Находят решение задачи на ЭВМ.
  8. Проводят анализ полученного решения.

Примеры задач с решением:

Двойственные задачи математического программирования

К оглавлению…

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

Определение 1.14. Задача, состоящая в нахождении минимального значения функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

называется двойственной no отношению к задаче (50) — (52).

Задачи (50) — (52) и (53) — (55) образуют пару задач, называемую в линейном программировании двойственной парой.

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

  • Целевая функция исходной задачи (50)—(52) задается на максимум, а целевая функция двойственной (53) — (55) — на минимум.
  • Матрица
Примеры решения задач по математическому программированию

составленная из коэффициентов при неизвестных в системе ограничений (51) исходной задачи (50)—(52), и аналогичная матрица

Примеры решения задач по математическому программированию

в двойственной задаче (53) — (55) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов — строками).

  • Число переменных в двойственной задаче (53) — (55) равно числу соотношений в системе (51) исходной задачи (50) —(52), а число ограничений в системе (54) двойственной задачи — числу переменных в исходной задаче.
  • Коэффициентами при неизвестных в целевой функции (53) двойственной задачи (53) — (55) являются свободные члены в системе (51) исходной задачи (50)—(52), а правыми частями в соотношениях системы (54) двойственной задачи — коэффициенты при неизвестных в целевой функции (50) исходной задачи.
  • Если переменная Примеры решения задач по математическому программированию исходной задачи (50) — (52) может принимать только лишь положительные значения, то Примеры решения задач по математическому программированию-е условие в системе (54) двойственной задачи (53) — (55) является неравенством вида Примеры решения задач по математическому программированию. Если же переменная Примеры решения задач по математическому программированию может принимать как положительные, так и отрицательные значения, то Примеры решения задач по математическому программированию-е соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (51) исходной задачи (50) — (52) и переменными двойственной задачи (53) — (55). Если Примеры решения задач по математическому программированию-е соотношение в системе (51) исходной задачи является неравенством, то Примеры решения задач по математическому программированию-я переменная двойственной задачи Примеры решения задач по математическому программированию. В противном случае переменная Примеры решения задач по математическому программированию может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (51) прямой задачи и соотношения (54) двойственной задачи являются неравенствами вида Примеры решения задач по математическому программированию. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Примеры задач с решением:

Экономическая интерпретация двойственных задач

К оглавлению…

Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере.

Пример задачи с решением:

Анализ устойчивости двойственных оценок

К оглавлению…

Продолжим рассмотрение основной задачи линейного программирования (61)—(63) и двойственной к ней (64). (65).

Предположим, что задача (61) — (63) имеет невырожденные опорные планы и хотя бы один из них является оптимальным.

Максимальное значение целевой функции (61) задачи (61) — (63) будем рассматривать как функцию свободных членов системы линейных уравнений (62):

Примеры решения задач по математическому программированию

Теорема 1.12. В оптимальном плане двойственной задачи (64), (65) значение переменной Примеры решения задач по математическому программированию численно равно частной производной функции Примеры решения задач по математическому программированию по данному аргументу, т. е.

Примеры решения задач по математическому программированию

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

Это изменение Примеры решения задач по математическому программированию определяется величиной Примеры решения задач по математическому программированию и может быть охарактеризовано лишь тогда, когда при изменении величии Примеры решения задач по математическому программированию значения переменных Примеры решения задач по математическому программированию в оптимальном плане соответствующей двойственной задачи (64), (65) остаются неизменными. Поэтому представляет интерес определить такие интервалы изменения каждого из свободных членов системы линейных уравнений (62), в которых оптимальный план двойственной задачи (64), (65) не меняется. Это имеет место для всех тех значений Примеры решения задач по математическому программированию, при которых столбец вектора Примеры решения задач по математическому программированию последней симплекс-таблицы решения задачи (61)— (63) не содержит отрицательных чисел, т.е. тогда, когда среди компонент вектора

Примеры решения задач по математическому программированию

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

Таким образом, если найдено решение задачи (61) — (63), то нетрудно провести анализ устойчивости двойственных оценок относительно изменений Примеры решения задач по математическому программированию. Это, в свою очередь, позволяет проанализировать устойчивость оптимального плана задачи (64), (65) относительно изменений свободных членов системы линейных уравнений (62), оценить степень влияния изменения bi на максимальное значение целевой функции задачи (61) — (63) и дает возможность определить наиболее целесообразный вариант возможных изменений Примеры решения задач по математическому программированию.

Пример задачи с решением:

Двойственный симплекс-метод

К оглавлению…

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

где

Примеры решения задач по математическому программированию

и среди чисел

Примеры решения задач по математическому программированию

имеются отрицательные.

В данном случае

Примеры решения задач по математическому программированию

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

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

Таким образом, можно найти

Примеры решения задач по математическому программированию

Определение 1.15. Решение

Примеры решения задач по математическому программированию

системы линейных уравнений (81), определяемое базисом Примеры решения задач по математическому программированию. называется псевдопланом задачи (80) — (82), если Примеры решения задач по математическому программированию для любого Примеры решения задач по математическому программированию.

Теорема 1.13. Если в псевдоплане Примеры решения задач по математическому программированию, определяемом базисом Примеры решения задач по математическому программированию есть хотя бы одно отрицательное число Примеры решения задач по математическому программированию такое, что все Примеры решения задач по математическому программированию, то задача (80) — (82) вообще не имеет планов.

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

Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода.

Итак, продолжим рассмотрение задачи (80) —(82). Пусть Примеры решения задач по математическому программированию — псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу (табл. 1.47), в которой некоторые элементы столбца вектора Примеры решения задач по математическому программированию являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (80)—(82), поскольку, по предположению, все Примеры решения задач по математическому программированию. Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс-таблицы к другой до тех пор, пока из столбца вектора Примеры решения задач по математическому программированию не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы Примеры решения задач по математическому программированию-й строки, т.е. Примеры решения задач по математическому программированию для любого Примеры решения задач по математическому программированию.

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

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

Таким образом, отыскание решения задачи (80) — (£2) двойственным симплекс-методом включает следующие этапы:

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

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

  • Находят новый псевдоплан и повторяют все действия начиная с этапа 2.

Примеры задач с решением:

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

К оглавлению…

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

I. Использование ППП ЛП2 для послеоптимизационного анализа решения задачи. Послеоптимизационный анализ решения задачи в условиях использования ППП ЛП2 реализуется процедурой LPANAI.YSIS. Отчет о нослеоптимизационном анализе выдается в виде таблицы, состоящей из двух частсй. В одной из них приводятся данные анализа для переменных, принявших свои значения на границе области допустимых значений, а в другой — для переменных, принявших значения внутри области их допустимых значений.

В отчете о послеоптимизационном анализе содержится вся информация, имеющаяся в отчетах LPSOLIJTION (см. § 1.5), а также приводятся:

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

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

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

Получение отчета о послеоптимизационном анализе решения задачи с использованием Г1ПП ЛГ12 включает те же основные этапы, что и процесс нахождения решения задачи с использованием данного пакета.

Пример задачи с решением:

Использование П П П ЛП АСУ для послеоитимизационного анализа решения задачи

В условиях использования ППП ЛП АСУ наиболее подробный послеоптимизационный анализ обеспечивается процедурой RANGE. Отчет о послеоптимизацмонном анализе выдается в виде таблицы, включающей четыре секции. Первая секция — СТРОКИ НА ГРАНИЦЕ, вторая секция — СТОЛБЦЫ НА ГРАНИЦЕ, третья секция — СТРОКИ НА ПРОМЕЖУТОЧНОМ УРОВНЕ и четвертая секция — СТОЛБЦЫ НА ПРОМЕЖУТОЧНОМ УРОВНЕ. В секциях содержится вся информация, выдача которой обеспечивается процедурой SOLUTION (см. § 1.5). Кроме того, указываются:

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

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

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

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

Пример задачи с решением:

Специальные задачи математического программирования

К оглавлению…

Транспортная задача

К оглавлению…

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

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

Определение 2.2. План

Примеры решения задач по математическому программированию

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

Обычно исходные данные транспортной задачи записывают в виде табл. 2.1.

Примеры решения задач по математическому программированию

Очевидно, общее наличие груза у поставщиков равно

Примеры решения задач по математическому программированию

а общая потребность в грузе в пунктах назначения равна

Примеры решения задач по математическому программированию

единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

Примеры решения задач по математическому программированию

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

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

В случае превышения запаса над потребностью, т. е.

Примеры решения задач по математическому программированию

вводится фиктивный Примеры решения задач по математическому программированию-й пункт назначения с потребностъю

Примеры решения задач по математическому программированию

и соответствующие тарифы считаются равными нулю:

Примеры решения задач по математическому программированию

Полученная задача является транспортной задачей, для которой выполняется равенство (5).

Аналогично, при

Примеры решения задач по математическому программированию

вводится фиктивный Примеры решения задач по математическому программированию-й пункт отправления с запасом груза

Примеры решения задач по математическому программированию

и тарифы полагаются равными нулю:

Примеры решения задач по математическому программированию

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

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

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

Для определения опорного плана существует несколько методов. Три из них — метод северо-западного угла, метод минимального элемента и метод аппроксимации Фогели — рассматриваются ниже.

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

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждая неизвестная входит лишь в два уравнения систем (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них — метод потенциалов и метод дифференциальных рент — рассмотрены ниже.

Пример задачи с решением:

Определение опорного плана транспортной задачи

К оглавлению…

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

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

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

Метод северо-западного угла. При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного Примеры решения задач по математическому программированию («северо-западный угол») и заканчивается клеткой для неизвестного Примеры решения задач по математическому программированию, т. e. идет как бы по диагонали таблицы.

Пример задачи с решением:

Метод минимального элемента

К оглавлению…

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

Пример задачи с решением:

Метод аппроксимации Фогеля

К оглавлению…

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

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

Пример задачи с решением:

Определение оптимального плана транспортной задачи

К оглавлению…

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

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

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

Теорема ‘2.2. Если для некоторого опорного плана Примеры решения задач по математическому программированиюПримеры решения задач по математическому программированию транспортной задачи существуют такие числа

Примеры решения задач по математическому программированию

для всех

Примеры решения задач по математическому программированию

оптимальный план транспортной задачи.

Определение 2.3. Числа Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию называются потенциалами соответственно пунктов назначения и пунктов потребления.

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

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

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

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

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

Если ломаная линия, образующая никл, пересекается, то точки самопересечения не являются вершинами. Примеры некоторых циклов показаны на рис. 2.1.

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

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

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

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

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

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

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

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

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

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

Примеры задач с решением:

Метод дифференциальных рент

К оглавлению…

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

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

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

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

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

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

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

Пример задачи с решением:

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

К оглавлению…

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

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

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

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

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

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

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

Примеры решения задач по математическому программированию

Примеры задач с решением:

Нахождение решения некоторых экономических задач, сводящихся к транспортной

К оглавлению…

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

Примеры задач с решением:

Целочисленные задачи математического программирования

К оглавлению…

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

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

Примеры задач с решением:

Определение оптимального плана задачи целочисленного программирования

К оглавлению…

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

Если найти решение задачи (32) — (35) симплексным методом, то оно может оказаться как целочисленным, так и нет (примером задачи линейного программирования, решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения оптимального плана задачи (32) — (35) требуются специальные методы. В настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори, в основе которого лежит описанный выше симплексный метод.

Метод Гомори

К оглавлению…

Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (32) —

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

(35). Если же в оптимальном плане задачи (32) — (34) переменная Примеры решения задач по математическому программированию принимает дробное значение, то к системе уравнений (33) добавляют неравенство

Примеры решения задач по математическому программированию

и находят решение задачи (32) — (34), (36).

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

Если в найденном плане задачи (32)—(34), (36) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (32) — (35), либо устанавливают ее неразрешимость.

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

Примеры решения задач по математическому программированию

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

1) для Примеры решения задач по математическому программированию которые могут принимать нецелочисленные значения,

Примеры решения задач по математическому программированию

2) для Примеры решения задач по математическому программированию, которые могут принимать только целочисленные значения,

Примеры решения задач по математическому программированию

Из изложенного выше следует, что процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие основные этапы:

  1. Используя симплексный метод, находят решение задачи (32) —(34) без учета требования целочисленности переменных.
  2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (32) —(34) имеет максимальное дробное значение, а в оптимальном плане задачи (32) — (35) должна быть целочисленной.
  3. Используя двойственный симплекс-метод, находят решение задачи, получающейся из задачи (32) — (34) в результате присоединения дополнительного ограничения.
  4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (32) —(35) или установления ее неразрешимости.

Примеры задач с решением:

Использование ППП ЛП АСУ для решения задач целочисленного программирования

Как уже отмечалось выше, решение задачи целочисленного программирования может быть найдено с использованием ППП ЛП АСУ. При этом число переменных решаемой задачи при оперативной памяти, равной 1024 Кбайт, не должно превышать 4095, Для решения задач целочисленного программирования используется метод ветвей и границ.

Процесс нахождения решения задачи целочисленного программирования с использованием ППП ЛП АСУ включает те же основные этапы, что и при нахождении решения задачи линейного программирования с использованием данного пакета. Однако здесь имеется некоторая специфика в записи исходных данных и в управляющей программе. Основной особенностью записи целочисленных переменных является то, что в секции COLUMNS запись каждого набора целочисленных переменных начинается и заканчивается специальными маркерами, а в секции BOUNDS обязательным является задание верхних границ целочисленных переменных. Эти границы определяются исходя из условий каждой конкретной задачи.

В начале каждого набора целочисленных переменных в поле 2 записывается присвоенное имя начала набора переменных (оно может быть любым и должно отличаться от других используемых маркеров и имен), в поле 3 указывается ключевое слово »MARKER7, а в поле 5 записывается маркер начала набора переменных ‘INTORG’. Все остальные поля остаются пустыми.

После записи данного набора целочисленных переменных в поле 2 указывается имя конца набора переменных, в голе 3 записывается ключевое слово ‘MARKER’, а в поле 5 указывается маркер конца набора ‘INTEND^.

Пример задачи с решением:

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

К оглавлению…

Экономическая и геометрическая интерпретации задачи параметрического программирования. Во многих задачах математического программирования исходные данные зависят от некоторого параметра. Такие задачи называются задачами параметрического программирования.

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

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

Пример задачи с решением:

Нахождение решения задачи параметрического программирования

К оглавлению…

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

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

Примеры решения задач по математическому программированию

Для всех Примеры решения задач по математическому программированию задача (57) — (59) имеет один и тот же оптимальный план, что и при Примеры решения задач по математическому программированию.

В том случае, если задача (57) — (59) при Примеры решения задач по математическому программированию неразрешима, в Примеры решения задач по математическому программированию-й строке последней симплекс-таблицы ее решения имеется число Примеры решения задач по математическому программированию гдеПримеры решения задач по математическому программированию. Тогда:

1) если Примеры решения задач по математическому программированию, то задача (57) — (59) неразрешима для любого Примеры решения задач по математическому программированию;

2) если Примеры решения задач по математическому программированию, то задача (57)—(59) неразрешима для всех Примеры решения задач по математическому программированию;

3) если Примеры решения задач по математическому программированию, то задача (57) —(59) неразрешима для всех Примеры решения задач по математическому программированию.

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

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

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

Итак, процесс нахождения решения задачи (57)—(59) включает следующие этапы:

  1. Считая значение параметра Примеры решения задач по математическому программированию равным некоторому числу Примеры решения задач по математическому программированию, находят оптимальный план Примеры решения задач по математическому программированию или устанавливают неразрешимость полученной задачи линейного программирования.
  2. Определяют множество значений параметра Примеры решения задач по математическому программированию, для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключают из рассмотрения.
  3. Полагают значение параметра Примеры решения задач по математическому программированию равным некоторому числу, принадлежащему оставшейся части промежутка Примеры решения задач по математическому программированию, и симплексным методом находят решение полученной задачи линейного программирования.
  4. Определяют множество значений параметра Примеры решения задач по математическому программированию, для которых новый оптимальный план остается оптимальным или задача неразрешима. Вычисления повторяют до тех пор, пока не будут исследованы все значения параметра Примеры решения задач по математическому программированию.

Примеры задач с решением:

Задачи дробно-линейного программирования

К оглавлению…

Экономическая и геометрическая интерпретации задачи дробно-линейного программирования. Общая задача дробно-линейного программирования состоит в определении максимального значения функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

где

Примеры решения задач по математическому программированию

некоторые постоянные числа,

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

в области неотрицательных решений системы линейных уравнений (90). При этом будем предполагать, что

Примеры решения задач по математическому программированию

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

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

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

Будем считать, что

Примеры решения задач по математическому программированию

Чтобы найти решение задачи (92) — (94), как и в § 1.3 при рассмотрении задачи (19)— (21), сначала находим многоугольник решений, определяемый ограничениями (93) и (94). Предполагая, что этот многоугольник не пуст, полагаем значение функции равным некоторому числу h, так что прямая

Примеры решения задач по математическому программированию

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

Итак, процесс нахождения решения задачи (92) — (94) включает следующие этапы:

  1. В системе ограничений задачи заменяют знаки неравенств на знаки точных равенств и строят определяемые этими равенствами прямые.
  2. Находят полуплоскости, определяемые каждым из неравенств системы ограничений задачи.
  3. Находят многоугольник решений задачи.
  4. Строят прямую (95), уравнение которой получается, если положить значение целевой функции (92) равным некоторому постоянному числу.
  5. Определяют точку максимума или устанавливают неразрешимость задачи.
  6. Находят значение целевой функции в точке максимума.

Примеры задач с решением:

Задачи блочного программирования

К оглавлению…

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

Прежде чем записать главную задачу, введем обозначения:

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Пусть

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Далее,

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

Если

Примеры решения задач по математическому программированию

оптимальный план главной задачи,

Примеры решения задач по математическому программированию

соответствующие вершины многогранника

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

где

Примеры решения задач по математическому программированию

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

Примеры задач с решением:

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

К оглавлению…

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

Определение 2.5. Ситуация называется конфликтной, если в ней участвуют стороны, интересы которых полностью или частично противоположны.

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

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

Определение 2.8. Количественная оценка результатов игры называется платежом.

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

Определение 2.10. Парная игра называется игрой с нулевой суммой, если сумма платежей равна нулю, т. е. если проигрыш одного игрока равен выигрышу второго.

Парные игры с нулевой суммой и рассматриваются ниже.

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

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

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

Из чисел Примеры решения задач по математическому программированию составим матрицу

Примеры решения задач по математическому программированию

Строки матрицы А соответствуют стратегиям первого игрока, а столбцы —стратегиям второго. Эти стратегии называются чистыми.

Определение 2.13. Матрица А называется платежной (или матрицей игры).

Определение 2.14. Игру, определяемую матрицей А, имеющей Примеры решения задач по математическому программированию строк и Примеры решения задач по математическому программированию столбцов, называют конечной игрой размерности Примеры решения задач по математическому программированию.

Определение 2.15. Число

Примеры решения задач по математическому программированию

называется нижней ценой игры или максимином, а соответствующая ему стратегия (строка) —максиминной.

Определение 2.16. Число

Примеры решения задач по математическому программированию

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

Теорема 2.3. Нижняя цена игры всегда не превосходит верхней цены игры.

Определение 2.17. Если Примеры решения задач по математическому программированию то число Примеры решения задач по математическому программированию называется ценой игры.

Задача 2.99.

Найти решение игры, заданной матрицей и дать геометрическую интерпретацию этого решения.

Примеры решения задач по математическому программированию

Решение. Прежде всего проверим наличие седловой точки в данной матрице. Для этого найдем минимальные элементы в каждой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5). Значит, нижняя цена игры

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Так как

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Тогда:

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

Следовательно, решением игры являются смешанные стратегии

Примеры решения задач по математическому программированию

а цена игры

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

(рис. 2.15). В частности, точке Примеры решения задач по математическому программированию (0; 1) отвечает стратегия Примеры решения задач по математическому программированию, точке Примеры решения задач по математическому программированию (1; 0) — стратегия Примеры решения задач по математическому программированию и т. д.

Примеры решения задач по математическому программированию

В точках Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию восставим лерпеидикуляры и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью Примеры решения задач по математическому программированию) отложим выигрыш игрока Примеры решения задач по математическому программированию при стратегии Примеры решения задач по математическому программированию, а на втором — при стратегии Примеры решения задач по математическому программированию. Если игрок Примеры решения задач по математическому программированию применяет стратегию Примеры решения задач по математическому программированию то его выигрыш при стратегии Примеры решения задач по математическому программированию игрока Примеры решения задач по математическому программированию равен 2, а при стратегии Примеры решения задач по математическому программированию он равен 5. Числам 2 и 5 на оси Примеры решения задач по математическому программированию соответствуют точки Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию.

Если же игрок Примеры решения задач по математическому программированию применяет стратегию Примеры решения задач по математическому программированию то его выигрыш при стратегии Примеры решения задач по математическому программированию игрока Примеры решения задач по математическому программированию равен 6, а при стратегии Примеры решения задач по математическому программированию он равен 4. Эти два числа определяют две точки Примеры решения задач по математическому программированию на перпендикуляре, восставленном в точке Примеры решения задач по математическому программированию. Соединяя между собой точки Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию, получим две прямые, расстояние до которых от оси Примеры решения задач по математическому программированию определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка Примеры решения задач по математическому программированию до оси Примеры решения задач по математическому программированию определяет средний выигрыш Примеры решения задач по математическому программированию при любом сочетании стратегий Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию и стратегии игрока Примеры решения задач по математическому программированию.

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Решая последнюю систему уравнений, получаем

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

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

Для ее определения имеем уравнения

Примеры решения задач по математическому программированию

Следовательно, решением игры являются смешанные стратегии

Примеры решения задач по математическому программированию

а цена игры

Примеры решения задач по математическому программированию

К такому выводу мы пришли и выше.

Обобщая изложенные выше результаты нахождения решения игры 2X2, можно указать основные этапы нахождения решения игры 2Х« или «X2.

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

Примеры задач с решением:

Задачи нелинейного программирования. Экономическая и геометрическая интерпретации задачи нелинейного программирования

К оглавлению…

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

Примеры решения задач по математическому программированию

при условии, что ее переменные удовлетворяют соотношениям

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

удовлетворяющей условиям (2), выполняется неравенство

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

Если Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию — линейные функции, то задача (1), (2) является задачей линейного программирования.

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

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

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

Примеры решения задач по математическому программированию

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

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

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

Примеры задач с решением:

Метод множителей Лагранжа

К оглавлению…

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

Примеры решения задач по математическому программированию

функции, непрерывные вместе со своими частными производными

Примеры решения задач по математическому программированию

В курсе математического анализа задачу (16), (17) называют задачей на условный экстремум или классической задачей оптимизации.

Чтобы найти решение этой задачи, вводят набор переменных

Примеры решения задач по математическому программированию

называемых множителями Лагранжа, составляют функцию Лагранжа

Примеры решения задач по математическому программированию

находят частные производные

Примеры решения задач по математическому программированию

и рассматривают систему Примеры решения задач по математическому программированию уравнений

Примеры решения задач по математическому программированию

с Примеры решения задач по математическому программированию неизвестными

Примеры решения задач по математическому программированию

Всякое решение системы уравнений (19) определяет точку

Примеры решения задач по математическому программированию

в которой может иметь место экстремум функции

Примеры решения задач по математическому программированию

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

Таким образом, определение экстремальных точек задачи (16), (17) методом множителей Лагранжа включает следующие этапы:

  1. Составляют функцию Лагранжа.
  2. Находят частные производные от функции Лагранжа по переменным Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию и приравнивают их нулю.
  3. Решая систему уравнений (19), находят точки, в которых целевая функция задачи может иметь экстремум.
  4. Среди точек, подозрительных па экстремум, находят такие, в которых достигается экстремум, и вычисляют значения функции (16) в этих точках.

Примеры задач с решением:

Задачи выпуклого программирования

К оглавлению…

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

Примеры решения задач по математическому программированию

где Примеры решения задач по математическому программированию и Примеры решения задач по математическому программированию—некоторые функции Примеры решения задач по математическому программированию переменных Примеры решения задач по математическому программированию.

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

Определение 3.1. Функция

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Определение 3.2. Функция

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

Определение 3.3. Говорят, что множество допустимых решений задачи (24) — (26) удовлетворяет условию регулярности, если существует по крайней мере одна точка Примеры решения задач по математическому программированию, принадлежащая области допустимых решений такая, что

Примеры решения задач по математическому программированию

Определение 3.4. Задача (24) — (26) называется задачей выпуклого программирования, если функция

Примеры решения задач по математическому программированию

является вогнутой (выпуклой), а функции

Примеры решения задач по математическому программированию

выпуклыми.

Теорема 3.1. Любой локальный максимijm (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Оп ределение 3.5. Функцией Лагранжа задачи выпуклого программирования (24)—(26) называется функция

Примеры решения задач по математическому программированию

где

Примеры решения задач по математическому программированию

множители Лагранжа.

Определение 3.6. Точка

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

называется седловой точкой функции Лагранжа, если

Примеры решения задач по математическому программированию

для всех

Примеры решения задач по математическому программированию

Теорема 3,2 (теорема Куна—Таккера). Для задачи выпуклого программирования (24) — (26), множество допустимых решений которой обладает свойством регулярности, Примеры решения задач по математическому программированиюПримеры решения задач по математическому программированиюявляется оптимальным планом тогда и только тогда, когда существует такой вектор Примеры решения задач по математическому программированиюПримеры решения задач по математическому программированию, что Примеры решения задач по математическому программированию — седловая точка функции Лагранжа.

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

Примеры решения задач по математическому программированию

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

Определение 3.7. Квадратичной формой относительно переменных

Примеры решения задач по математическому программированию

называется числовая функция от этих переменных, имеющая вид

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

для любого набора значений переменных

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

и, кроме того, существует такой набор переменных

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Определение 3.10. Задача, состоящая в определении максимального (минимального) значения функции

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

где

Примеры решения задач по математическому программированию

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

Для сформулироааннои задачи квадратичного программирования функция Лагранжа запишется и виде

Примеры решения задач по математическому программированию

Если функция Примеры решения задач по математическому программированию имеет седловую точку

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

то в этой точке наполняются соотношения (30) — (35). Вводя теперь дополнительные церемонные

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

обращающие неравенства (30) и (33) в равенства, перепишем выражении (30) — (35), записанные для задачи квадратичного программирования, следующим образом:

Примеры решения задач по математическому программированию

Таким образом, чтобы найти решение задачи квадратичного программирования (36) — (38), нужно определить неотрицательное решение систем линейных уравнений (39) и (40), удовлетворяющее условиям (41) и (42). Это решение можно найти с помощью метода искусственного базиса, примененного для нахождения максимального значения функции Примеры решения задач по математическому программированию. При условиях (39), (40), (43) с учетом (41) и (42). Здесь Примеры решения задач по математическому программированию— искусственные переменные, введенные в уравнения (39) и (40).

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

Итак, процесс нахождения решения задачи квадратичного программирования (36) — (38) включает следующие этапы:

  1. Составляют функцию Лагранжа.
  2. Записывают в виде выражений (39) — (43) необходимые и достаточные условия существования седловой точки для функции Лагранжа.
  3. Используя метод искусственного базиса, либо устанавливают отсутствие седловой точки для функции Лагранжа, либо находят ее координаты.
  4. Записывают оптимальное решение исходной задачи и находят значение целевой функции.

Пример задачи с решением:

Градиентные методы

К оглавлению…

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

К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. Наиболее распространенным из таких методов является метод Франка—Вулфа.

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

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

Примеры решения задач по математическому программированию

в очередной точке Примеры решения задач по математическому программированию не станет равным нулю или же пока

Примеры решения задач по математическому программированию

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

Остановимся более подробно на методах Франка—Вулфа, штрафных функций и Эрроу Гурвица.

I. Метод Франка—Вулфа. Пусть требуется найти максимальное значение вогнутой функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

и строят линейную функцию

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

где Примеры решения задач по математическому программированию— некоторое число, называемое шагом вычислении и заключенное между нулем и единицей Примеры решения задач по математическому программированию. Это число Примеры решения задач по математическому программированию берут произвольно или определяют таким образом, чтобы значение функции в точке Примеры решения задач по математическому программированию. зависящее от Примеры решения задач по математическому программированию было максимальным. Для этого необходимо найти решение уравнения Примеры решения задач по математическому программированию и выбрать его наименьший корень. Если его значение больше единицы, то следует положить Примеры решения задач по математическому программированию = 1. После определения числа Примеры решения задач по математическому программированию находят координаты точки вычисляют значение целевой функции в ней и выясняют необходимость перехода к попой точке Примеры решения задач по математическому программированию. Если такая необходимость имеется, то вычисляют в точке градиент целевой функции, переходят к соответствующей задаче линейного программирования и находят се решение. Определяют координаты точки и исследуют необходимость проведения дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.

Итак, процесс нахождения решения задачи (57) — (50) методом Франка—Вулфа включает следующие этапы:

  1. Определяют исходное допустимое решение задачи.
  2. Находят градиент функции (57) в точке допустимого решения.
  3. Строят функцию (60) н находят ее максимальное значение при условиях (58) и (59).
  4. Определяют шаг вычислений.
  5. По формулам (61) находят компоненты нового допустимого решения.
  6. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.

Пример задачи с решением:

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

К оглавлению…

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

Определение 3.11. Функция

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

I. Метод кусочно-линейной аппроксимации. Пусть требуется определить максимальное значение вогнутой функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

Чтобы найти решение задачи (80) —(82), заменим функции

Примеры решения задач по математическому программированию

кусочно-линейными функциями

Примеры решения задач по математическому программированию

и перейдем от задачи (80) — (82) к задаче, состоящей в определении максимального значения функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

можно записать в виде

Примеры решения задач по математическому программированию

где

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

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

Подставляя теперь в равенства (83) и (84) выражения функций

Примеры решения задач по математическому программированию

в соответствии с формулами (86), приходим к следующей задаче:

Найти максимальное значение функции

Примеры решения задач по математическому программированию

при условиях

Примеры решения задач по математическому программированию

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

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

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

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

  1. Каждую из сепарабельных функций заменяют кусочно-линейной функцией.
  2. Строят задачу линейного программирования (88)—(91).
  3. С помощью симплексного метода находят решение задачи (88) —(91).
  4. Определяют оптимальный план задачи (80) — (82) и находят значение целевой функции при этом плане.

Пример задачи с решением:

Использование ППП ЛП АСУ для решения задачи нелинейного программирования

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

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

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

Каждый набор переменных имеет свое имя. Это имя записывается в поле 2, в поле 3 помещается ключевое слово ‘MARKER’, а в поле 5— ключевое слово начала набора ‘SEPORG’. Если при этом наборы вспомогательных переменных идут один за другим, то имя конца набора может быть одним и тем же.

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

Пример задачи с решением:

Задачи динамического программирования. Общая характеристика задач динамического программирования и их геометрическая и экономическая интерпретации

К оглавлению…

В рассмотренных выше задачах линейного и нелинейного программирования мы находили их решение как бы в один этап или за один шаг. Такие задачи получили название одноэтапных или одношаговых.

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

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

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

Примеры решения задач по математическому программированию

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

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

Пример задачи с решением:

Нахождение решения задач методом динамического программирования

К оглавлению…

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

Будем считать, что состояние рассматриваемой системы Примеры решения задач по математическому программированию на Примеры решения задач по математическому программированию-м шаге Примеры решения задач по математическому программированию определяется совокупностью чисел

Примеры решения задач по математическому программированию
Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

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

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

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

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

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

Примеры решения задач по математическому программированию

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

Полагая Примеры решения задач по математическому программированию в рекуррентном соотношении (6), получаем следующее функциональное уравнение;

Примеры решения задач по математическому программированию

В этом уравнении Примеры решения задач по математическому программированию будем считать известным. Используя теперь уравнение (7) и рассматривая всевозможные допустимые состояния системы Примеры решения задач по математическому программированию на Примеры решения задач по математическому программированию-м шаге

Примеры решения задач по математическому программированию

…, находим условные оптимальные решения

Примеры решения задач по математическому программированию

и соответствующие значения функции (7)

Примеры решения задач по математическому программированию

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

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

Примеры решения задач по математическому программированию

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

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

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

Чтобы найти оптимальную стратегию управления, т. е. определить искомое решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. А именно: на первом шаге в качестве оптимального управления Примеры решения задач по математическому программированию возьмем найденное условно оптимальное управление Примеры решения задач по математическому программированию. На втором шаге найдем состояние Примеры решения задач по математическому программированию, в которое переводит систему управление Примеры решения задач по математическому программированию. Это состояние определяет найденное условно оптимальное управление которое теперь будем считать оптимальным. Зная Примеры решения задач по математическому программированию, находим Примеры решения задач по математическому программированию, а значит, определяем и т. д. В результате этого находим решение задачи, т. е. максимально возможный доход и оптимальную стратегию управления Примеры решения задач по математическому программированию, включающую оптимальные управления на отдельных шагах;

Примеры решения задач по математическому программированию

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

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

Примеры задач с решением:

Возможно эти страницы вам будут полезны: