Letysite.ru

IT Новости с интернет пространства
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Целочисленное программирование онлайн

Калькулятор симплекс-метода

Выполнено действий: 126

Как пользоваться калькулятором

  • Задайте количество переменных и ограничений
  • Введите коэффициенты целевой функции
  • Введите коэффициенты ограничений и выберите условия (≤, = или ≥)
  • Выберите тип решения
  • Нажмите кнопку «Решить»

Что умеет калькулятор симплекс-метода

  • Решает основную задачу линейного программирования
  • Позволяет получить решение с помощью основного симплекс-метода и метода искусственного базиса
  • Работает с произвольным количеством переменных и ограничений

Что такое симплекс-метод

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

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Алгоритм является универсальным методом, которым можно решить любую задачу линейного программирования.

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

Целевая функция — функция, максимум (или минимум) которой нужно найти. Представляет собой сумму произведений коэффициентов на значения переменных: F = c1·x1 + c2·x2 + . + cn·xn

Ограничение — условие вида a1·x1 + a2·x2 + . + an·xn v b , где вместо v ставится один из знаков: ≤, = или ≥

План — произвольный набор значений переменных x1 . xn.

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

Пусть в задаче есть m ограничений, а целевая функция заивисит от n основных переменных. Первым делом необходимо привести все ограничения к каноническому виду — виду, в котором все условия задаются равенствами. Для этого предварительно все неравенства с ≥ умножаются на -1, для получения неравенств с ≤.

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

Формирование начального базиса

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

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

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

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x6
Столбец 4 является частью единичной матрицы. Переменная x4 входит в начальный базис
В пятом столбце все значения кроме третьего равны нулю. Поэтому в качестве третьей базисной переменной берём x5 , предварительно разделив третью строку на 2.
Симплекс-таблица

Целочисленное программирование

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

Формулировка задачи целочисленного программирования: найти наибольшее значение функции

,

, х j — целые, .

Если k = n , то задача полностью целочисленная.

Если k n , то задача является частично целочисленной.

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

Иногда задачи целочисленного программирования решают приближенно. Отбросив условие целочисленности, решают задачу методом линейного программирования, затем в полученном оптимальном решении округляют переменные до целых чисел. Такой прием можно использовать, если значения переменных достаточно велики и погрешностью округления можно пренебречь. Если значения переменных невелики, то округление может привести к значительному расхождению с оптимальным решением. Существует аналитический метод решения полностью целочисленных задач — метод Гомори.

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

Читать еще:  Ошибка ssl подключения как исправить opera

Дополнительное ограничение отсекает часть области, содержащую нецелочисленное оптимальное решение.

Вновь полученную задачу решают методом линейного программирования. Процесс построения сечений и решения задачи повторяется до получения целочисленного оптимального решения. Общий систематический способ построения сечений разработал Гомори в 1958 г .

Алгоритм метода Гомори

Пусть дана полностью целочисленная задача линейного программирования: найти максимальное значение функции

,

, х j — целые, .

1) Отбросив условие целочисленности, решаем исходную задачу симплексным методом. Если получится целочисленное оптимальное решение, то задача решена. Если в оптимальном решении не все переменные целочисленны, то строим сечения.

2) Пусть в оптимальном решении переменная x t — дробное число, т.е. x t = f t . Рассмотрим уравнение, в котором x t — базисная переменная.

, (1)

где J — множество индексов свободных переменных.

Разобьем все коэффициенты и свободный член (1) на два слагаемых: целую и дробную часть. Целой частью числа а называется наибольшее целое число, не превышающее а. Дробной частью числа а называется разность между числом а и его целой частью. Целую часть числа обозначим [ а ] , а дробную часть — í а ý , т.е. а = [ а ] + í а ý . Тогда уравнение (1) примет вид

, (2)

.

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

(3)

является сечением Гомори.

Покажем, что любое целочисленное решение задачи удовлетворяет этому неравенству, а нецелочисленное решение ему не удовлетворяет. Пусть — целочисленное решение, и предположим, что оно не удовлетворяет неравенству (3), т.е.

