ТИПОВЫЕ ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ

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

1. Задача о диете (пищевом рационе)

Постановка задачи. Имеется n видов продуктов питания. Известна стоимость единицы каждого продукта Сi. Из этих продуктов необходимо составить пищевой рацион, который должен содержать m видов полезных элементов (белки, жиры, углеводы и т. п.), причем количество каждого элемента в рационе должно быть не менее Bj. Для каждой единицы i-го продукта известно содержание j-го вида элемента - bij . Требуется так составить пищевой рацион, чтобы обеспечить заданные условия при минимальной стоимости рациона.

Модель.

Пусть xi – количество продуктов i-го вида. Тогда модель задачи имеет следующий вид:

Эта задача ЛП с размерностью 3хN, решается универсальными методами ЛП, например, симплекс-методом.

2. Задача о ранце

Постановка задачи. Имеется N видов предметов, которые турист хочет взять с собою в поход. Известны вес bi каждого предмета и его эффективность ei для туриста. Составить список предметов, помещаемых в рюкзак, учитывая, что предельный вес рюкзака не может быть более заданной величины B. Необходимо, чтобы суммарный эффект от набора предметов был максимальным.

Эту задачу можно рассмотреть в двух вариантах:

1. турист решает вопрос: сколько взять предметов каждого вида.

НЕ нашли? Не то? Что вы ищете?

2. турист по поводу каждого предмета решает, брать его или нет.

Модель 1. Пусть xi – количество предметов каждого вида. Тогда:

Это задача ЦЛП с размерностью 1хN. Решается методами ЦЛП: метод ветвей и границ для ЦЛП, метод Гомори.

Модель 2.

Пусть xi – количество предметов каждого вида, может принимать только два значения 0 или 1.

Модель задачи для второго варианта:

Это задача булевского программирования с размерностью 1хN.

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

Тогда размерность задачи станет равной (N+1)хN.

3. Транспортная задача (ТЗ)

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

Постановка задачи. Имеется m пунктов производства (складов) некоторого одного продукта, задан ai – объем производства в i-м пункте производства, . Есть n пунктов потребления этого продукта, задан bj – объем потребления (поданные заявки на поставку продукта) в j-м пункте потребления, .

Пункты производства связаны с пунктами потребления сетью дорог с определенными тарифами на перевозки. Стоимость перевозки одной единицы продукта (груза) из i –го пункта производства в j-ый пункт потребления равна сij. Необходимо найти оптимальный план перевозок продукции, при котором транспортные издержки минимальны, продукция полностью вывозится из пунктов производства и полностью удовлетворяется потребность в продукции.

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

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

Ограничения группы (a) задают условие: из каждого i-го пункта производства должен быть вывезен весь продукт. Например (рис. 1), из первого пункта производства с объемом производства a1 продукт может быть перевезен в любой пункт потребления. Объемы перевозок неизвестны и составляют: – количество единиц продукции, перевезенных из первого пункта производства в первый пукнт потебления; – количество единиц продукции, перевезенных из первого пункта производства во второй пункт потребления; – количество единиц продукции, перевезенных из первого пункта производства в n-ый пункт потребления. Сумма всех перевезенных единиц продукции должна быть равна a1. Получаем ограничение: .

Ограничения группы (b) задают условие: в каждый j-й пункт потребления завезен весь необходимый продукт.

Размерность задачи: . Транспортная задача – частный случай задачи линейного программирования, в которой все ограничения представлены равенствами. В отличие от общего случая решения задачи ЛП оптимальное решение транспортной задачи всегда существует.

Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ: открытая ТЗ и закрытая ТЗ.

Транспортная задача называется закрытой, если выполняется условие баланса: суммарный объем производства равен суммарному объему потребления:

. (1)

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

Открытая ТЗ имеет место в двух случаях.

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

. (2)

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

, (3)

при этом полагают .

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

. (4)

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

, (5)

при этом полагают .

Методы решения.

· Как задача линейного программирования ТЗ может быть решена симплекс методом.

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

4. Задача о назначении

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

Модель.

Введем обозначения: xij – факт применения i-го работника на j-й работе.

Это задача булевского программирования размерностью (p+p)xpp. Она сводится к задаче ЦЛП с размерностью (2p+p2) x p2. Для этого, так же как и в задаче о ранце вводим дополнительные ограничения:

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

Методы решения задачи о назначении:

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

· некоторыми методами решения ТЗ (задача о назначении рассматривается как частный случай ТЗ);

· при сведении задачи к задаче ЦЛП ее можно решать методами ЦЛП, напрмер, методом ветвей и границ для ЦЛП (гл. 4 данного пособия);

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

3.1.5. Задача о коммивояжере

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

Постановка задачи. Коммивояжер должен объехать N городов. Известны затраты (стоимостные, временные, расстояния) на переезд между i – м и j – м городом, которые заданы в виде матрицы . Коммивояжер, выехав из исходного города, должен объехать все города, посетив каждый один раз, и вернуться в исходный. Требуется определить в каком порядке следует объезжать города, чтобы суммарные затраты были минимальными.

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

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

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

Пусть .

- переезд из i-го города в j-ый включается в маршрут;

- в противном случае.

Ограничения группы (а) задают условие: в каждый город коммивояжер въезжает только один раз. Ограничения группы (b) задают условие: из каждого города коммивояжер выезжает только один раз.

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

Например, для задачи с 5-ю городами в модель добавляются следующие блоки условий:

(6)

(7)

(8)

Условия блока (6) не допускают появления неполных замкнутых циклов между парами городов. Условия блока (7) не допускают появления неполных замкнутых циклов между тремя городами. Аналогичный блок условий (8) вводится для всех четверок городов.

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

Методы решения:

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

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

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

6. Задача о раскрое материалов

Постановка задачи. На раскрой поступает s различных материалов, требуется изготовить n различных видов изделий, причем продукция выпускается комплектами и в комплект входит bk изделий k-го вида. Каждая единица j-го материала может быть раскроена p различными способами так, что при использовании i-го способа получается aijk единиц изделий k-го вида. Известно, что материала j-го вида имеется cj единиц. Найти план раскроя, обеспечивающий максимальное число комплектов при заданных ограничениях на материал.

Модель.

Пусть xij – число заготовок j-го материала, раскроенных i-м способом.

Это задача нелинейного программирования. Размерность задачи: s x ps. Но ее можно привести к линейному виду. Введем еще одну переменную y – количество комплектов. Тогда получим модель:

Полученная модель относится к классу ЛП (ЦЛП). Размерность задачи (s+n) x (p*s+1).

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

Основные порталы (построено редакторами)