Примеры решения типовых задач

Задача № 1

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

Таблица 1.1

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
S1
S2
S3		-
S4			-

Прибыль, получаемая от единицы продукции и – соответственно 4 и 5 руб.

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

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

(1)

Ресурса :

(2)

Ресурса :

(3)

И, наконец, :

(4)

Поскольку потребление ресурсов не должно превышать , , и не должно превышать их запасов, соответственно 18, 16, 5 и 21 ед., то связь между потреблением ресурсов и их запасами выразится системой неравенств:

(5)

Согласно условию задачи:

(6)

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

(7)

Таким образом, экономико-математическая задача: найти такой план выпуска продукции , удовлетворяющий системе (5) и условию (6), при котором функция (7) принимает максимальное значение.

Строим область допустимых решений задачи. Нумеруем ограничения задачи. В прямоугольной декартовой системе координат (рис. 1) строим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

(8)

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

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

(9)

В результате получим . Максимум линейной функции равен:

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

Рис. 1.

Задача № 2

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

поставщики	потребители	запасы
потребности					1000=1000

Решение:

поставщики	потребители	запасы
потребности			0	0	1000=1000

Последовательность заполнения клеток:

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

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

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

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

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

6. В таблице осталась одна строка и один столбец. Это последний шаг процесса, .

Количество заполненных клеток равно 6, . Следовательно, полученный план невырожденный . Значения базисных переменных , , , , , . Остальные переменные – свободные, их значения равны 0. Транспортные расходы (значение целевой функции):

(единиц).

Задача № 3

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

Рис. 2.

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

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

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

Опорный план должен удовлетворять следующим требованиям:

1) все запасы должны быть распределены, а потребности удовлетворены;

2) к каждой вершине должна подходить или выходить из нее хотя бы одна стрелка;

3) общее количество стрелок должно быть на единицу меньше числа вершин ;

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

План распределения груза, отвечающий этим требованиям, представлен на рис. 3.

Далее следует проверить план на оптимальность. Для этого вычисляем потенциалы. Одной из вершин (например, вершине 1) присвоим некоторое значение потенциала (например, равное 10).

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

Рис. 3.

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

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

Вычислим характеристики ребер без стрелок:

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

В нашем примере новая стрелка направлена от вершины II к вершине I (штриховая линия (см. рис. 3). Для определения величины поставки (ρ) для ребра рассматриваются все стрелки образовавшегося замкнутого контура, имеющие направление, противоположное новой стрелке, и среди них находится стрелка с наименьшей поставкой λ (в нашем примере λ = 20 на ребре ). Выбранная таким образом величина прибавляется ко всем поставкам в стрелках, имеющих то же направление, что и новая стрелка, и вычитается из поставок в стрелках, имеющих противоположное направление. Поставки в стрелках, не входящих в контур, сохраняются неизменными. Стрелка, на которой выбрано число λ, ликвидируется, и общее число стрелок остается прежним. Новый опорный план представлен на рис. 4. Полученный план исследуется на оптимальность, подобно предыдущему.

Определим оптимальное значение целевой функции:

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

Рис. 4.

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

Задача № 4

Турист готовится к длительному переходу в горах. В рюкзаке он может нести груз, масса которого не более G кг. Груз может включать n предметов, причем i -й из них обладает массой q _i кг, i = ; для каждого предмета турист определяет его ценность (полезность) с _i во время перехода.

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

Обозначим х _i = 0, если i -й предмет отвергается и х _i = 1, если предмет берут в рюкзак.

Математическая модель задачи

(3)

(4)

, где I = (5)

Метод ветвей и границ является одним из методов решения задачи о «рюкзаке».

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

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

Понятие оценки подмножества (множества)

· Если М_к – некоторое подмножество множества М, то оценкой множества М_к называется число (М_к) такое что, для любого х М_к, где f -целевая функция рассматриваемой оптимизационной задачи.

Алгоритм МВГ

1. Строятся вершины первого уровня. Для каждой вершины подсчитывается оценка φ (М_к). Ветвится вершина, которой соответствует максимальная оценка;

2. Для всех вершин j – го уровня (j = 2,3,…) подсчитывается оценка φ (М_к). Ветвится та из висячих вершин уровня j, у ² – 1, …1, которой соответствует максимальная оценка.

3. Действия пункта 2 повторяются до тех пор пока не будет получено точное решение на последнем n -ом уровне. Конечная висячая вершина отвечает конкретному варианту х ^* = (х ₁^*, х ₂^*,…, х ₄^*). Для него подсчитывается точное значение целевой функции f (х ^*).

4. Если значение f (х ^*) не хуже оценок оставшихся вершин, т.е. f (х ^*) ≥ φ (М_к), то найдено оптимальное решение. Причем:

а) в случае строгого неравенства f (х ^*) > φ (М_к) оптимальное решение единственно.