, или

по условию lj ³ 0, , отсюда , кроме того, . Получим

, или , т.е. является дробным числом.

Подставив в уравнение (2), получим

.

Правая часть уравнения — дробное число, а левая часть — целое число. Получили противоречие. Следовательно, любое целочисленное решение задачи удовлетворяет неравенству (3).

Покажем, что нецелочисленное оптимальное решение не удовлетворяет неравенству (3).

Пусть — нецелочисленное оптимальное решение задачи. Подставим его в неравенство (3):

, но

Следовательно, не удовлетворяет неравенству (3).

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

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

Пример. Найти наибольшее значение функции

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

х j ³ 0, .

Целочисленное программирование онлайн

13. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

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

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

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

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

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

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

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

Читать еще:  Ssl connect error что за ошибка

Исторически первой задачей целочисленного типа является опубликованная в 1932 г. венгерским математиком Е. Эгервари задача о назначении персонала. В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце.

Приведем примеры целочисленных задач линейного программирования.

Пример. Задача о ранце. Имеется m -вектор ограниченных ресурсов , которые можно использовать для перевозки различных по своим характеристикам грузов. Каждый j -й груз обладает следующими свойствами: 1) неделимостью; 2) полезностью ; 3) расходом i -го ресурса для перевозки единицы j -го груза . Выбрать такой номер груза для перевозки, при котором максимизируется общая полезность рейса (суммарная стоимость перевезенных за рейс грузов).

Составим математическую модель задачи. Обозначим через количество выбранных для траспортировки предметов. Требованию неделимости соответствует условие

целые, (13.1)

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

(13.2)

Общая полезность рейса определяется значением функции

. (13.3)

Частным случаем задачи (13.1) – (13.2) является задача о ранце, в которой любой из заданного набора предметов может быть выбран или нет. Тогда математическая модель примет следующий вид:

Пример. В области

найти максимум функции .

Решим задачу геометрически (рис. 13.1). Область поиска экстремума – многоугольник OABCD . Так как линия уровня целевой функции параллельна стороне BC многоугольника, экстремум достигается в вершинах и , а также в любой точке отрезка BC и равен 7. Нас интересуют лишь точки с целочисленными координатами, поэтому ни B , ни C не являются допустимым решением задачи. Округлив значение координат точек B и C , получим точку (4; 3), не принадлежащую области поиска. Легко показать, что целочисленный оптимум достигается в точках M (2; 3) и N (3; 2) и равен 5. Обе точки находятся внутри области поиска.

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

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

Целочисленное программирование онлайн

целое, , где все — заданные числа, а переменные задачи.

Задачи П. ц. можно разделить на несколько характерных классов. 1. Задачи с неделимостями — задачи, переменные которых представляют физически неделимые величины. 2. Экстремальные комбинаторные задачи — задачи, в которых требуется найти экстремум целочисленной линейной ф-ции, заданной на конечном множестве элементов, и само подмножество элементов, на котором этот экстремум достигается. Число таких подмножеств для реальных задач, как правило, чрезвычайно велико, поэтому решение таких задач путем перебора всех вариантов связано с непреодолимыми трудностями. Эти задачи можно сформулировать в виде задачи программирования линейного, в многограннике решений которой каждой целочисленной точке соответствует определенное подмножество элементов исходной комбинаторной задачи. Решение полученной задачи имеет комбинаторный смысл лишь в случае его целочисленности. К числу наиболее известных задач этого класса относятся задачи о коммивояжере, о назначении, задачи теории расписаний и т. д. 3. Задачи с неоднородной разрывной линейной формой, т. е. задачи с линейной формой вида

