ГЛАВА 4. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ : Математические методы исследования операций в экономике - П. Конюховский : Книги по праву, правоведение

ГЛАВА 4. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

1 2 3 4 5 6 7 8 9 10 11 12 
РЕКЛАМА
<

 

4.1. ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

 

4.1.1. Основные понятия. Многие экономические задачи ха­рактеризуются тем, что объемы управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые значения. Математическая формализация данных ситуа­ций приводит к моделям дискретного программирования. В об­щем виде задача дискретного программирования может быть сформулирована как задача нахождения максимума (или мини­мума) целевой функции f(x1, x2,...,xn) на множестве D, опреде­ляемом системой ограничений

 

 

где Ω — некоторое конечное, или счетное*, множество. Ус­ловие хΩ. называется условием дискретности. Особое место среди дискретных задач занимает целочисленная за­дача линейного программирования в канонической форме (ЦКЗЛП):

* Напомним, что примерами счетных множеств являются множества натуральных, целых и рациональных чисел.

 

 

где Z+ ={0; 1; 2; ...} — множество неотрицательных целых чи­сел.

Заметим, что в некоторых ситуациях требование «целочисленности» может быть наложено лишь на некоторые перемен­ные xj, что кардинально не меняет характера задачи.

 

 

Принципиальная сложность, вызываемая наличием условий целочисленности в системе ограничений оптимизационной задачи, состоит в том, что в значительном количестве случаев невозможно заменить дискретную задачу ее непрерывным ана­логом и, найдя соответствующее решение, округлить его ком­поненты до ближайших целых значений. Пример, показанный на рис. 4.1, демонстрирует, что при округлении оптимального плана х* обычной задачи ЛП до целых значений получается точ­ка ([х1*],[x2*]), не принадлежащая области допустимых планов задачи D. Условимся целую часть числа хj. обозначать [хj], а дробную — как {хj}. Тогда хj =[хj]+{хj}. Отдельно следует до­бавить, что если даже оптимальный план непрерывной задачи, округленный до целых значений компонент, окажется допусти­мым, то целевая функция может вести себя так, что ее значение будет на нем существенно «хуже», чем на оптимальном плане целочисленной задачи.

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

 

задачи с неделимостями;

экстремальные комбинаторные задачи;

задачи с разрывными целевыми функциями;

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

 

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

Классическим представителем задач данного класса стала так называемая задача о ранце. Ее фабула носит достаточно услов­ный характер и состоит в том, что солдат (или турист), собираю­щийся в поход, может нести груз весом не более W кг. Этот груз может состоять из набора предметов n типов, каждый предмет типа j весит wj кг и характеризуется некоторой «полезностью» uj, j 1: n. В рамках описанной ситуации вполне естественным представляется вопрос: сколько предметов каждого вида нужно положить в ранец, чтобы его суммарная полезность была макси­мальной? Если в качестве компонент плана хj. принять количе­ство укладываемых предметов типа j, то данную задачу можно записать:

 

 

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

4.1.3. Комбинаторные задачи. К данному классу относят­ся задачи оптимизации функции, заданной на конечном множе­стве, элементами которого служат выборки из n объектов.

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

 

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

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

 

элементы которой определяются следующим образом:

 


           1, если в маршруте предусмотрен переезд из пункта i в j,

 xi,j =   0, если в маршруте не предусмотрен переезд из пункта i в j,

 


причем по условию задачи xii =0,  i1: n.

Допустимыми планами служат связные маршруты, однознач­но определяемые упорядоченным набором посещаемых пунктов:

 

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

С учетом сказанного задача коммивояжера принимает вид целочисленной задачи линейного программирования:

 

 

Условия (4.8) и (4.9) с содержательной точки зрения означа­ют, что в каждый пункт можно въехать и выехать только один раз. Приведенная форма записи задачи коммивояжера (4.6)-(4.10) не является самой рациональной и предназначена только для того, чтобы подчеркнуть ее общность с другими задачами дискретного программирования. Существует и другая форма, которая более ярко отражает комбинаторный характер данной проблемы:

 

 

