Некоторые особенности двойственного симплекс-метода

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

2. Ведущая строка определяется максимальным по модулю отрицательным элементом столбца решения;

3. Ведущий столбец определяется минимальным по модулю отношением элементов Е-строки к отрицательным элементам ведущей строки;

4. Ведущая строка и ведущий столбец определяют ведущий элемент и, следовательно, исключаемую и включаемую переменную;

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

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

 

Пример реализации целочисленной оптимизации на основе метода Гомори.

Формальная модель задачи:

Е=7х₁+9х₂→max

-х₁+3х₂≤6

7х₁+х₂≤35

х₁, х₂≥0

х₁, х₂ – целые числа.

Приведем задачу к ОЗЛП в базисной форме:

Е=7х₁+9х₂→max

-х₁+3х₂+х₃=6

7х₁+х₂+х₄=35

х₁, х₂, х₃, х₄≥0

х₁, х₂ – целые числа.

Решим задачу оптимизации на основе симплекс-таблиц.

Полученное оптимальное решение представлено в следующей таблице:

Базис	Х1	Х2	Х3	Х4	Решение
Е			28/11	15/11
Х2			7/22	1/22	7/2
Х1			-1/22	3/22	9/2

 

Оптимальное решение без учета условия целочисленности (х₁; х₂) = (9/2; 7/2), Е=63.

Введем дополнительные ограничения, соответствующие переменной х₂ (в данном случае – всё равно какой, т.к. ½ - дробная часть для обеих переменных).

7/22х₃+1/22х₄≥1/2

-7/22х₃-1/22х₄+х₅=-1/2

Выполним симплексные преобразования с учетом дополнительного ограничения:

 

Базис	Х1	Х2	Х3	Х4	Х5	Решение
Е			28/11	15/11
Х2			7/22	1/22		7/2
Х1			-1/22	3/22		9/2
Х5			-7/22	-1/22		-1/2

 

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

а) ведущая строка определяется максимальным по модулю отрицательным элементом столбца «Решение» (-1/2);

б) ведущий столбец определяется минимальным по модулю отношением элементов Е-строки к отрицательным элементам ведущей строки (8 и 30 соотв.);

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

Пересчитываем симплекс-таблицу:

 

Базис	Х1	Х2	Х3	Х4	Х5	Решение
Е
Х2
Х1				1/7	-1/7	32/7
Х3				1/7	-22/7	11/7

 

Введем дополнительное ограничение, соответствующее переменной х₁.

1/7х₄+6/7₄≥4/7

-1/7х₄-6/7х₅+х₆=-4/7

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

 

Базис	Х1	Х2	Х3	Х4	Х5	Х6	Решение
Е
Х2
Х1				1/7	-1/7		32/7
Х3				1/7	-22/7		11/7
Х6				-1/7	-6/7		-4/7

 

Пересчитываем таблицу по правилам симплекс-метода:

Базис	Х1	Х2	Х3	Х4	Х5	Х6	Решение
Е
Х2
Х1					-4
Х3					-4
Х4						-7

 

Полученное оптимальное целочисленное решение: Х1=4; Х2=3; Х3=1; Х4=4. Е=55.

 

Метод ветвей и границ

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

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

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

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

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

а) задача не имеет допустимых решений;

б) в задаче получено целочисленное решение;

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

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

Пример.

Формальная модель задачи:

Е=1,2х₁+1,4х₂→max

40х₁+25х₂≤1000

35х₁+28х₂≤980

25х₁+35х₂≤875

х₁, х₂≥0

х₁, х₂ – целые числа.

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

 

X 1 = 16,94; X 2 = 12,9; E = 38,39

2

X 2 ≤ 12 X 1 = 17,5; X 2 = 12; E = 37,8

X 2 ≥ 13 X 1 = 16,8; X 2 = 13; E = 38,36

не перспективно

X 2 ≥ 13; X 1 ≤ 16 X 1 = 16; X 2 = 13,57; E = 38,2

X 2 ≥ 13; X 1 ≥ 17 нет решений

X 2 ≥ 13; X 1 ≤ 16; X 2 ≤ 13 X 1 = 16; X 2 = 13; E = 37,4

X 2 ≥ 13; X 1 ≤ 16; X 2 ≥ 14 X 1 = 15,4; X 2 = 14; E = 38,08

X 2 ≥ 13; X 1 ≤ 16; X 2 ≥ 14; X 1 ≤ 15 X 1 = 15; X 2 = 14,29; E = 38,01