б) для висячих вершин, в которых f (х ^*) = φ(М_к) производится ветвление и осуществляется поиск других оптимальных решений задачи в соответствии с пунктами 2 и 3.

Если значение f (х ^*) для вершин последнего уровня не лучше значения оставшихся висячих вершин, т.е. f (х ^*) < φ(М_к), то переходят на шаг 2.

При использовании алгоритма МВГ о задаче наилучшей загрузки «рюкзака» учитывают, что каждый предмет может быть выбран единственный раз в единичном количестве.

В общем случае имеется 2ⁿ вариантов, однако часть этих вариантов недопустима, т.к. соответствующий некоторому вектору х вариант может не удовлетворять ограниченного по максимальной загрузке «рюкзака», что позволяет дополнительно отсекать ветви.

Ветвление задачи организуется следующим образом:

1. Все множество вариантов М на два подмножества:

, где М₁ – множество вариантов отвечающих х ₁ = 1 (т.е. выбору первого предмета), а = М₀ – множество вариантов, в которых первый предмет не выбирается (х ₁ = 0).

2. Дальнейшее ветвление ведется аналогично, т.е. разбиваем множества М₀ и М₁ по второй переменной х ₂:

М₁ = М₁₁ U М₁₀ и М₀₁ U М₀₀ и т.д.

В качестве оценки φ (Мj) каждого из рассматриваемых в задаче множеств Мj выбираем значение целевой функции f(х₁^*) соответствующее решениям также задачи (3) – (5), но без ограничения х _i є {0,1} (т.е. допускается выбор кратных и нецелых частей предметов).

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

, т.е. .

Оптимальное решение задачи (3) – (4) без учета условия (5) запишем, выбрав максимальное количество первых предметов:

; для (*)

Указанное предварительное упорядочение заказов позволяет сформулировать эвристическое правило порядка ветвления правило порядка ветвления и для построения оценки каждого следующего множества Мj следует:

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

2.Заменять 6 на оставшийся объем ресурса.

Задача 2

Пусть имеются все необходимые данные для задачи о «рюкзаке», которые уже упорядочены по убывающим K_j и G = 13 … (табл. 1).

Таблица 1

Решение:

1. Оценку множества М проводим в соответствии с соотношениями (*) берем относительное решение вспомогательной задачи х _м^*= (, 0, 0, 0, 0) на котором получим оценку множества М:

2. Произведем разбиение М = М₁ U М₀, где М₁ - множество содержащее варианты с выбором первого предмета, М₀ – множество, содержащее варианты с отказом от первого предмета.

- оптимальное решение ослабленной задачи на множестве М₀ имеют вид х ₀^* = (0, , 0, 0, 0), а оценка этого множества М₀ равна

- оптимальное решение вспомогательной задачи на множестве М₁:

Это решение дает оценку множества М₁ в виде

Полученные оценки множеств М₁ и М₀ равны, следовательно на этом шаге ветвятся оба множества.

1. Продолжим ветвление

множество М₀: → М₀ = М₀₀ М₀₁