где D — множество перестановок чисел от 1 до n.

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

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

 

 

где сi,j — по-прежнему издержки на перевозку единицы груза;

di,j — фиксированная доплата за аренду транспортных средств.

При таких предпосылках целевая функция суммарных затрат на перевозку

 

 

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

 

то целевая функция примет вид

 

 

Действительно, если уi,j =0 , то переменные хi,j =0, а при уi,j =1 неравенства (4.15) становятся несущественными, поскольку они и так справедливы для любого опорного плана. Следова­тельно, задача (4.16) эквивалентна исходной задаче (4.13). В силу характера ограничений (4.14)-(4.15) задача (4.16) яв­ляется задачей частично-целочисленного программирования.

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

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

 

4.2. МЕТОД ГОМОРИ

 

4.2.1. Основные идеи и принципы*. Данный метод, кото­рый также носит название метода отсекающих плоскостей, предназначен для решения ЦЗЛП в канонической форме (4.2)-(4.3). Кратко представим его основные идеи.

* Впервые был предложен Р.Гомори в 1957-1958 гг.

 

Отправной точкой для решения задачи (4.2)-(4.3) является решение ее непрерывного аналога, т. е. КЗЛП без учета условий целочисленности. Если получаемый в результате оптимальный план х* содержит только целые компоненты, то мы автомати­чески получаем и соответствующее решение ЦЗЛП. В против­ном случае к системе ограничений задачи должно быть добавле­но такое ограничение, для которого:

 

найденный нецелочисленный оптимальный план х* не удов­летворяет вновь добавляемому ограничению;

любой допустимый целочисленный план непрерывной задачи (4.2)-(4.3) удовлетворяет вновь добавляемому ограниче­нию.

 

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

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

Теперь необходимо несколько более подробно остановиться на принципах формирования отсекающих ограничений. Вос­пользуемся системой обозначений, применявшихся при изло­жении вычислительных методов линейного программирования. Пусть β(q) — оптимальный базис, полученный на последней итерации решения нецелочисленной ЗЛП. Если обозначить через αi,j  и άi  коэффициенты матрицы задачи и вектора ограниче­ний в текущем базисе (A(β(q)) и b(β(q)))

 

 

то i-ое уравнение в системе ограничений задачи примет вид:

 

 

Так как план x(β(q)) является базисным, то в каждом уравнении все коэффициенты αi,j, соответствующие базисным столбцам (jN(β(q))), равны нулю за исключением некоторого αi,ji =1, на основе чего из (4.18) получаем:

 

 

Если представить каждый коэффициент αi,j в виде суммы це­лой и дробной частей αi,j =[αi,j]+{αi,j}, то получим

 

или

 

 

Из (4.21) следует, что если все хj, j1: n являются целыми, то целым будет и выражение

 

 

стоящее в левой части (4.21), и, стало быть, правая часть данно­го уравнения:

 

 

также должна быть целой. Предположим, что

 

 

тогда, в силу того, что 0 ≤ {άi} < 1, а {αi,j} ≥ 0, xj ≥ 0, должно вы­полняться неравенство

 

 

Однако неравенства (4.22) и (4.23) противоречат требуемой целочисленности правой части (4.21) xj(β(q)). Следовательно, для целочисленных решений должно выполняться условие, проти­воположное неравенству (4.22), или, что то же самое,

 

 

В то же время (4.24) не выполняется для любого нецелочислен­ного базисного плана х. Действительно, небазисные компонен­ты плана равны нулю: хj =0 , jN(β(q)),  и (4.24) приобретает вид {άi} ≤0 <=> {άi} =0, но это противоречит предположению о нецелочисленности плана х, т. к. в базисном плане хi = άi . Все сказанное позволяет утверждать, что ограничение (4.24) задает правильное отсечение.

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

 

 

