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

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

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

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

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

Обозначим далее через {а} дробную часть числа а. Дробная часть числа а есть разность между данным числом и его целой частью:

Для чисел, рассмотренных выше, найдем дробные части:

Дробная часть числа всегда положительна.

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

где — базисная неизвестная; — свободная неизвестная; - нецелочисленное значение базисной переменной. Тогда условие отсечения будет иметь вид

Здесь— дробные части соответствующих чисел.

Рассмотрим применение метода отсечений на конкретном примере.

Пример.

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

БП

СЧ

CO

20

2

3

1

20/3

40

9

7

10

40/7

F

0

-2

-4

-3

БП

СЧ

20/7

-13/7

-3/7

-23/7

40/7

9/7

1/7

10/7

F

160/7

22/7

4/7

19/7

В полученном оптимальном решении задачи имеем нецелочисленное значение неизвестной х2 . Дополнительное ограничение формируем по элементам второй строки:

БП

СЧ

CO

20/7

-13/7

-3/7

-23/7

-

40/7

9/7

1/7

10/7

40

-5/7

-2/7

-1/7

-3/7

5

F

160/7

22/7

4/7

19/7

БП

СЧ

5

5

5

F

20

2

4

1

Ответ:

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

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

Если, например, дополнительные ограничения строить по переменной , то первое ограничение будет а второе этим мы исключаем из ОДР исходной задачи промежуток с дробными значениями неизвестной . Этот промежуток разбивает ОДР на две части

ОДР

ОДЗ1 ОДЗ2

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

Поскольку множество всех решений задачи ЦЛО конечно, то после конечного числа разбиений исходной задачи на подзадачи оптимальное решение будет найдено.

Проиллюстрируем применение метода ветвей и границ на следующем примере.

Пример. Найти максимум функции

при ограничениях

Решение. Для наглядности решение осуществим графическим методом. ОДР задачи является многоугольник ОАВС (рис. 1). В точке В находится максимальное значение функции: при и

Рис. 1

Поскольку значения неизвестных дробные, то разобьём по неизвестной ОДР задачи на две части. Одна будет содержать множество точек, у которых , а вторая — у которых . В результате получаем две новые задачи линейной оптимизации: №2 и № 3 (исходная задача имеет № 1).

Задача № 2

Задача № 3

Области допустимых решений задач представлены на рис. 2.

Из рис. 2 видно, что ни одна целочисленная точка исходной ОДР не потеряна. ОДР задачи № 2 является многоугольник OADEC. В точке Е с координатами и функция достигает максимального значения

Рис. 2

Решение задачи № 2 не является целочисленным. Что касается задачи № 3, то ее ОДР пустая. Ограничения этой задачи противоречивы, и она не имеет решения.

Продолжая решение, разобьем ОДР задачи № 2 на два подмножества по неизвестной . В результате получим две новые задачи № 4 и № 5 с соответствующими дополнительными ограничениями : и .

Задача № 4

Задача № 5

ОДР этих задач представлены на рис. 3.

ОДР задачи № 4 является многоугольник OADFK. Максимальное значение функции достигается в точке F с координатами и . . Таким образом, получено целочисленное решение задачи № 4.

ОДР задачи № 5 является треугольник LMC. Максимальное значение функция достигает в точке L с координатами ; ;

Так как значение функции целочисленного решения задачи № 4 меньше , то дальнейшему разбиению на две задачи № 6 и № 7 подлежит задача № 5 по нецелочисленной неизвестной . Не проводя дополнительных построений, отметим, что ОДР задачи № 6 с дополнительным ограничением не существует, а значение функции в оптимальном целочисленном решении задачи № 7 с дополнительным ограничением равно 7, что меньше . Таким образом, целочисленное решение исходной задачи следующее: , , .

Рис. 3

Двойственность в линейной оптимизации

Постановка и правила построения двойственной задачи

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

Пусть дана общая задача линейной оптимизации (исходная задача):

произвольного знака при .

Двойственная к ней задача имеет вид:

произвольного знака при .

Двойственная задача строится по следующим правилам:

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

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

