Обзор задач дискретного программирования - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Обзор задач дискретного программирования

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


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

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Пермский Национальный Исследовательский Политехнический Университет
«Обзор задач дискретного программирования»
Глава 1. Обзор и методы решений задач дискретного программирования
1.1 Предмет, постановка и особенности задач дискретного программирования
1.2 Модели дискретного программирования
1.2.2 Экстремальные комбинаторные задачи
1.2.3 Задачи с разрывными целевыми функциями
1.3 Методы решения задач дискретного программирования
Глава 2.Примеры решений задач дискретного программирования
2.1 Пример решения задачи методом Гомори
2.2 Пример решения задачи методом ветвей и границ
Дискретное программирование сформировалось как самостоятельная и важная часть математического программирования в конце 60-х годов. В терминах дискретного программирования формулируются многие важные задачи экономики, управления, планирования, военного дела, биологии и т. п. Кроме того, к задачам дискретного программирования удается свести ряд экстремальных комбинаторных задач. По мнению автора, дискретное программирование является интересным и перспективным разделом математического программирования. Именно поэтому объектом настоящего исследования являются задачи дискретного программирования. Встают закономерные вопросы, в чем особенность данных задач, в чем прикладное значение их и какие существуют методы решения в дискретном программировании. Чтобы ответить на поставленные вопросы, в данной работе решены следующие задачи: во-первых, предлагаются формулировка, особенности дискретных задач. Во-вторых, приводится их классификация. В- третьих, рассматриваются методы решения дискретных задач.
Настоящая работа опирается прежде всего на работы авторитетных ученых, работающих в данной область (Сигал И. Х., Иванова А. П., Дроздов Н. Д., Корбут А. А., Фанкельштейн Ю. Ю.). В процессе работы привлекались данные сайтов в сети Интернет. Данная работа состоит из введения , 2 глав, заключения и списка литературы. В 1 главе приводятся теоритические данные, а именно, особенности задач дискретного программирования, классификация и методы решения. 2 глава - практическая, в ней приведены примеры задач и их решение.
Глава 1. Обзор и методы решений задач дискретного программирования
1.1 Предмет, постановка и особенности задач дискретного программирования
Дискретное программирование - раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Таким образом, здесь используется модель общей задачи математического программирования с дополнительным ограничением: x1, x2, ..., xn -- целочисленны. Итак, под задачей дискретного программирования понимается задача математического программирования F(x°)= min F(x), x Є G, множество допустимых решений которой конечно, т. е. 0?¦G¦=N< ?, где ¦G¦-число элементов множества G. Рассмотрим задачу линейного программирования.
Если n1 0 и вес aj > О, j = 1,2,...,n. Имеется ранец (рюкзак), грузоподъемность которого есть R, при этом ?aj >R , т.е. все предметы в ранец положить невозможно. Необходимо положить в ранец набор предметов с максимальной суммарной ценностью. Введем п переменных:
После введения этих переменных суммарная ценность и грузоподъемность соответственно имеют вид
Поэтому задача об одномерном ранце имеет вид
Естественно предположить, что cj > 0, 0 < aj < R, j = 1,2,... , n. Множество допустимых решений этой задачи -- это множество n-мерных булевых векторов х = {х1, х2,..., хп), удовлетворяющих условию (2). Вместе с задачей (1)-( 3) будем рассматривать задачу линейного программирования, в которой вместо условий (3) вводятся условия
Задача о многомерном ранце. Эта задача имеет вид
gi(x1,x2,...,xn) = ?bi j , i = 1,2,...,m, (5)
Предполагаем, что cj > 0, 0 < aij ? bi , i = 1, 2,..., m, j = 1, 2,..., п. В этой задаче каждый предмет имеет т свойств (кроме ценности). Эти свойства описываются количественно с помощью элементов столбца с номером j матрицы А = (aij)mxn. Множество допустимых решений этой задачи -- это множество булевых векторов х = (x1,x2,...,xn), удовлетворяющих условиям (5). Вместе с задачей (4)-(6) будем рассматривать задачу линейного программирования, в которой вместо условий (6) вводятся условия
Экономическая интерпретация задачи о ранцах. Пусть имеется п проектов, и для их реализации задан вектор ресурсов BT = (b1,b2,...,bm), bi > 0. Обозначим через aij > 0 количество единиц ресурса типа i, необходимое для реализации проекта с номером j, при этом для любого ресурса Bs выполнено условие > bs, т.е. реализация всех проектов невозможна. Пусть Cj > 0, j = 1, 2,..., п -- прибыль, полученная при реализации проекта j. Требуется выбрать для реализации набор проектов с максимальной суммарной прибылью. Введем п булевых переменных:
Получим задачу о многомерном ранце (4)-(6).
В данных задачах необходимо найти  экстремум некоторой целевой функции, заданной на конечном множестве, элементами которого служат перестановки из n символов. Найти такую перестановку  из чисел 1, 2, …, n, при которой достигается минимум  по всем перестановкам .
Каждая такая перестановка может быть представлена точкой в n2-мерном пространстве или в виде матрицы .
Одной из наиболее простых задач этого класса является известная задача о назначениях.
Задача о назначениях - это распределительная задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи.
В некоторых случаях, например, когда cij - это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ. В этом случае ЦФ L(X) заменяют на L1(X) = - L(X) и решают задачу с ЦФ L1(X) > min, что равносильно решению задачи с ЦФ L(X) > max.
Эта задача относится к классу экстремальных комбинаторных задач на графах. Рассмотрим типичную задачу о покрытии. Дан граф G. Требуется найти его минимальное покрытие, т.е. такую минимальную совокупность ребер, чтобы любая вершина графа была инцидентна некоторому ребру, входящему в покрытие.
Обозначим вершины графа i, i =1, 2, …, m, а ребра -- j, j =1, 2, …, n... Граф характеризуется своей матрицей инциденций вершин и ребер , где
Введем множество переменных {xj}, таких, что
Тогда нахождение минимального покрытия эквивалентно следующей задаче:
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения: 
маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение; в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды. 
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице как бы вычеркивается диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Ci j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i- го города в j-й.
Xi j - матрица переходов с компонентами:
Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,
Xi j = 0, если не совершает перехода,
Ui - Uj + N Ч Xij ? N-1, i, j = 1..N, i j. (15)
1.2.3 Задачи с разрывными целевыми функциями
Многие экономические системы характеризуются наличием так называемых постоянных затрат, которые должны быть произведены независимо от объема производства. Учет в моделях этих и подобных факторов приводит к появлению в них целевых функций, не обладающих свойством непрерывности. В качестве примера может быть приведена транспортная задача с фиксированными доплатами. Она отличается от транспортной задачи в матричной постановке, тем, что в ней затраты по перевозке груза из i-го пункта производства в j-й пункт потребления определяются как
где сi,j --издержки на перевозку единицы груза;
di,j -- фиксированная доплата за аренду транспортных средств. ai -- объем производства в пункте производства i ; bj -- объем потребления в пункте потребления j. Обозначим через xij объемы перевозок из пункта i в пункт j.
При таких предпосылках целевая функция суммарных затрат на перевозку
содержит «скачкообразные» разрывы, что существенно затрудняет ее минимизацию, поэтому стандартный метод решения основан на следующем преобразовании. Если ввести вспомогательные переменные уi,j, такие, что
М ij = min (ai ,bj), i = 1,2,...,m; j = 1,2,...n.
при дополнительном условии i = 1,2,...,m; j = 1,2,...n.
Действительно, если уi,j =0 , то переменные хi,j =0, а при уi,j =1 неравенства (18) становятся несущественными, поскольку они и так справедливы для любого опорного плана. Следовательно, задача (19) эквивалентна исходной задаче (17). Задача (19) является задачей частично-целочисленного программирования.
Перечисленные примеры далеко не исчерпывают всего многообразия задач дискретного программирования. Далее мы рассмотрим методы решения дискретных задач.
1.3 Методы решения задач дискретного программирования.
Методы решения задач дискретного программирования можно разделить на следующие классы:
Рассмотрим каждый класс в отдельности.
Алгоритмы методов отсечения разработаны для решения полностью или частично целочисленных и дискретных задач линейного программирования.
Общая схема методов отсечения заключается в переходе от решения задачи целочисленного (дискретного) линейного программирования к решению последовательности задач линейного программирования . Первая задача последовательности получается из исходной снятием требования целочисленности (дискретности).
Каждая последующая k-ая задача получается из предыдущей (k-1)-ой
путем добавления к условиям, определяющим область допустимых
решений (k-1)-ой задачи, еще одного ограничения, называемого
После решения каждой k-ой задачи ЛП (k = 0,1,2, . . .) проверятся
удовлетворяет ли полученное оптимальное решение условиям исходной
задачи. При положительном ответе итерационный процесс решения
задач из последовательности прекращается - полученное оптимальное решение задачи ЛП является и решением исходной задачи.
Решение каждой k-ой задачи ЛП называется k-ой большой итерацией.
Доказывается, что при выполнении определенных условий решение
исходной задачи будет получено через конечное число итераций. Если
задачи ЛП не имеют решения, не имеет решения и исходная задача.
Основным понятием метода является термин правильное отсечение:
Правильные отсечения - отсечение (дополнительное ограничение), которое удовлетворяют следующим требованиям:
2. отсекает от области допустимых решений ту ее часть, которая содержит оптимальное решение задачи ЛП, не удовлетворяющее требованиям исходной задачи;
3. в отсекаемой области не должно содержаться ни одной точки, принадлежащей области допустимых решений исходной задачи. (является «правильным»).
Общая формула построения правильного отсечения для всех алгоритмов запишется в следующем виде:
где xj - небазисные переменные оптимального решения k-ой задачи ЛП, г0 , гj - определяются по коэффициентам разложения базисной переменной, не удовлетворяющей требованиям целочисленности (дискретности) исходной задачи по небазисным переменным в последней симплекс-таблице k-ой задачи ЛП (строка симплекс-таблицы с найденным оптимальным значением задачи ЛП).
1). 1-ый алгоритм Гомори решения целочисленной задачи ЛП.
2). 2-ой алгоритм Гомори решения частично целочисленной задачи ЛП.
3). Алгоритм Дальтона-Ллевилина решения дискретной задачи ЛП.
Скажем пару слов о каждом приведённом алгоритме.
1-ый алгоритм Гомори решения целочисленной задачи ЛП.
Что бы решать задачу методом Гомори № 1 необходимо, чтобы все компоненты плана были целочисленными. Другими словами, даже к искусственным переменным предъявляется требование целочисленности.
1.Решим исходную задачу (без условия целочисленности) Симплекс-методом. Если все базисные компоненты оптимального плана решаемой задачи целые, то найденное решение есть оптимальное решение исходной задачи. Если некоторая компонента -
2.Строим правильное отсечение. Гомори предложено делать каждый раз дополнительное ограничение для нецелой переменной с наибольшей дробной частью. Итак, задача с отброшенным условием целочисленности решена. Рассмотрим i-ю строку оптимальной симплексной таблицы, которой соответствует нецелое решение в i базисной переменной xi .Пусть R - множество индексов j, которые соответствуют небазисным переменным. Тогда переменная xi может быть выражена через небазисные переменные xj:
Обозначим наибольшую целую часть числа a, его не превосходящую, через [a], ( a?[a]), а дробную положительную часть - через {a} Очевидно a = [a] + {a}. Например, если a=4,7 то [a] = 4, {a} = 0,7.
Выразим базисную переменную xi в виде суммы целой и дробной частей. 
Выражение в левых круглых скобках целое число, и чтобы xj было целым, необходимо, чтобы выражение в правых круглых скобках тоже было целым. Когда выражение Li= будет целым? Так как 0?{вi}?1, а ?0, то Li будет целым числом, если . 
Задача не будет иметь полностью целочисленного решения, если встретится в симплекс-таблице уравнение такое, что вi дробное число, а dij -целые.
3.Добавляем полученное дополнительное условие к задаче из п.1.Так как оптимальное решение задачи, решенной в п.1, определяло одну из вершин многогранника условий, то оно может быть выбрано в качестве первоначального опорного решения для вновь полученной задачи.Решаем полученную задачу С-методом.
Теорема (о конечности первого алгоритма Гомори)
Пусть множество оптимальных планов задачи, полученной из исходной отбрасыванием условий целочисленности, ограничено, и выполняются следующие условия:
1) cj- целые коэффициенты целевой функции F, строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;
2) справедливо одно из двух утверждений: либо целевая функция ограничена снизу, либо исходная задача имеет хотя бы один план.
Тогда первый алгоритм Гомори требует конечного числа больших итераций.
Пример применение первого алгоритма Гомори будет рассмотрено в главе 2.
Алгоритм Дальтона-Ллевилина решения дискретной задачи ЛП.
В задачах, решаемых алгоритмом Дальтона-Ллевилина, область допустимых значений задается следующим образом
x Є Aj (A j1,Aj2 ,...,Ajmj ), j =1,2,…,n1, n1 ? n .
Полагаем, что коэффициенты Aj проранжированы, т.е. Аj1 < Аj2 < …< Аjmj.
Если x не удовлетворяет требованиям исходной задачи и
Aiv < xi0< Aiv+1 тогда, используя i-ю строку симплекс-таблицы, запишем правильное ограничение в виде
г ij= (-xij)*( xi0 - Aiv)/( Aiv+1 -xi0) ,если xij? 0,
1.) Для того, чтобы при вводе правильных отсечений ограничить размеры симплекс-таблицы, Гомори предложил после решения очередной задачи ЛП вычеркивать из таблицы переменную, по которой построено правильное ограничение.
2.) Известно, что с увеличением размерности задачи эффективность методов отсечения значительно снижается. Решение может быть не получено, в частности, из-за недостаточной точности вычисления коэффициентов.
Основная идея методов этого класса заключается в использовании конечности множества допустимых решений и замене полного их перебора сокращенным (направленным перебором). Если каким-либо образом удается показать, что подмножество G' С G не может содержать оптимальных решений, то в дальнейшем задача решается на множестве хG\G'. Таким образом, главную роль в сокращении перебора играют оценка и отбрасывание подмножеств, заведомо не содержащих оптимальных решений. Эта идея реализуется путем последовательного разбиения множества всех допустимых решений на подмножества. При этом среди подмножеств, последовательно порождаемых на каждом шаге процесса, могут обнаружиться как подмножества, не содержащие допустимых решений, так и подмножества, не содержащие оптимальных решений. Отбрасывание таких подмножеств позволяет заменить полный перебор частичным и тем самым делает реализуемым вычислительный процесс.
Таким образом, комбинаторные методы основаны на двух элементах:
-- последовательное разбиение на подмножества;
-- оценивание получаемых подмножеств.
Подмножество, которое не может быть отсеяно, подвергается дальнейшему разбиению. Комбинаторные методы различаются способом разбиения и способом оценивания, эти способы обычно связаны со спецификой решаемых классов задач. Правила, в соответствии с которыми производится отсев подмножеств, заведомо не содержащих оптимальных решений, называются правилами отсева.
Среди комбинаторных методов выделяют:
-- метод последовательного анализа вариантов;
-- методы, основанные на последовательностных схемах;
-- метод динамического программирования;
-- аппроксимационно-комбинаторный метод;
Остановимся подробнее на самом распространённом из них, на методе ветвей и границ.
Суть метода заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.
Алгоритм действия метода ветвей и границ
Первоначально находим, к примеру, симплекс-методом оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax = F(X0).
Если же среди компонент плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи.
Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла xi в плане X0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу Ci0 , либо больше или равно ближайшему большему целому числу Ci0 +1. Определяя эти числа, находим симплекс-методом решение двух задач линейного программирования:
Найдем решение задач линейного программирования (20) и (21). Очевидно, здесь возможен один из следующих четырех случаев:
1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (20) и (21).
3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой.
3.1. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение.
3.2. Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (20) и (21).
4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (20) и (21).
Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х0 исходной задачи, а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (20) и (21). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.
Итак, процесс нахождения решения задачи целочисленного программирования методом ветвей и границ включает следующие основные этапы:
1. Находят решение задачи линейного программирования .
2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи является дробным числом.
3. Находят решение задач (20) и (21), которые получаются из задачи в результате присоединения дополнительных ограничений.
4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (20) и (21), и находят их решение.
Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.
Пример решения задачи данным методом разберем в главе 2.
Отмечаются два основных стимула к развитию приближенных
1) Возможности точных методов ограничены и не удовлетворяют потребностям практики. Вычислительная реализация комбинаторных алгоритмов зачастую весьма трудоемка и является препятствием применения методов для решения практических задач.
2) Потребности практики часто обеспечиваются приближенными решениями, если адекватность модели реальному процессу не достаточна, или, когда исходная информация не точна.
Можно отметить два подхода к повышению вычислительной эффективности комбинаторных алгоритмов:
- локальный, под которым понимаются любые приемы расширения возможности решения конкретной задачи;
- глобальный, заключающийся в переводе определенных классов задач на более низкий уровень сложности.
Возможные классификации приближенных методов
2) Специфические (эвристические) методы.
1) Детерминированные методы (например, линейная аппроксимация, локальная оптимизация).
2) Методы случайного поиска (неуправляемый поиск, управляемый поиск).
3) Методы решения задач специальной структуры (транспортная задача с фиксированными доплатами).
4) Статистические эффективные методы.
Глава 2. Примеры решений задач дискретного программирования
2.1 Пример решения задачи методом Гомори.
Решим задачу без учета целочисленности.
Определим минимальное значение целевой функции F(X) = - 5x1 - 4x2 при следующих условиях.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
Решим систему уравнений относительно базисных переменных:
Полагая, что свободные переменные равны 0, получим первый опорный план:
Переходим к основному алгоритму симплекс-метода.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Конец: индексная строка не содержит положительных элементов - найден оптимальный план
Оптимальный план можно записать так:
В полученном оптимальном плане присутствуют дробные числа.
Для переменной x, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение:
q3 - q31*x1 - q32*x2 - q33*x3 - q34*x4?0
Дополнительное ограничение имеет вид:
Преобразуем полученное неравенство в уравнение:
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
В полученном оптимальном плане присутствуют дробные числа.
Для переменной x5, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение:
q3 - q31*x1 - q32*x2 - q33*x3 - q34*x4 - q35*x5?0
Дополнительное ограничение имеет вид:
Преобразуем полученное неравенство в уравнение:
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2/3).
Выполняем преобразования симплексной таблицы.
Решение получилось целочисленным. Оптимальный целочисленный план можно записать так:
2.2 Пример решения задачи методом ветвей и границ
Методом ветвей и границ найти решение задачи,
Обзор задач дискретного программирования курсовая работа. Программирование, компьютеры и кибернетика.
Реферат: Национальный проект Развитие АПК
Эссе Английский 11
Реферат: Банковская конкуренция
Курсовая работа по теме Навигационный расчет плана полета
Реферат по теме История болезни (терапия) язвенная болезнь
Реферат: Custer
Дипломная работа: Основания и условия прекращения трудового договора
Проектно Технологическая Практика По Педагогике Отчет
Реферат: John Paul Jones Essay Research Paper John
Курсовая работа: Трудовой договор: его понятие, виды, значение, содержание. Скачать бесплатно и без регистрации
Социально Психологическая Характеристика Коллектива Реферат
Курсовая работа: Система социальной защиты населения
Курсовая работа по теме Розробка маршрутів доставки робітників на будівельний об’єкт
Сочинение 9 1 Пример
Контрольная Работа На Тему Экономические Взгляды Ивана Пересветова И Ермолая-Еразма
Сочинение На Кабардинском Языке Бжьыхьэ 6 Класс
Аннотация К Диссертации По Медицине Пример
Курсовая Работа На Тему Проблема Адаптации И Причины Дезадаптации В Младшем Дошкольном Возрасте
Курсовая работа по теме Общие положения авторского права
Отан Дегеніміз Не Эссе
Розрахунок каналу обробки аналогового сигналу - Коммуникации, связь, цифровые приборы и радиоэлектроника курсовая работа
Відображення в балансі витрат і доходів майбутніх періодів - Бухгалтерский учет и аудит контрольная работа
Особенности терроризма как уголовного преступления - Государство и право дипломная работа