Теория двойственности в линейном программировании. Двойственный симплекс-метод (стр. 1 )

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

2.2. Основные положения теории двойственности

Теорема 1. Пусть- планы соответственно прямой и двойственной ЗЛП, тогда

(2.12)

Теорема 2, Пусть- планы соответственно прямой и двойственной ЗЛП и

, тогда- решения соответственно прямой и двойственной задач.

Теорема 3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойст­венная (прямая) ЗЛП имеет решение, причем

(2.13)

Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

Замечание. Если в одной из взаимно двойственных задач нару­шается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное. Это связано с тем, что при нарушении единственности оптимального решения исходной задачи в выражении линейной функции ее опти­мального решения через неосновные переменные отсутствует хотя бы одна из основных переменных.

С помощью теорем двойственности можно, решив симплекс­ным методом исходную задачу, найти оптимум и оптимальное решение двойственной задачи.

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

3. Целочисленные модели исследования операций

Целочисленное программирование ориентировано на решение задач математиче­ского программирования, в которых все или некоторые переменные должны принимать только целочисленные значения.

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

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

Пример 3,2, В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19,3 м площади. На приобретение оборудования предприятие может израсходовать 10 тыс. у. е., при этом оно может купить оборудование двух видов. Комплект оборудования 1 вида стоит 1000 у. е., а II вида - 3000 у. е. Приобре­тение одного комплекта оборудования 1 вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида - на 3 ед. Зная, что для установки одного комплекта оборудования 1 вида требуется 2 м2 площади, а оборудования II вида - 1площади, определить такой набор дополнительного оборудования, который дает воз можность максимально увеличить выпуск продукции.

Решение. Составим математическую модель задачи. Предположим, что предпри­ятие приобрететкомплектов оборудования 1 вида икомплектов оборудования II ви­да. Тогда переменныеидолжны удовлетворять следующим неравенствам:

(3.11)

Если предприятие приобретет указанное количество оборудования, то общее уве­личение выпуска продукции составит

(3.12)

По своему экономическому содержанию переменные х\ и Х2 могут принимать лишь целые неотрицательные значения, т. е.,

(3.13) (3.14)

Таким образом, задача (3.11)-(3.14) представляет собой задачу ЦЛП.

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

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

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

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

3.1. Метод ветвей и границ решения целочисленных задач линейного программирования (ЦЗЛП)

Рассмотрим задачу целочисленного линейного программирования (ЗЦЛП):

Найти вектор, максимизирующий линейную форму

(З.1)

и удовлетворяющий условиям:

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

В случае, когда целочисленные переменные являются булевыми, применяются комби­нированные методы. Булевы свойства переменных существенно упрощают поиск решения.

Рассматриваемый в данном разделе метод ветвей и границ решения задачи цело­численного программирования также опирается на решение задачи с ослабленными огра­ничениями. Метод ветвей и границ непосредственно применим как к полностью, так и к частично целочисленным задачам.

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

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

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

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

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

3.2. Задача коммивояжера

Имеется n городов, занумерованных числами 1,2,...,n. Для любой пары городов задано расстояние (время, путевые расходы)между ними. Поэтому в общем случае Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую после­довательность объезда городов, при которой длина маршрута была бы минимальной.

Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из n различных деталей. Здесь- время переналадки при переходе от обработки детали i к обработке детали j. Требуется найти после­довательность обработки деталей, минимизирующую общее время переналадок.

Для записи постановки задачи в терминах целочисленного линейного программи­рования определим булевы переменные следующим образом: , если коммивояжер переезжает и i-го города в j-й; , в противном случае. Тогда задача заключается в отыскании значений переменныхудовлетворяющих следующим соотношениям:

u(i) - специальные переменные, i=1,2,...m.

Для цикла, проходящего через все города, начинающегося и заканчивающегося в городе с номером 0, найдутся величины u(i), удовлетворяющие условиям (3.18).

Положим u(i)=p, если город с номером i будет посещен коммивояжером p-ым по порядку, p=1,2,...,m.

Пусть x(i, j) = 0. Тогда условия (3) примут вид: u(i) - u(j) ≤ m-1, что верно, так как p<m+1 и p>0.