где xn+1 ≥0 — фиктивная переменная, добавляемая для преоб­разования неравенства в строгое равенство. Ей соответствует нулевой коэффициент в целевой функции.

Данному преобразованию условий задачи будет соответ­ствовать преобразование симплекс-таблицы, показанное на рис. 4.2. На нем по соображениям обеспечения наглядности ис­пользованы обозначения (4.17) и предполагается, что текущий базис β(q) состоит из первых m столбцов.

 

 

Индекс i соответствует выбранной для формирования отсе­чения строке симплекс-таблицы, содержащей нецелочисленное значение bi(β(q)).

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

 

совместно с добавленным столбцом

 

 

образуют сопряженный (двойственно допустимый) базис для сформированной задачи, а (ά1, ..., άm, -{άi}) являются ненуле­выми компонентами соответствующего псевдоплана. Исходя из этого, приходим к тому, что для решения вновь получен­ной задачи может быть эффективно применена процедура двойственного симплекс-метода (см. параграф 1.7).

Поскольку в начальном псевдоплане имеется только одна от­рицательная компонента (-{άi}), то из базиса должен быть вы­веден соответствующий ей вектор аn+1 . Далее, следуя рекомен­дациям алгоритма двойственного симплекс-метода, находим оптимальный план. Если он не является целочисленным, то опи­санные действия итеративно повторяются.

Если в ходе решения дополнительная переменная хn+1 вновь становится базисной, ее значение оказывается безразличным для основных переменных. Поэтому строку и столбец, отвеча­ющие ей, вычеркивают. С геометрической точки зрения это можно обосновать так: если псевдоплан оказывается внутри полупространства хn+1 ≥0, то дополнительное ограничение, оп­ределяемое гиперплоскостью хn+1=0, становится несущест­венным и опускается.

4.2.2. Описание алгоритма. Приведем обобщенную схе­му алгоритма Гомори. Структурно он делится на так называе­мые большие итерации. Каждая большая итерация содержит этапы:

1. Решение «текущей» задачи методами линейного програм­мирования (малые итерации). На первой итерации в качестве «текущей» задачи выступает нецелочисленный аналог исходной ЦЗЛП.

2. Определение первой нецелочисленной компоненты в оп­тимальном плане, полученном на этапе 1. Если все компоненты являются целочисленными, то алгоритм завершается.

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

Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнитель­ные ограничения (правильные отсечения) и переходить от те­кущего псевдоплана к новому оптимальному плану.

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

В качестве существенного замечания по поводу метода Гомори следует добавить, что при его практической реализации на ЭВМ следует считаться с ошибками округления, т, к. в усло­виях машинной арифметики практически ни один план не будет целочисленным. Кроме того, накапливающиеся погрешности могут внести возмущения в алгоритм и «увести» от оптимально­го целочисленного плана.

4.2.3. Пример решения ЦЗЛП методом Гомори. Рас­смотрим особенности применения метода Гомори на конкрет­ном примере. Пусть дана задача со следующими условиями:

 

 

Итерация 1. Используя обычный симплекс-алгоритм, реша­ем непрерывный аналог исходной задачи, в котором игнориру­ются условия целочисленности (4.28). В качестве исходного базиса можно взять первый и второй столбцы. На его основе заполняется таблица T(1,1) (первый индекс в обозначении табли­цы соответствует «большой» итерации, а второй — «малой»).

 

 

Как видно из строки оценок, данный базис является опти­мальным, однако соответствующий ему план х ={11/5,17/5, 0) не является целочисленным, поэтому выбираем из таблицы T(1,1) строку, содержащую первый нецелый элемент, и согласно формуле (4.25) строим отсекающее ограничение:

 

 

после чего переходим к следующей «большой» итерации.

Итерация 2. С учетом сформированного отсекающего ог­раничения заполняем симплекс-таблицу T(2,1).

 

 

