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

⇐ ПредыдущаяСтр 5 из 9Следующая ⇒

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

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

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

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

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

Все методы целочисленной оптимизации можно разделить на три основные группы:

1. Методы отсечения

2. Комбинаторные методы

3. Приближенные методы

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

- оно должно быть линейным;

- должно отсекать найденный оптимальный нецелочисленный план;

- не должно отсекать ни одного целочисленного плана.

Далее задача решается с учетом нового ограничения (правильного отсечения). После этого в случае необходимости добавляется еще одно ограничение и т.д.

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

На рисунке 1 ОКLM – область допустимых решений задачи, ограниченная прямыми (1), (2), (3) и осями координат; L – точка оптимального, но нецелочисленного решения задачи; (4) – прямая, отсекающая это нецелочисленное решение; OKNM – область допустимых решений расширенной задачи с новым ограничением; N – точка оптимального целочисленного решения.

Рис. 1. Графическая иллюстрация метода отсечения

Один из алгоритмов решения задачи линейного целочисленного программирования методом отсечения, предложенный Р. Гомори, основан на симплексном методе^{^[3]} и использует достаточно простой способ построения правильного отсечения.

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

, (1)

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

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

Замечание. Под дробной частью некоторого числаа понимается наименьшее неотрицательное число b такое, что разность а и bесть целое, например, , т.к. -3, 35-0, 65=-4 – целое число.

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

Пример. Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Фермер может заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед., требующие производственную площадь 3 кв. м, и производительностью за смену 2 т зерна, и более мощные машины типа В стоимостью 4 ден. ед., занимающие площадь 5 кв. м, и производительностью за смену 3 т сортового зерна.

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

Решение. Обозначим через количество машин соответственно типа А и В, через Z – общую производительность.

ЭММ задачи:

Приведем модель задачи к каноническому виду:

(2)

Решаем задачу симплексным методом. Графическая иллюстрация решения представлена на рисунке 1.

Первая симплексная таблица:

Базис	Свободный член	Переменные	Оценочные отношения




Z		-2	-3

Вторая симплексная таблица:

Базис	Свободный член	Переменные	Оценочные отношения

				-5	20/3
				-4	2/3

Z		-2

Третья симплексная таблица:

Базис	Свободный член	Переменные	Оценочные отношения

				-1	-1
	2/3			1/3	-4/3

Z				2/3	1/3

Получили оптимальное решение:

; ,

которое не является целочисленным.

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

В соответствии с (1) к системе ограничений добавляем неравенство

или, учитывая, что , т.к. – целое, получим

Вводим балансовую переменную :

или, после деления на (-1), чтобы коэффициент при стал равен 1, получим:

Включим в систему ограничений (в последнюю симплекс-таблицу) новую балансовую переменную в качестве основной переменной:

Базис	Свободный член	Переменные	Оценочные отношения

				-1	-1
	2/3			1/3	-4/3

	-2/3			-1/3	-2/3
Z				2/3	1/3

Видим, что полученное базисное решение – недопустимо.

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

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

Выберем в качестве основной переменной, например, . В правильном отсечении

разделим все на 2/3, чтобы коэффициент при переменной стал равен 1:

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

Пересчет элементов следующей таблицы осуществляем обычным для симплекс-метода способом:

Базис	Свободный член	Переменные	Оценочные отношения

				-1/2	-3/2
					-2
				-1/2	3/2
				1/2	-3/2
Z				1/2	1/2

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

В последней строке нет отрицательных значений. В результате, в столбце «Свободный член», получаем целочисленное оптимальное решение:

X=(2, 7, 19, 0, 1, 0); Z=25.

Экономический смысл полученного решения:

максимальную производительность 25 т сортового зерна за смену можно получить приобретением 2 машин типа А и 7 машин типа В; при этом незанятая площадь помещения составит 19 кв. м, остатки денежных средств из выделенных равны нулю, в резерве для покупки – 1 машина типа В. Шестая компонента содержательного смысла не имеет.

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