3) каждой переменной двойственной задачи соответствует i-е ограничение исходной задачи, и, наоборот, каждой переменной прямой задачи соответствует j-e ограничение двойственной задачи;

4) матрица из коэффициентов при неизвестных двойственной задачи образуется транспонированием матрицы, составленной из коэффициентов при неизвестных системы ограничений исходной задачи;

5) если на j-ю переменную исходной задачи наложено условие неотрицательности, то
j-e ограничение двойственной задачи будет неравенством, в противном случае j-e ограничение будет равенством; аналогично связаны между собой ограничения исходной задачи и переменные двойственной.

Дадим экономическую интерпретацию пары двойственных задач.

Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами которые могут использоваться для выпуска п видов продукции. Пусть также известны стоимость единицы j-го вида продукции и норма потребления i-го ресурса на производство единицы j-й продукции — аij.

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

При этом расход ресурсов не должен превышать их наличия:

Все неизвестные по своему экономическому смыслу неотрицательны:

По исходным данным сформулируем другую экономическую задачу (двойственную).

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

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

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

Пример. Построить двойственную задачу к следующей задаче, заданной в общей форме:

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

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

В соответствии с указанными выше правилами запишем двойственную задачу:

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

Транспортная задача

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

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

Математически транспортная задача по критерию стоимости формируется следующим образом. Имеется п потребителей и т поставщиков однородного груза. Мощность i-гo поставщика (i = 1,m) обозначим аi, спрос j-го потребителя (j = 1,п) bj. Затраты на перевозку одной тонны груза от i-гo поставщика до j-го потребителя обозначим сij. Размер поставки продукции поставщиком i потребителю j обозначим хij; общую сумму затрат на перевозку груза обозначим через F.

Запишем математическую модель задачи:

1) объем поставок i-гo поставщика должен равняться количеству имеющегося у него груза:

2) объем поставок j-му потребителю должен быть равен его спросу:

3) запас груза у поставщиков должен равняться суммарному спросу потребителей:

4) размер поставок должен выражаться неотрицательным числом:

5) общая сумма затрат на перевозку груза должна быть минимальной:

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

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

Построения начального опорного плана

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

Способ "северо-западного угла". Первой загружается клетка (1; 1). Если закрывается строка, то следующей загружается клетка (2; 1); если же закрывается столбец, то следующей загружается клетка (1; 2). Итак, каждый раз загружается клетка, соседняя либо по строке, либо по столбцу (в зависимости от конкретных данных задачи). Последней будет загружена клетка (т; п). В результате загруженные клетки расположатся вдоль диагонали (1; 1) — (т; п), поэтому способ "северо-западного угла" называют еще диагональным способом.

Существенным недостатком способа "северо-западного угла" является игнорирование при загрузке клеток тарифов , поэтому построенный опорный план обычно оказывается весьма далеким от оптимального.

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

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

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

1. Находится первый опорный план по одному из рассмотренных методов.

2. Проверяется найденный опорный план на оптимальность, для чего:

2.1. Находятся потенциалы поставщиков и потребителей по формуле .

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

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

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

2.4. Осуществляется перераспределение груза по циклу на величину Q. В результате выполнения этого пункта будет получен новый опорный план, который проверяется на оптимальность, т. е. производится переход к пункту 2.1 алгоритма.

Дополнительные условия в транспортных задачах

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

Рассмотрим наиболее часто встречающиеся случаи.

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

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

Иногда приходится учитывать ограничения по пропускной способности некоторых маршрутов. Если, например, по маршруту i-j можно провезти не более d единиц груза, то j-й столбец матрицы перевозок разбивается на два: j’-й и j’’. В первом спрос принимается равным разности между действительным спросом bj и ограничением d, во втором — равным ограничению d. Тарифы в обоих столбцах одинаковы и равны данным, но в первом в клетке, соответствующей ограничению, вместо истинного тарифа ставится искусственно завышенный тариф М (клетка блокируется). Затем задача решается обычным способом.

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

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

Транспортная задача в сетевой постановке

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

Рис.1

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

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

Рис.2

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

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

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5