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

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

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

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

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

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

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

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

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

Е=7х1+9х2→max

1+3х2≤6

12≤35

х1, х2≥0

х1, х2 – целые числа.

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

Е=7х1+9х2→max

1+3х23=6

124=35

х1, х2, х3, х4≥0

х1, х2 – целые числа.

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

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

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

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

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

7/22х3+1/22х4≥1/2

-7/22х3-1/22х45=-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.

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

-1/7х4-6/7х56=-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.

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

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

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

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

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

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

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

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

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

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

Пример.

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

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

40х1+25х2≤1000

35х1+28х2≤980

25х1+35х2≤875

х1, х2≥0

х1, х2 – целые числа.

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


   
  X1 = 16,94; X2 = 12,9; E = 38,39  
Некоторые особенности двойственного симплекс-метода - student2.ru Некоторые особенности двойственного симплекс-метода - student2.ru 2
X2 ≤ 12 X1 = 17,5; X2 = 12; E = 37,8 X2 ≥ 13 X1 = 16,8; X2 = 13; E = 38,36
Некоторые особенности двойственного симплекс-метода - student2.ru Некоторые особенности двойственного симплекс-метода - student2.ru
не перспективно
  X2 ≥ 13; X1 ≤ 16 X1 = 16; X2 = 13,57; E = 38,2 X2 ≥ 13; X1 ≥ 17 нет решений
  Некоторые особенности двойственного симплекс-метода - student2.ru Некоторые особенности двойственного симплекс-метода - student2.ru  
  X2 ≥ 13; X1 ≤ 16; X2 ≤ 13 X1 = 16; X2 = 13; E = 37,4 X2 ≥ 13; X1 ≤ 16; X2 ≥ 14 X1 = 15,4; X2 = 14; E = 38,08  
  Некоторые особенности двойственного симплекс-метода - student2.ru Некоторые особенности двойственного симплекс-метода - student2.ru
  X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≤ 15 X1 = 15; X2 = 14,29; E = 38,01 X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≥ 16 нет решений
Некоторые особенности двойственного симплекс-метода - student2.ru Некоторые особенности двойственного симплекс-метода - student2.ru
X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≤ 15; X2 ≤ 14 X1 = 15; X2 = 14; E = 37,6 X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≤ 15; X2 ≥ 15 X1 = 14; X2 = 15; E = 37,8
                           

ПРИЛОЖЕНИЕ 3

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

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

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

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

1) запасы грузов в ПО заданы вектором ā = (а1, а2, …, аj, …, аm);

2) потребности в грузах в ПН заданы вектором  = (b1, b2, …, bi, …, bn);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Некоторые особенности двойственного симплекс-метода - student2.ru Алгоритм решения транспортной задачи методом потенциалов

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

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

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

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

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

Замечания:

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

1) Некоторые особенности двойственного симплекс-метода - student2.ru для всех базисных клеток;

2) Некоторые особенности двойственного симплекс-метода - student2.ru для всех небазисных клеток.

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

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

Некоторые особенности двойственного симплекс-метода - student2.ru Задача о назначениях и ее решение по двухэтапной схеме методом К. Мака

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

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

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

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

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

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

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

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

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

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

«Имеются 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 примера)

.

Наши рекомендации