Они сводятся к задачам линейного П. ц. путем добавления к задаче целочисленных переменных и ограничений , где наибольшее значение, принимаемое и заменой исходной линейной формы (1) на . Из задач этого класса наиболее известны транспортная задача с фиксированными доплатами и различные варианты задач размещения. К задачам линейного П. ц. сводится с достаточной степенью точности и задача минимизации произвольной сепарабельной функции (1) на выпуклом многограннике. 4. Задачи на неклассически? областях представляют собой задачи нахождения экстремума линейной формы на области, задаваемой, помит линейных неравенств, еще и логическими условиями вида «ЛИБО — ЛИБО». Такие области обычно невыпуклы или несвязны. Путем введения новых целочисленных переменных эти задачи также сводятся к задачам линейного П. ц.

Общие методы линейного программирования непосредственно к задачам линейного П. ц. применять нельзя, т. к. в большинстве случаев они дают дробные решения. Округление компонент целочисленного решения до ближайших целых чисел может не только увести от оптим. целочисленного решения, но и вывести за пределы допустимых решений. Существует класс задач П. ц., среди оптим. решений которых всегда имеется целочисленное. К этому классу относятся, напр., транспортная задача, сетевая транспортная задача, задача о назначениях, задача о кратчайшем пути и некоторые другие. Эта особенность связана с тем, что определитель произвольной квадратной подматрицы матрицы условий задачи равен нулю или ± 1. Такие задачи решают методами

Читать еще:  При установке скайпа выдает ошибку

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

Американскими учеными Дж. Данцигом, Д. Фалкерсоном и С. Джонсоном была предложена основная идея методов отсечения для решения задач линейного П. ц. Эта идея заключается в следующем. Задача решается сначала без ограничений целочисленности. Если полученное решение целочисленно, то оно является оптим. решением задачи П. ц. В противном случае, к условиям исходной задачи добавляется линейное ограничение, которому удовлетворяют все целочисленные решения исходной задачи, но не удовлетворяет полученное нецелочисленное решение. Описанная процедура отсечения продолжается вплоть до получения на некотором шаге целочисленного оптим. решения либо до выявления неразрешимости задачи. Т. о., решение задачи П. ц. сводится к решению последовательности задач линейного программирования. Впервые правило формирования дополнительных ограничений для полностью целочисленных, а затем и частично целочисленных линейных задач П. ц. было разработано амер. ученым Р. Гомори в 1958 г. Гомори метод при достаточно естественных предположениях о задаче приводит к оптим. целочисленному решению за конечное число шагов. Известны и другие методы, использующие идею отсечения.

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

Методы случайного поиска (см. Численные методы) и другие приближенные методы применяются, как правило, для решения задач П. ц. большой размерности, для которых точные методы малоэффективны. Лит.: Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. М., 1969 [библиогр. с. 358—366]: Корбут А. А., Финкельштейн Ю. Ю. Дискретные задачи математического программирования. В кн.: Итоги науки. Теория вероятностей, математическая статистика, теоретическая кибернетика. 1966. М., 1967 [библиогр. с. 97—108]; Гольштейн Б. Г., Юдин Д. В. Новые направления в линейном программировании. М., 1966 [библиогр. с. 516—520].

ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

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

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

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

Пусть получено оптимальное решение опт = (f1, f2, . , fr, 0, . 0), которое не является целочисленным, тогда последний шаг симплексной таблицы имеет следующий вид:

где r — ранг системы ограничений; hi,r+1 — коэффициент симплексной таблицы i–й строки, (r + 1)–го столбца; fi — свободный член i–й строки.

Пусть fi и хотя бы одно hij (j = , r = ) — дробные числа.

Обозначим через [fi] и [hij] целые части чисел fi и hij.

Определение. Целой частью числа fi называют наибольшее целое число, не превосходящее числа fi.

Дробную часть чисел fi и hij обозначим и , она определяется следующим образом:

Если fi и хотя бы одно значение hij дробны, то с учетом введенных обозначений целых и дробных чисел дополнительное ограничение по целочисленности примет вид

Примечания. 1) Если fi — дробное число, а все hij — целые числа, то задача линейного программирования не имеет целочисленного решения.

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

Ссылка на основную публикацию
Adblock
detector