или .

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

- из системы ограничений модели (2) имеем

- подставляя эти выражения в дополнительное ограничение вместо переменных и , получим

или, после преобразований,

Прямая (4) на рисунке 1 задана соответствующим полученному неравенству уравнением

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

Пример. Управляющему банком были представлены 4 проекта, претендующие на получение кредита в банке. Ресурс банка в каждый период, потребности проектов и прибыль по ним приведены в таблице (в тыс. долл.).

Проект	Потребность проекта в объеме кредита	Прибыль
Период 1	Период 2	Период 3	Период 4
А
Б
В
Г				17, 5
Ресурсы банка

При выборе проектов следует принять во внимание потребности проектов в объемах кредитов и ресурсы банка для соответствующих периодов.

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

Решение. Переменные задачи являются двоичными, при этом

ЭММ задачи имеет обычный вид с дополнительным условием двоичности

Решение задач с двоичными переменными целесообразно проводить в Excel с использованием надстройки «Поиск решений», позволяющей вводить дополнительно условия как целочисленности, так и двоичности переменных [5]. Результат решения данной задачи в «Поиске решений» приведен на рисунке 2.

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

2.2.Транспортная задача. Методы построения опорного плана. Улучшение плана методом потенциалов

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

Постановка задачи. В т пунктах A₁, A₂, …, A_m(далее – поставщики), сосредоточены некоторые количества однородного продукта (запасы), которые обозначим соответственно а_i (i = 1, 2, ..., m). Данный продукт потребляется в п пунктах (далее – потребители) В₁, В₂, …, В_n; объемы потребления (потребности) равны соответственно b_j (j = 1, 2, ..., п). Расходы (тарифы) на перевозку единицы продукта из пункта A_i в пункт B_j равны c_ij и приведены в матрице транспортных расходовС = (c_ij). Требуется составить такой план перевозок, при котором суммарные затраты на них были бы минимальны.

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

Таблица 1 – Исходные данные транспортной задачи

Поставщики	Потребители	Запасы
		…		…
			…		…
			…		…
…	…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…	…
			…		…
Потребности			…		…

Различают открытую и закрытую транспортные задачи.

Если суммарные запасы груза у поставщиков равны суммарным потребностям в грузе потребителей, т.е.

, (*)

то задача называется закрытой.

Если равенство (*) не выполняется, то задача открытая.

Экономико-математическая модель закрытой транспортной задачи:

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

Если задача открытая, то возможны два случая:

1) суммарных потребностей больше, чем суммарных запасов, т.е.

Тогда не все потребности будут удовлетворены и модель примет вид

2) суммарных запасов больше, чем суммарных потребностей, т.е.

Тогда не все запасы будут вывезены и модель примет вид

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

1. Построение первоначального (опорного) плана перевозок, длячего можно использовать различные методы: метод северо-западного угла, наименьших затрат (тарифов), метод аппроксимации Фогеля[2].

Замечание. Сущность этих методов состоит в том, что начальный опорный план находят за не более чем (m+n-1) шагов. При этом число заполненных клеток (число базисных переменных) также оказывается равным (m+n-1) (это одновременно ранг системы линейных уравнений (1) – (2)).Такой план называется невырожденным. Нередко при решении задачи возникает вырожденный план с меньшим числом занятых клеток (когда какие-то из базисных переменных равны 0). В этом случае, как правило, выбирается свободная клетка (или несколько свободных клеток – в зависимости от вырожденности плана) с наименьшим тарифом, которая в дальнейшем формально считается занятой с нулевой перевозкой.

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

2. Построение системы потенциалов и проверка первоначального плана на оптимальность

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

= + .

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

3. Реализация циклов перераспределения (корректировка плана прикрепления потребителей к поставщикам и объема поставок), после чего переходят к этапу 2.

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

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

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

Таблица 2 – Исходные данные задачи

Поставщики	Потребители	Запасы




Потребности