В соответствии с алгоритмом двойственного симплекс-мето­да переходим к следующему базису N(β(2,2))={1, 2, 3}.

 

 

План, достигнутый в таблице T(2,2), является не только опти­мальным (b(β(2,2))>0), но и полностью состоит из целочислен­ных компонент, т. е. решение задачи найдено: х* = (1, 2, 1) и f(x)=7.

 

4.3. МЕТОД ВЕТВЕЙ И ГРАНИЦ

 

4.3.1. Общая схема метода «ветвей и границ». Другим широко применяемым для решения задач дискретного програм­мирования методом является метод ветвей и границ. Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его «второе рождение» произошло в 1963 г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере [33].

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

Пусть стоит задача:

 

 

где D — конечное множество.

Алгоритм является итеративным, и на каждой итерации про­исходит работа с некоторым подмножеством множества D. На­зовем это подмножество текущим и будем обозначать его как D(q), где q — индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D(1)=D), и для него некоторым способом вычисляется значе­ние верхней оценки для целевой функции max f(x) ≤ ξ( D(1)). Стандартная итерация алгоритма состоит из следующих этапов:

1°. Если можно указать план x(q)D(q), для которого f(x(q))≤ξ( D(q)), то x(q)=х* — решение задачи (4.29).

2°. Если такой план не найден, то область определения D(q) некоторым образом разбивается на подмножества D1(q), D2(q), ..., Dlq(q), удовлетворяющие условиям:

 

 

Для каждого подмножества находятся оценки сверху (вер­хние границы) для целевой функции ξD1(q), ξD2(q), ..., ξDl1(q), уточняющие ранее полученную оценку ξD(q), то есть ξDi(q) ≤ ξD(q), i1:lq. Возможно одно из двух:

2.1. Если существует такой план х(q), что

 

 

то этот план оптимальный.

 

 

2.2. Если такой план не найден, то выбирается одно из мно­жеств Di(q), i1:lq (как правило, имеющее наибольшую оценку

 

 

Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются как D1(q+1), D2(q+1),..., Dl(q+1)(q+1), после чего процесс повторяется.

Схема дробления множества D представлена на рис. 4.3 в виде графа. Существуют и более сложные системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.

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

4.3.2. Решение ЦЗЛП методом ветвей и границ. Рас­смотрим применение алгоритма метода ветвей и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, через D(q) обозначается подмножество множества допустимых планов за­дачи. Перед началом первой итерации (q = 1) в качестве теку­щего множества берется все множество D (D(1) = D), после чего решается стандартная задача линейного программирования (D(1), f). Нетрудно заметить, что она является непрерывным аналогом

 

 

исходной задачи (4.2)-(4.3). Если найденный оптималь­ный план (1) содержит только целочисленные компоненты, то он является и оптимальным планом для (4.2)-(4.3):  (1) = x*. В противном случае значение f( (1)) становится оценкой (верх­ней границей) значения целевой функции на множестве D(1), и мы переходим к выполнению стандартной итерации алгоритма. Опишем входящие в нее этапы.

1) Выбирается некоторая нецелочисленная компонента пла­на k(q). Поскольку в оптимальном плане она должна быть це­лой, то можно наложить ограничения xk ≤ [k(q)] и xk ≥ [k(q)]+1. Таким образом, D(q)  разбивается на подмножества

 

 

Графическая интерпретация такого разбиения множества D(q) приведена на рис. 4.4.

2) Решаются задачи линейного программирования

 

 

Соответствующие максимальные значения целевой функции принимаются как ее оценки на этих множествах:

 

 

Если оптимальный план  для одной из решенных задач удов­летворяет условию

 

 

и содержит только целые компоненты, то, значит, найдено ре­шение основной задачи (4.2)-(4.3). В противном случае среди всех концевых подмножеств, полученных как на предыду­щих (Di(q)), так и на текущем (D1(q), D2(q)) этапе, выбирается об­ласть с наибольшей оценкой ξ(Di(q)). Она становится текущим рассматриваемым подмножеством (D(q+1)). Далее производится перенумерация концевых множеств и вычислительный процесс итеративно повторяется.