Во множестве М₀₀ – содержатся варианты, в которых первые два предмета в «рюкзак» не взяли.

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

Х₀₀^* = (0,0, , 0,0) = (0,0, , 0,0); оценка

Множество М₀₁ включает варианты с отказом от первого предмета и выбором второго. Для него

Х ₀₁^* = (0, 1, , 0, 0) = (0,1, , 0, 0), а оценка

(х ₀₁^*) = 12

4. Поскольку полученные оценки для множеств М₀₀ и М₀₁ меньше висячих вершин М₁, то переходим на ветвь соответствующую множеством с выбором первого предмета.

Производим ветвление М₁: М₁ = М₁₁ М₁₀

Для множества М₁₁ имеем:

х ₁₁^* = (1, 1, , 0, 0) = (1, 1, , 0, 0)

оценка (х ₁₁^*) = 15 .

Для множества М₁₀ имеет относительное решение вспомогательной задачи х ₁₀^* = (1, 0, , 0, 0) = (1, 0, , 0, 0) и оценку (х ₁₀^*) = 15 = 31.

5. Множество М₁₁ = М₁₁₀ М₁₁₁

∙ Для множества М₁₁₀ имеем решение

х ₁₁₀^* = (1, 1, 0, , 0) = (1, 1, 0, 1, 0) и оценку

φ(М₁₁₀) = f (х ₁₁₀^*) = .

∙ Множество М₁₁₁ остается, поскольку ему элементы не удовлетворяют ограничению по ресурсам (1)

g₁ + g₂ + g₃ = 14 > 13.

φ = 39

φ = 39 φ = 39

φ = 26 φ = 30 φ = 31 φ = 35

∑g_ix_i > G

φ = 35

φ = 35 φ = 35

∑g_ix_i > G

φ(М) = f (x ^*₁₁₀₀₀) = 27 φ(M) = f (x ^*₁₁₀₁₀) = 35

φ(M) = f (x ^*₁₁₀₀₁) = 35

f _макс = f (х ^*₁₁₀₀₁) = f (x ^*₁₁₀₁₀) = 35

6. Производим ветвление множества М₁₁₀ = М₁₁₀₀ М₁₁₀₁

- Для множества М₁₁₀₀ решение

х ^*₁₁₀₀ = (1, 1, 0, 0, ) = (1, 1, 0, 0, )

оценка φ(М₁₁₀₀) = f (x ^*₁₁₀₀) = .

- Для множества М₁₁₀₁ имеем решение

х ^*₁₁₀₁ = (1, 1, 0, 1 ) = (1, 1, 0, 1, 0) и его оценку φ(М₁₁₀₁) = f (x ^*₁₁₀₁) = .

7. Поскольку множества М₁₁₀₀ и М₁₁₀₁ имеют одинаковые оценки производим ветвление обоих множеств и просмотрим решения последнего уровня.

М₁₁₀₀ = М₁₁₀₀₀ М₁₁₀₀₁ и М₁₁₀₁ = М₁₁₀₁₀ М₁₁₀₁₁

- Для множества М₁₁₀₀₀ решение х ^*₁₁₀₀₀ = (1, 1, 0, 0, 0)

оценка φ(М₁₁₀₁₀) = f (x ^*₁₁₀₀₀) = 15

- Для множества М₁₁₀₀₁: х ^*₁₁₀₀₁ = (1, 1, 0, 0, 1)

оценка φ(М₁₁₀₀₁) = f (x)^*₁₁₀₀₁) = .

- Множество М₁₁₀₁₁ – выходит за ограничения по ресурсу

.

Вывод: Задача имеет два оптимальных решения

х^* ₁₁₀₁₁ = (1, 1, 0, 0, 1) и х ^*₁₁₀₁₀ = (1, 1, 0, 1, 0), на которых целевая функция f (х ^*₁₁₀₁₀) = f (x ^*₁₁₀₀₁) = 35.

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