Пусть x(i, j) = 1. Тогда, так как если u(i) = p, то u(j)=p+1 (это следует из того, что город с номером j будет следующим в маршруте коммивояжера после города с номером i).

Получим: u(i) - u(j) + m x(i, j) = p - (p+1) +m = m - 1, что и доказывает правомочность присутствия в модели ограничений (3).

4. Транспортная задача линейного программирования

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

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

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

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

Пример 4.1. Построить экономико-математическую модель следующей задачи. Имеются три поставщика и четыре потребителя. Мощ­ность поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары "поставщик — потре­битель" сведены в таблицу поставок (табл. 7.1).

В левом верхнем углу произвольной -клетки (i — номер

строки, j — номер столбца) стоит так называемый коэффициент затрат — затраты на перевозку единицы груза от i-го поставщика

Суммарные затраты F нa перевозку выражаются через коэффи­циенты затрат и поставки следующим образом:

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

На множестве неотрицательных решений системы ограничений (7.1) и (7.2) найти такое решение, при котором линейная функция (7.3) принимает минимальное значение.

Особенности экономико-математической модели транс­портной задачи:

  1) коэффициенты  целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);

  2) коэффициенты правых частей ограничений неотрицательны (запасы и потребности продукта);

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

  4) система ограничений есть система уравнений (т. е. транспорт­ная задача задана в канонической форме);

  5) каждая переменная входит в систему ограничений два раза: один раз — в систему (7.1) и один раз — в систему (7.2).

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

Постановка задачи. Некоторый однородный продукт, сосредоточенный у m по­ставщиковв количестве единиц соответственно, необходимо доставить п потребителямв количестве единиц. Известна стоимость cij перевозки еди­ницы груза от i-ro поставщика к j-му потребителю.

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

Обозначим черезколичество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю заплани­ровано к перевозке единиц груза, то стоимость перевозки составит

Стоимость всего плана выразится двойной суммой

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

а) все грузы должны быть перевезены, т. е.

б) все потребности должны быть удовлетворены, т. е.

Таким образом, vатематическая модель транспортной задачи имеет следующий вид: найти минимальное значение линейной функции

(4.1)

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

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

(4.5)

Транспортная задача, в которой суммарные запасы и потребности совпадают, т. е. выполняется условие (4.5), называется закрытой моделью; в противном случае - откры­той. Для открытой модели может быть два случая:

а) Суммарные запасы превышают суммарные потребности

б) Суммарные потребности превышают суммарные запасы

Линейная функция одинакова в обоих случаях, изменяется только вид системы ог­раничений.

Найти минимальное значение линейной функции

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

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводит­ся фиктивный потребитель, потребность которого

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

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

Транспортная задача имеетуравнений с mn неизвестными.

Матрицу, удовлетворяющую условиям (4,2)-(4.4), называют планом перевозок транспортной задачи (- перевозками).

Определение. План, при котором целевая функция (4.1) обращается в минимум, называется оптимальным.

Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, что­бы выполнялось условие баланса

План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов , где- векторы при переменных в матрице системы ограничений (4.2)-(4.4).

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

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

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

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

Метод северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.

Схема метода: 1) Полагают верхний левый элемент матрицы X

Возможны три случая:

а) еслии всю первую строку, начиная со второго элемента, запол­няют нулями.

б) если, а все оставшиеся элементы первого столбца заполняют нулями.

в) если, и все оставшиеся элементы первых столбца и строки заполняют нулями.

На этом один шаг метода заканчивается.

2) Пусть проделано k шагов,-й шаг состоит в следующем.

Определяют верхний левый элемент незаполненной части матрицы X. Пусть это элемент

Тогда полагаютгде

Если, то заполняют нулями-ю строку начиная с-го элемента.

В противном случае заполняют нулями оставшуюся часть-го столбца,

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

Схема метода: элементы матрицы С нумеруют, начиная от минимального в поряд­ке возрастания, а затем в этом же порядке заполняют матрицу

Пусть элементом с минимальным порядковым номером оказался элемент

Тогда полагают

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