Некоторые особенности двойственного симплекс-метода
1. При добавлении нового ограничения оптимальное решение становится недопустимым, так как в столбце решений появляется отрицательный элемент;
2. Ведущая строка определяется максимальным по модулю отрицательным элементом столбца решения;
3. Ведущий столбец определяется минимальным по модулю отношением элементов Е-строки к отрицательным элементам ведущей строки;
4. Ведущая строка и ведущий столбец определяют ведущий элемент и, следовательно, исключаемую и включаемую переменную;
5. Пересчет симплекс-таблиц осуществляется на основе стандартных процедур симплекс-метода.
Если все элементы столбца решений неотрицательны, то это означает останов вычислительного процесса, т.к. допустимое и одновременно оптимальное решение найдено.
Пример реализации целочисленной оптимизации на основе метода Гомори.
Формальная модель задачи:
Е=7х1+9х2→max
-х1+3х2≤6
7х1+х2≤35
х1, х2≥0
х1, х2 – целые числа.
Приведем задачу к ОЗЛП в базисной форме:
Е=7х1+9х2→max
-х1+3х2+х3=6
7х1+х2+х4=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х4+х5=-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х5+х6=-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+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 | |||||||||||||
  2
| |||||||||||||
| X2 ≤ 12 X1 = 17,5; X2 = 12; E = 37,8 | X2 ≥ 13 X1 = 16,8; X2 = 13; E = 38,36 | ||||||||||||
| 
| ||||||||||||
| не перспективно | |||||||||||||
| X2 ≥ 13; X1 ≤ 16 X1 = 16; X2 = 13,57; E = 38,2 | X2 ≥ 13; X1 ≥ 17 нет решений | ||||||||||||
| 
| ||||||||||||
| 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 | ||||||||||||
| 
| ||||||||||||
| X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≤ 15 X1 = 15; X2 = 14,29; E = 38,01 | X2 ≥ 13; X1 ≤ 16; X2 ≥ 14; X1 ≥ 16 нет решений | ||||||||||||
| 
| ||||||||||||
| 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
| Общая постановка транспортной задачи линейного программирования и методы составления начального плана перевозок |
Транспортная задача (ТЗ) является частным случаем задачи линейной оптимизации. Таким образом, для решения ТЗ применимы процедуры симплекс-метода. Однако для решения задачи существуют специальные методы (метод потенциалов, распределительный метод), которые призваны упростить процесс решения сложных задач (с большим количеством переменных).
Общая постановка транспортной задачи:
«Определить оптимальный по стоимости план перевозок однородного груза из m пунктов отправления (ПО) в n пунктов назначения (ПН) в следующих условиях:
1) запасы грузов в ПО заданы вектором ā = (а1, а2, …, аj, …, аm);
2) потребности в грузах в ПН заданы вектором = (b1, b2, …, bi, …, bn);
3) тарифы на перевозку единицы груза из j-го ПО в i-ый ПН заданы матрицей (Cij)».
Для решения транспортной задачи должно выполняться условие 
, то есть сумма запасов на всех ПО = сумме потребностей всех ПН. Такие задачи называются транспортными задачами с правильным балансом.
Если условие не выполняется, то в задачу вводится либо фиктивный пункт ПН с потребностью 
(тарифы Сin+1 =0 для всех j=1,m), либо фиктивный ПО с запасом 
(тарифы Сm+1i =0 для всех i=1,n).
Решение транспортной задачи выполняется в 2 этапа:
Этап 1. Определяется начальный опорный план перевозок одним из трех методов:
· метод «северо-западного угла»;
· метод минимального элемента;
· метод Фогеля.
Этап 2. Определяется оптимальный план перевозок в результате итерационных улучшений опорного плана перевозок (распределительный метод, метод потенциалов и его модификации).
Пример. Сравнительный анализ различных методов определения начального опорного плана.
Метод «северо-западного угла»:
Метод исключительно прост, так как не учитывает тарифы на перевозку. Оптимизация отсутствует.
Технология: Начиная с верхнего левого угла матрицы перевозок записываем в каждую ячейку максимально возможный объем перевозимого груза (минимальная из двух величин: остаток груза в ПО и неудовлетворенная потребность в ПН). ПО с исчерпанными запасами и ПН с закрытыми потребностями постепенно выбывают из рассмотрения. Процесс продолжается до полного заполнения матрицы.
Метод минимального элемента:
Метод ориентируется на минимальные тарифы матрицы перевозок. Происходит оптимизация текущего шага.
Технология: В матрице перевозок находится ячейка, которой соответствует минимальный тариф на перевозку. Если таких ячеек несколько, выбирается любая. В выбранную ячейку записывается максимально возможный объем перевозимого груза (-//-). ПО с исчерпанными запасами и ПН с закрытыми потребностями постепенно выбывают из рассмотрения. Процесс продолжается до полного заполнения матрицы.
Метод Фогеля:
Метод учитывает все тарифы в матрице. Происходит оптимизация текущего шага с учетом следующего.
Технология: По строкам и столбцам матрицы находятся наиболее дешевые тарифы, после чего рассчитываются их возможные минимальные удорожания на следующем шаге. Удорожание рассчитывается как разница между предпоследним по дешевизне доступным тарифом по каждой строке/столбцу и самым дешевым доступным тарифом в той же строке/столбце. Для заполнения выбирается одна строка или столбец, по которым на следующем шаге ожидается максимальное удорожание. В выбранной строке или столбце, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом, куда записывается максимально возможный объем перевозимого груза (-//-). Если на шаге существует несколько строк или столбцов с одинаковым удорожанием или несколько ячеек с одинаковым тарифом, то для заполнения выбирается любая из них. ПО с исчерпанными запасами и ПН с закрытыми потребностями постепенно выбывают из рассмотрения. Процесс продолжается до полного заполнения матрицы.
Вывод: метод Фогеля дает начальный опорный план наиболее близкий к оптимальному.
Пример решения задачи распределительным методом.
| Алгоритм решения транспортной задачи методом потенциалов |
Метод потенциалов представляет собой в сущности вариант симплекс метода, который специально приспособлен для решения транспортных задач.
ШАГ №1. Любым методом определяется начальный опорный план перевозок, в котором есть базисные и свободные клетки.
ШАГ №2. Определяются потенциалы (Uj, Vi) таким образом, чтобы в любой базисной клетке псевдостоимость была равна стоимости (псевдотариф был равен тарифу). 
Причем для расчета один из потенциалов можно назначить произвольно (например, положить равным нулю).
ШАГ №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 примера)
.