X 2 ≥ 13; X 1 ≤ 16; X 2 ≥ 14; X 1 ≥ 16 нет решений

X 2 ≥ 13; X 1 ≤ 16; X 2 ≥ 14; X 1 ≤ 15; X 2 ≤ 14 X 1 = 15; X 2 = 14; E = 37,6

X 2 ≥ 13; X 1 ≤ 16; X 2 ≥ 14; X 1 ≤ 15; X 2 ≥ 15 X 1 = 14; X 2 = 15; E = 37,8

ПРИЛОЖЕНИЕ 3

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

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

Общая постановка транспортной задачи:

«Определить оптимальный по стоимости план перевозок однородного груза из m пунктов отправления (ПО) в n пунктов назначения (ПН) в следующих условиях:

1) запасы грузов в ПО заданы вектором ā = (а₁, а₂, …, а_j, …, а_m);

2) потребности в грузах в ПН заданы вектором  = (b₁, b₂, …, b_i, …, b_n);

3) тарифы на перевозку единицы груза из j-го ПО в i-ый ПН заданы матрицей (C_ij)».

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

Если условие не выполняется, то в задачу вводится либо фиктивный пункт ПН с потребностью (тарифы С_in+1 =0 для всех j=1,m), либо фиктивный ПО с запасом (тарифы С_m+1i =0 для всех i=1,n).

Решение транспортной задачи выполняется в 2 этапа:

Этап 1. Определяется начальный опорный план перевозок одним из трех методов:

· метод «северо-западного угла»;

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

· метод Фогеля.

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

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

Метод «северо-западного угла»:

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

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

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

Метод ориентируется на минимальные тарифы матрицы перевозок. Происходит оптимизация текущего шага.

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

Метод Фогеля:

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

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

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

Пример решения задачи распределительным методом.

 

Алгоритм решения транспортной задачи методом потенциалов

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

ШАГ №1. Любым методом определяется начальный опорный план перевозок, в котором есть базисные и свободные клетки.

ШАГ №2. Определяются потенциалы (U_j, V_i) таким образом, чтобы в любой базисной клетке псевдостоимость была равна стоимости (псевдотариф был равен тарифу). Причем для расчета один из потенциалов можно назначить произвольно (например, положить равным нулю).

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

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

Замечания:

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

1) для всех базисных клеток;

2) для всех небазисных клеток.

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

Пример решения транспортной задачи методом потенциалов.

 

Задача о назначениях и ее решение по двухэтапной схеме методом К. Мака

Задача о назначениях имеет важное практическое значение и связана с распределением:

· исполнителей по работам;

· рабочих по станкам;

· механизмов по объектам;

· заказов по предприятиям;

· задач по компьютерам;

· автобусам по маршрутам;

· самолетов по авиалиниям;

· инвестиций по проектам и т.д.

Задача о назначениях формулируется следующим образом:

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

Замечания:

1) Если задана матрица выигрышей, то следует перейти к матрице затрат;

2) Если количество исполнителей и работ не совпадает, то вводятся фиктивные исполнители или фиктивные работы (аналогично транспортной задаче с неправильным балансом);

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

Метод Мака реализуется по двухэтапной схеме:

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

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

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

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

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

 

краны	объекты
№1	№2	№3	№4
№1	3	7	5	8
№2	2	4	4	5
№3	4	7	2	8
№4	9	7	3	8

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

Решение.

Этап 1. Каждый кран назначается на объект по минимальным затратам на выполнение работ. Причем на объекты №2 и №4 краны не назначены.

краны	объекты
№1	№2	№3	№4
№1	3	7	5	8
№2	2	4	4	5
№3	4	7	2	8
№4	9	7	3	8

Этап 2. К элементам столбца №1 прибавлено число 2, что позволяет кран №2 назначить на объект №2, причем на объект 4 кран не назначен.

краны	объекты
№1	№2	№3	№4
№1	6	8	10	8
№2	5	5	9	5
№3	7	8	7	8
№4	12	8	8	8

К элементам столбцов №1 и 2 прибавлено число 1, к элементам столбца №3 – 5, что позволяет кран 4 назначить на объект 4. Останов вычислительного процесса, так как все краны распределены по объектам.

Оптимальное решение: Кран №1 выполняет монтаж объекта №1; №2-№2; №3 - №3; №4 - №4. Минимальные затраты времени на монтаж всех объектов 17 крано-суток.

(еще 2 примера)

 

.