Методы оптимальных решений
Пример про стирку
В нашей жизни часто возникают задачи, в которых нужно не просто найти "любое решение" (которое, как раз, достаточно легко найти), а "наилучшее" из возможных решений. Приведем пример. Допустим, у нас есть стиральная машина, в которую можно загрузить 6 килограмм белья. И есть наборы белья, весом 1,2,4,5,6 килограмм. Каждый набор необходимо стирать только целиком. Требуется составить программу стирки наилучшим образом.
Тут мы явно видим, что "какое-то" решение найти очень просто. Например, будем брать наборы белья по-порядку:
| Номер стирки | Какие наборы берем в стирку | Сколько кг белья стираем в этот раз |
| 1 | 1+2 | 3 |
| 2 | 4 | 4 |
| 3 | 5 | 5 |
| 4 | 6 | 6 |
Итого, мы запустим стиральную машину 4 раза. Решение? Вполне себе решение. И вполне себе можно так и сделать - постирать 4 раза, и задача будет решена.
Но нам-то нужно именно "лучшее" решение. Будет ли наше решение, в котором мы стираем 4 раза лучшим? А вдруг можно так перетасовать белье, чтобы стирать 3 раза? Или даже 2 раза? На самом деле, в 3 раза вполне можно уложиться:
| Номер стирки | Какие наборы берем в стирку | Сколько кг белья стираем в этот раз |
| 1 | 6 | 6 |
| 2 | 2+4 | 6 |
| 2 | 1+5 | 6 |
Это решение будет оптимальным - ведь за два раза можно постирать максимум $2\cdot6=12$ килограмм, а у нас $1+2+4+5+6=18$.
Задачи оптимизации
Такие задачи, где нужно найти наилучшее решение из возможных, называются задачами оптимизации. В таких задачах, как правило, выделяют два аспекта:
- Ограничения - это то, что ограничивает наши решения. Например, в нашей задаче мы не могли постирать все белье сразу, оно не влезло бы в стиральную машину. Поэтому максимальный объем белья в стиральной машине в нашем случае является ограничением. Как правило ограничения записываются в виде равенств или неравенств. В нашем случае это неравенство "количество белья, которое мы можем постирать за раз должно быть МЕНЬШЕ ИЛИ РАВНО 6 килограммам".
- Целевая функция - это некоторое числовое значение, которое показывает, насколько хорошо мы решили задачу. В нашем случае это количество стирок. Чем оно меньше, тем лучше. То есть, говоря по математически, число стирок, то есть целевую функцию, нужно "минимизировать". Иногда наоборот, целевую функцию необходимо максимизировать, сделать как можно больше - например, если целевая функция это прибыль предприятия от продажи товаров. Предприятие всегда стремится заработать как можно больше.
Такие задачи называются задачи оптимизации, а область математики, которая ищет ответы на такие задачи называется "Математическим программированием" (Изучается в курсах "Исследование операций", "Методы оптимальных решений" и т.п.).
Как правило, такие задачи приходят к нам именно из жизни, как задача, приведенная выше. Среди самых распространенных задач оптимизации, пришедших из жизни можно выделить следующие.
Основные типы оптимизационных задач
- Производственная задача - существует некоторое предприятие, которое может выпускать некоторые изделия. На то, чтобы их выпустить необходимы различные ресурсы. Задано, сколько и каких ресурсов необходимо для каждого изделия, задано сколько ресурсов у нас имеется, и задано, сколько предприятие выручит за продажу произведенных изделий. Необходимо выбрать, какие изделия и в каком количестве выпускать, чтобы прибыль предприятия была максимальной.
- Транспортная задача - существуют несколько предприятий, производящих некий ресурс, и существуют предприятия, которые его потребляют. Задано сколько единиц ресурса производит или потребляет каждое предприятие. Задано расстояние между каждым поставщиком и каждым потребителем ресурса. Необходимо перевезти ресурс от поставщиков к потребителям, чтобы при этом затратить как можно меньше бензина (то есть, проехать как можно меньше километров)
- Задача об инвестициях - существует некоторое количество предприятий, в которые можно вложить инвестиции. Задана максимальная сумма инвестиций, и задана прибыль, которую можно получить, если вложить некоторое количество денег в какое-либо предприятие. Необходимо выбрать, сколько денег вложить в каждое предприятие, чтобы итоговая прибыль была максимальной
- Задача о назначениях - существует некоторое количество людей, и некоторое количество работ, которые необходимо выполнить. Задано, какую стоимость нужно будет заплатить каждому человеку за выполнение каждой работы. Необходимо выбрать, какому человеку какую работу дать, чтобы все работы были выполнены, и необходимо было заплатить как можно меньше
- Задача коммивояжера - существует некоторое количество городов, и указаны все расстояния между городами. Некому "коммивояжеру" необходимо посетить все города по одному разу (не заходя в один город дважды), при этом ему нужно передвигаться как можно меньше
- Задача о ранце - существует некий ранец заданного объема. Также существует набор предметов, для каждого из которых задан их объем, и стоимость. Необходимо так наполнить ранец, чтобы все предметы в него влезли по объему, и их стоимость была максимальной
Если задача математического программирования пришла из жизни, то ее решением занимается дисциплина "Исследование операций". Именно она решает задачи из вышеприведенного списка.
Линейное и нелинейное программирование
Кроме этого, задачи математического программирования делятся на два больших класса:
- Если в задаче как ограничения, так и целевая функция представляют собой линейные функции, то есть, многочлены первой степени, то такая задача называется задачей линейного программирования. Например, если в нашей задаче про стирку мы обозначим количество взятых наборов №1, 2, 3, 4, 5 за $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, то количество итоговых килограмм должно получиться меньше или равно шести. То есть, $x_1+2x_2+4x_3+5x_4+6x_5\leq6$. Это ограничение линейно. Тем не менее, полностью нашу задачу за задачу линейного программирования принять нельзя, так как линейной должна быть еще и целевая функция, кроме того у нас есть неявное условие, что переменные $x_1-x_5$ должны принимать только значения $0$ (мы не берем набор) или $1$ (мы берем набор), а это ограничение нельзя записать в линейной форме.
- Если в задаче либо оганичения, либо целевая функция (либо и то, и другое) выражены в каком-либо другом виде, то данная задача называется задачей нелинейного программирования. Например, так было бы, если бы наше ограничение имело вид $x_1+3x_2^2+5x_3^3+10x_4^4+\sin(x_5)\geq100$
Задачи линейного программирования решаются, как правило, гораздо легче и быстрее, чем задачи нелинейного программирования. Поэтому мы и рассмотрим их в первую очередь.
В следующем разделе мы рассмотрим самую часто встречающуюся задачу линейного программирования - производственную задачу, и методы, которые позволяют ее решать. Однако, на самом деле, теми же самыми методами, как мы убедимся позднее, можно решить и любую другую задачу линейного программирования.
Далее: 2.1. Производственная задача