При решении задач (D1(q), f) и (D2(q), f) можно воспользовать­ся результатами решения предыдущей задачи (D(q), f). Рас­смотрим вариант организации вычислительного процесса на примере задачи (1(q), f) (для (2(q), f) он выглядит аналогично с точностью до знаков неравенств).

Предположим, что на последнем шаге решения задачи (D(q), f) был получен оптимальный базис β. Без ограничения общности можно считать, что он состоит из первых m столбцов матрицы задачи. Данное предположение делается исключитель­но для обеспечения наглядности дальнейшего изложения и оче­видно, что его выполнения можно всегда добиться за счет про­стой перенумерации векторов аj. По аналогии с предыдущим параграфом введем обозначения для элементов матрицы задачи (D(q), f) и ее вектора ограничений относительно базиса :

 

 

Тогда система ограничений задачи (D(q), f) может быть пред­ставлена как

 

 

а получаемая на ее основе система ограничений задачи (1(q), f) как

 

 

или

 

 

где хn+1 ≥ 0 — фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции, добавляемая для пре­образования неравенства в строгое равенство.

Очевидно, что 1≤k≤m, т. к. небазисные компоненты опти­мального плана (m+1≤j≤n) равны нулю, т. е. являются заведо­мо целочисленными. Тогда с учетом сделанных предположений о виде базиса  можно записать:

 

 

Как видно из (4.39), в k-м столбце имеется всего два отлич­ных от нуля элемента: в k-й и (m+1)-й строках. Если вычесть из (m+1)-го уравнения k-e, то, учитывая, что [άk] – άk =-{άk}, по­лучим эквивалентную систему:

 

 

Проведенные преобразования системы ограничений D1(q) по­зволили явно выделить сопряженный базис, образуемый столб­цами с номерами 1,..., m, n+1, и соответствующий ему псевдо­план (ά1, ..., άm, 0,...., 0, -{άk}), т.е. для решения задачи (D1(q), f) может быть применен алгоритм двойственного симплекс-мето­да. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5.

 

 

Для случая задачи (D2(q), f) преобразование симплекс-табли­цы, получаемое на базе аналогичных рассуждений, приведено на рис. 4.6.

 

 

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

Подчеркнем, что приведенная реализация метода ветвей и границ является одной из многих. Помимо нее, например, очень популярна версия метода решения задачи коммивояжера, в которой для ветвления и построения оценок используют специфические свойства данной модели. При желании о ней мож­но прочесть в [1, 14].

 

КЛЮЧЕВЫЕ ПОНЯТИЯ

 

Задачи с неделимостями.

Экстремальные комбинаторные задачи.

Задачи с разрывными целевыми функциями.

Правильное отсечение.

Метод Гомори.

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

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

 

4.1. Какие основные проблемы возникают при решении дис­кретных задач?

4.2. Сформулируйте задачу о ранце.

4.3. Какие экономико-математические модели могут быть све­дены к задаче о коммивояжере?

4.4. Приведите пример моделей с разрывными целевыми функ­циями.

4.5. Какой принцип используется для построения правильно­го отсечения в методе Гомори?

4.6. Перечислите основные этапы, входящие в «большую» итерацию метода Гомори.

4.7. Какую роль играет алгоритм двойственного симплекс-ме­тода при решении целочисленной

       линейной задачи мето­дом Гомори?

4.8. Перечислите принципиальные идеи, лежащие в основе ме­тодов ветвей и границ.

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

       ветвей и границ?

4.10. Опишите схему решения целочисленной задачи линейно­го программирования методом ветвей и

         границ.

4.11. За счет каких преобразований удается построить сопря­женный базис при добавлении

         отсекающего ограничения?