Решение. Данная задача является открытой, т.к. суммарные запасы груза 40+60+90=190 у поставщиков на 10 единиц меньше, чем суммарные потребности в грузе 45+35+55+65=200 потребителей.

Экономико-математическая модель задачи:

- в компактной форме (с использованием знаков суммирования)

- в развернутом виде

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

Таблица 3 – Исходные данные с фиктивным поставщиком

Поставщики	Потребители	Запасы




Ф
Потребности

1 этап.Первоначальное распределение поставок найдем двумя методами:

а)метод северо-западного угла

Заполнение начинаем с левой верхней клетки, то есть с северо-западного угла. Так как потребности первого потребителя равны 45, а возможности первого поставщика – 40, то в клетку с номером (1, 1) записываем максимально возможную поставку – 40. Запасы первого поставщика исчерпаны, поэтому первую строку исключаем из рассмотрения (оставшаяся ее часть закрашена штриховкой). Недостающий первому потребителю груз в 5 единиц поставляем за счет запасов второго поставщика. В результате потребность первого потребителя в 45 единиц груза удовлетворена полностью, и первый столбец исключается из рассмотрения. Аналогично продолжаем далее до получения первоначального распределения поставок (см. табл. 4).

Заметим, что занятыми оказались m+n-1=4+4-1=7клеток таблицы.

Первоначальное распределение поставок имеет общую стоимость, равную

усл. ден. ед.

Замечание.

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

Таблица 4 – Первоначальное распределение поставок методом северо-западного угла

Поставщики	Потребители	Запасы




Ф
Потребности

б)метод наименьших затрат(тарифов)

Находим в таблице поставок клетки с наименьшими тарифами. Таких клеток четыре – (4, 1), (4, 2), (4, 3), (4, 4). Их тарифы равны 0. Сравним максимально возможные поставки для этих клеток:

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

В оставшейся таблице наименьший тариф, равный 1, в клетке с номером (1, 2). Максимально возможная поставка в нее . Второй столбец выпадает из рассмотрения.

Минимальный тариф теперь в клетках (1, 3) и (3, 4). Сравним максимально возможные поставки:

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

Далее аналогично заполняем клетки (1, 3), (2, 3), (2, 1), (3, 1). В результате получим первоначальное распределение, представленное в таблице 5.

Таблица 5 – Первоначальное распределение поставок методом наименьших затрат

Поставщики	Потребители	Запасы




Ф
Потребности

Заполнено такжеm+n-1=4+4-1=7 клеток.

Первоначальное распределение поставок имеет общую стоимость, равную

усл. ден. ед.

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

2 этап.Построение системы потенциалов и проверка начального плана на оптимальность

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

= +

Для начала расчета потенциалов положим u₁=0.Тогда

v₂= u₁+с₁₂=0+1=1, v₃= u₁+с₁₃=0+2=2, u₂= v₃-с₂₃=2-3=-1 и т.д.

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

Таблица 6 – Результаты расчета потенциалов

Поставщики	Потребители	Запасы


			-1
			-2
Ф
Потребности

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

. (3)

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

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

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

После расчетов по формуле (3) матрица оценок примет вид

Пояснение к определению оценок:

и т.д.

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

3 этап.Реализация циклов перераспределения (корректировка плана прикрепления потребителей к поставщикам и объемов поставок).

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

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

Таблица 7 – Контур перераспределения

Поставщики	Потребители	Запасы


	3 +		3 –		-1
	– 35			2 +	-2
Ф			+	– 10
Потребности

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

В вершинах контура расставляются поочередно знаки «+» и «–», начиная со знака «+» в выбранной свободной клетке.

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

В нашем примере наименьшая из величин поставок в вершинах контура со знаком «–» или поставка, передаваемая по циклу, равна

Передвигая по циклу поставку 10, получим следующее новое распределение поставок (см. табл.8).

⇐ Предыдущая 1 2 3 456 7 8 9 Следующая ⇒