Исходник симплекс метода в питоне

Исходник симплекс метода в питоне

Вчера я защитил курсовую работу по теме «Симплекс-метода» и решил поделиться своими наработками с читателем. Ниже представлена осноная часть пояснительной записки.

Если вам лень читать это здесь — скачайте весь курсовой проект в запакованном виде.

Введение

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

Данный метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.

Постановка задачи

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

Математическое обеспечение

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

Необходимо найти оптимальный план данной задачи с помощью симплекс-метода с использованием симплекс-таблицы.

Разработка алгоритма программы

Перед началом работы необходимо было понять сам алгоритм симплекс-метода. Для этого решалось несколько задач письменно. После освоение алгоритма была продумана структора самого проекта. Первым делом был написан класс user_data, который принимает пользовательские данные, т.е. Саму задачу, которую необходимо решить с помощью симплекс-метода. Рассмотрим содержимое заголовочного файла этого класса.

Рассмотрим все защищенные переменные-члены данного класса.

    int num_v хранит в себе значение количества переменных исходной задачи.

int num_l хранит в себе значение количества ограничений исходной задачи.

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

double system хранит в себе значения коэффициентов самой системы ограничений. Это член является указателем на массив указателей, который в последующем будет инициализирован как матрица, соответствующая по размеру системе ограничений поставленной задачи ( num_l * num_v ).

int sign хранит в себе знак каждого ограничения системы. Является указателем типа int, который будет инициализирован как одномерный массив типа с размером num_l . Рационально использовать в данном случае целочисленный тип а не строковый. т.к. У нас есть три знака: , = и >= , которые храняться в *sign как 0, 1 и 2 соответственно.

  • bool way хранит в себе направление целевой функции задачи (min/max). При решении задачи на максимум эта переменная-член будет хранить в себе значение истины ( true ). А при решении на минимум, соответственно, ложь ( false ). Такой способ хранения данных очень рационален в данном случае, поскольку направлений у функции цели может быть только два. Поэтому тип bool идеально подходит для этого.
  • Функция void get_data_from_user() , собственно запрашивает у пользователя данные, которые обрабатывает должным образом и помещает в защищенные переменные-члены данного класса, приведенные выше. В заголовочном файле хранится только прототип данной функции. Само определение функции находится в файле user_data.cpp.

    Рассмотрим содержимое этого файла.

    Функция error(int err_no) принимает в качестве аргумента номер ошибки, которая должна вывестись пользователю в том случае, если он ввел некорректные данные. Далее номер ошибки, переданный в функцию обрабатывается оператором switch(), и в зависимости от принимаемого функцией аргумента, выводится ошибка с помощью оператора cout.

    Теперь рассмотрим функцию-член get_data_from_user() класса user_data. Все данные, который вводит пользователь, первоначально помещаются в объект типа string, а затем проверяется корректность данных, если все введено верно, то выполняется преобразование из std::string в int или double с помощью функций atoi() и atof() соответственно.

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

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

    Затем выделяется память под массив function и матрицу system, а затем также идет ввод коэффициентов функции цели в цикле. После идет ввод значения направления функции. Если оно введено верно, то в переменная-член way заносится true или false, в зависимости от введенного значения. Регистр при вводе направления не учитывается при проверке. Если все верно, заполняется матрица system коэффициентами системы ограничений исходной задачи. Заполнение происходит в двух вложенных циклах, в первом из которых, также вводится знак ограничения и значение свободного члена при этом ограничении. Когда пользователь закончит ввод, все переменная-члены класса user_data будут заполнены, и тогда мы переходим к самому алгоритму, который реализован в классе simplex, являющимся прямым наследником класса user_data.

    Рассмотрим содержимое заголовочного файла этого класса.

    Сначала рассмотрим закрытые переменная-члены данного класса.

    • double func — содержит значение целевой фукнции. При каждой итерации оно меняется.
    • double **bv — Содержит значения базисных переменных задачи. Данный член является указателем на массив указателей, который в последующем инициализируется двумерным массивом num_v * 2 , в первом стобце которого содержатся непосредственно. Сами значения базисных переменных задачи, а во втором номера этих переменных, которые изменяются при каждой последующей итерации. Номера базисных переменных необходимы для того, чтобы правильно вывести пользователю ответ и построить таблицу на выходе.

    double **sv — Матрица коэффициентов при переменных задачи размером num_l * num_v * 2 . Первые num_v столбцы данной матрицы заполняются коэффициентами исходной системы ограничений, а последующие num_v столбцы заполняются единичной матрицей, если решается задача на максимум, если же производится решение задачи на минимум, единицы меняют свой знак.

    double *istr — индексная строка, является одномерным массивом размером num_v * 2, первая половина которого заполняется коэффициентами функции-цели с обратным знаком, а вторая нулями на первой итерации. На последующих итерациях значения индексной строки меняются.

    int i_lrow = индекс ведущей строки текущего плана.

    double alm — разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки.

  • std::stringstream table — объект класса std::stringstream, который содержит весь пользовательский вывод в выходной файл.
  • Собственно, сейчас были рассмотрены предназначения каждой переменная-члена класса simplex.

    Весь алгоритм вычиления вышеприведенных значений производится в файле simplex.cpp.

    Сначала выполняется инициализация первого опорного плана. Этим занимается функция-член init() класса simplex.

    Значение функции-цели в первом опорном плане всегда равно нулю, поэтому в init() выполняется инициализация переменной-члена func класса simplex именно нулем.

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

    Читайте также:  Как проверить термопредохранитель холодильника самсунг

    После заполнения sv производится выделение памяти под одномерный массив istr и иницализация этого массива (индексной строки первого опорного плана). Первая ее часть заполняется коэффициентами целевой функции с обратным знаком, вторая ее половина инициализируется нулями.

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

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

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

    Разрешающий элемент плана находится на пересечении ведущего столбца и ведущей строки текущего плана. После его вычисления производится вызов функции print_result_to_file(), которая заносит таблицу для первоначального опорного плана в объект table класса std::stringstream, который также является переменная-членом класса simplex.

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

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

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

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

    Где «НЭ» — вычисляемые элемент нового плана, «СТЭ» — элемент предыдушего плана, соответвующий вычиляемому элементу, РЭ — разрешающий элемент предыдушего плана. Переменные A и B — это элементы старого плана, которые образуют «Прямоугольник», например.

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

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

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

    Но перед тем, как вывести на экран ответ, в цикле производится вызов функции print_result_to_file(), которая в данном случает принимает в качестве аргумента номер итерации цикла, начиная с единицы. Функция пишет в объект table класса std::stringstream весь вывод, причем делает это «по умному», т. е. Формулирует весь алгоритм решения человеческим языком. Если план при текущей итерации стал оптимален, функция print_result_to_file() создает объект outfile класса std::oftream, т. е. Грубо говоря, выходной файл, в который записывается уже имеющийся объект table класса std::stringstream. Это является рациональным решением, т. к., если будет необходимо напечатать все решение на экран или еще куда-либо, нужно будет просто заменить «outfile

    Зачем решать экстремальные задачи

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

    К сожалению, не всегда можно положиться на интуицию. Допустим Вы сотрудник коммерческой фирмы и отвечаете за рекламу. Затраты на рекламу в месяц не должны превышать 10 000 денежных единиц (д.е). Минута радиорекламы стоит 5 д.е., а телерекламы 90 д.е. Фирма намерена использовать радиорекламу в три раза чаще чем телерекламу. Практика показывает, что 1 минута телерекламы обеспечивает объём продаж в 30 раз больший чем 1 минута радиорекламы.

    Перед Вами стоит задача определить такое распределение средств между двумя упомянутыми видами рекламы при котором объём продаж фирмы будет максимальным. Вы сначала выберите переменные, а именно месячный объём в минутах на телерекламу — x1, а на радиорекламу —x2. Теперь не трудно составить следующую систему:

    30×1+x2 –увеличение продаж от рекламы;
    90×1+5×2 Листинг программы для решения задачи «О рекламе»

    В лис тенге программы уже знакомые нам соотношения для максимальной прибыли от рекламы 30*x1+x2, условия ограничения затрат, помеченные для сравнения «1». Мы не забыли и об отношении времён использования радио и теле рекламы, помеченные в лис тенге как «2». Назначение других операторов очевидны, Подробности можно прочесть в [1].

    Результаты решения задачи оптимизации с использованием pulp.

    Результат:
    x1 = 95.238095
    x2 = 285.71429
    Прибыль:
    3142.85714
    Время:
    0.10001182556152344

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

    Оптимизация с библиотекой cvxopt [2].

    По структуре программа аналогична предыдущей, но имеются два существенных отличия. Во-первых, библиотека cvxopt настроена на поиск минимума функции цели, а не на максимум. Поэтому целевая функция взята с отрицательным знаком минус -(30*x[0] +1*x[1]). Полученное вследствие этого отрицательное её значение выведено по абсолютной величине. Во-вторых, введено ограничение на не отрицательность переменных- non_negative. Повлияло ли это на результат мы сейчас у видим.

    Результаты решения задачи оптимизации с использованием cvxopt.

    Прибыль:
    3142.857142857143
    Результат:
    [ 9.52e+01]
    [ 2.86e+02]
    Время:
    0.041656494140625

    Никаких существенных изменений в сравнении с библиотекой pulp не произошло за исключением время работы программы.

    Оптимизация с библиотекой scipy. optimize [3].

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

    Результаты решения транспортной задачи с использованием pulp.

    Результат:
    x1 = 0.0
    x2 = 45.0
    x3 = 0.0
    x4 = 0.0
    x5 = 0.0
    x6 = 30.0
    x7 = 20.0
    x8 = 0.0
    x9 = 0.0
    Стоимость доставки:
    215.0
    Время:
    0.19006609916687012

    Оптимизация с библиотекой cvxopt.

    Результаты решения транспортной задачи с использованием cvxopt.

    Результат:
    [ 0.00e+00]
    [ 4.50e+01]
    [ 0.00e+00]
    [ 0.00e+00]
    [ 0.00e+00]
    [ 3.00e+01]
    [ 2.00e+01]
    [ 0.00e+00]
    [ 0.00e+00]
    Стоимость доставки:
    215.0
    Время :
    0.03001546859741211

    Оптимизация с библиотекой scipy. optimize.

    Результаты решения транспортной задачи с использованием scipy optimize.

    fun: 215.0
    message: ‘Optimization terminated successfully.’
    nit: 9
    slack: array([ 29., 10., 16.])
    status: 0
    success: True
    x: array([ 0., 45., 0., 0., 0., 30., 20., 0., 0.])
    Время:
    0.009982585906982422

    Читайте также:  Дан пространственный четырехугольник авсд в котором

    Анализ решения двух типовых задач линейного программирования с помощью трёх библиотек аналогичного назначения не вызывает сомнения в выборе библиотеки scipy. optimize, как лидера по компактности ввода данных и быстродействию.

    Что нового для использования библиотеки scipy. optimize при решении задач линейного программирования

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

    Теперь вводиться только сама матрица A и списки правых частей b_ub неравенств и b_ub – равенств.

    Результат рaботы программы предсказуем.
    fun: 215.0
    message: ‘Optimization terminated successfully.’
    nit: 9
    slack: array([ 29., 10., 16.])
    status: 0
    success: True
    x: array([ 0., 45., 0., 0., 0., 30., 20., 0., 0.])

    Вывод частный

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

    Вывод общий

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

    Ссылки

    Редакторский дайджест

    Присылаем лучшие статьи раз в месяц

    Скоро на этот адрес придет письмо. Подтвердите подписку, если всё в силе.

    • Скопировать ссылку
    • Facebook
    • Twitter
    • ВКонтакте
    • Telegram
    • Pocket

    Похожие публикации

    • 31 января 2012 в 00:04

    Python, scipy.weave и openMP — разгоняем код

    Учебник по языку программирования Python (хабраиндекс)

    Основы языка программирования Python за 10 минут

    Заказы

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Комментарии 8

    Python 2.* и вырвиглазное форматирование — классика.

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

    Я совершенно не специалист в оптимизациях, но все же я не уверен что корректно сравнивать scipy linprog и cvxopt.
    Первый — просто вызов симплекс солвера по готовым матрицам.
    https://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.optimize.linprog.html

    cvxopt же — целый DSL (т.е. вам не нужно в ручную подготавливать данные для солвера) позволяющий решать намного больший класс задач.
    Так же, в примере с cvxopt использовался солвер glpk (https://www.gnu.org/software/glpk/), который вроде как предназначен для работы с задачами большой размерности («The GLPK (GNU Linear Programming Kit) package is intended for solving large-scale linear programming (LP)»). Т.е. в статье сравнивается теплое с мягким.

    Окей, давайте по порядку.

    >Цель статьи не тестирование библиотек, а сравнение интерфейсных возможностей решателей для двух конкретных групп задач линейного программирования
    В таком случае, на это стоило делать акцент.
    К тому же, мне кажется что если мы сравниваем библиотеки по способу задания задачи, cvxopt/pulp явно предпочтительней. Почему? Потому что они позволяют писать значительно более читаемый и поддерживаемый код.
    Ограничения добавляются/удаляются в cvxopt одной строчкой. Функционал так же очень легко модифицируется. Фактически вы просто пишете формулы описывающие ограничения и функционал.
    Если же матрицы сформированы вручную, то это разумеется более эффективно, но читать и работать с таким кодом довольно неприятно. Как минимум вам придется писать комментарии

    Собственно код из вашей статьи.
    Это cvxopt. Если нормально назвать переменные (x1 — moneyForTVAd x2 — moneyForRadioAd) и ф-ии (z — negativeSalesIncr и т.д.), то понять какую именно задачу вы решаете, сможет даже человек не знакомый с предметной областью

    Это та же самая задача, но решаемая при помощи linprog (если я не ошибаюсь, конечно).
    Работать можно и с этим, но согласитесь, это значительно менее приятно чем работать с кодом выше.

    Идем дальше
    >Различные формы представления исходных данных с использованием матрицы для формирования функции цели и без влияет на аппаратное время выполнения программы.
    Да, это разумеется так.
    >При усреднении времен такое сравнение корректно и оправдано.
    И это тоже верно, вот только я не увидел чтобы вы решали запускали решение LP задач тысячу раз, чтобы говорить об усреднении. Но это не самое страшное. Проблема в том, что на задачах очень малой размерности на время выполнения начинает сильно влиять различный .Overhead. Overhead от вызова самих питоновских функций (если анализ задачи оптимизации в cvxopt выполняется на питоне, то он может занимать больше времени чем сама оптимизация), overhead от вызова C/C++ кода, и т.д.
    Более того, как я и писал выше, linprog и cvxopt (в вашем случае) используют разные алгоритмы оптимизации заточенные под разные случаи. Симплекс-метод хорошо подходит для небольших задач (как ваши), GLPK же (если я правильно понял) использует итеративный алгоритм и заточен под большие задачи (т.е. сотни тысяч переменных/ограничений). Подозреваю, что у cvxopt есть и другие солверы, однако у вас вызывается именно этот. Собственно на этом можно остановиться, сравнение производительности в такой ситуации смысла не имеет.

    >Кроме того само утверждения голословно — какой класс, каких задач.
    Выпуклые оптимизации же =) CVXOPT — ConVeX OPTimization.

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

    Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

    ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

    Симплекс-метод. Реализация

    В этой статье рассматривается симплекс-метод, который применяется при решении задач линейного программирования (ЗЛП). Приводится алгоритм метода, а также его реализация на языке C#. Реализация представлена в конце статьи.

    Определения

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

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

    Оптимизация – задача нахождения минимума или максимума (экстремума) целевой функции.

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

    Алгоритм симплекс-метода

    В начале исходную задачу линейного программирования приводят к каноническому виду, затем составляют симплекс-таблицу вида:

    где в столбце «базис» указываются базисные переменные, а в последней строке столбца «базис» пишется f(x). В столбец «B» записываются свободные члены ограничений bi и значение целевой функции (на 1-м этапе оно равно 0, т.е. никакой прибыли).

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

    Читайте также:  Как отключить truecaller в wileyfox

    В последней строке -cj – это коэффициенты при переменных целевой функции взятые с противоположным знаком.

    Симплекс-таблица составлена, теперь опишем сам симплекс-метод.

    Шаг 1: Выполняется проверка полученного базисного плана на оптимальность по условию: если при каком-либо ДБР (допустимое базисное решение) в симплекс-таблице все коэффициенты строки f(x) (то есть -cj) не отрицательны, то данное ДБР оптимально, следовательно КОНЕЦ решения. В противном случае:

    Шаг 2: Переход к новому базисному плану. Для этого из числа небазисных переменных с отрицательными значениями в последней строке (то есть -cj

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

    Демонстрация работы симплекс-метода:

    Поделиться в соц. сетях:

    33 комментария(ев) к статье “ Симплекс-метод. Реализация ”

    Спасибо, очень полезная информация и программа!

    А что нужно сделать, чтобы функции искали переменные для минимума, а не для максимума?

    1. admin Автор статьи 02.12.2016 в 10:38

    Нужно поменять знак у функции: min(f(x)) = max(-f(x))

    то есть сменить знаки коэффициентов при переменных? если так, то программа всё равно считает максимум

    1. admin Автор статьи 02.12.2016 в 13:21

    Да. Странно, должно было сработать.

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

    1. admin Автор статьи 11.12.2016 в 11:44

    Перед вводом данных в программу задачу нужно привести к каноническому виду.

    Что вы подразумеваете под привести задачу к каноническому виду? Канонический вид, это же вроде:
    1)инвертировать знаки у ф-ции F
    2)добавить доп.переменные, 1 если знак неравенства =, это канонический вид.

    У вас же таблица на входе имеет вид —-B—X1—X2 или я что-то не понимаю? Скажите пожалуйста, как именно нужно обработать систему неравенств?

    1. admin Автор статьи 06.01.2017 в 00:54

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

    А в программу заносятся коэффициенты из приведённых ограничений:

    b1 a11 a12 …
    b2 a21 a22 …

    0 -c1 -c2 …

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

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

    1. admin Автор статьи 12.12.2016 в 21:31

    Перед вычислениями сохраните в отдельный массив значения коэффициентов при иксах: например в массив a.

    После того, как массив result будет получен, найдём значение целевой функции F:

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

    1. admin Автор статьи 20.12.2016 в 22:09

    1) Самый простой: привести задачу минимизации (сами исходные данные) к задаче максимизации и использовать приведённый выше алгоритм. Как преобразовать написано здесь.

    2) Изменить приведённый алгоритм конкретно под задачу минимизации. При минимизации целевой функции ведущий столбец определяется по наибольшему значению в строке индексов. Читать про это подробнее.

    Админ, спасибо за реализацию, а какой будет алгоритм, если мне необходимо в одной задачи использовать ограничения ‘=>’ и ‘

    1. admin Автор статьи 21.03.2017 в 07:45

    Алгоритм будет точно такой же. Ведь система неравенств всё равно приводится к каноническому виду (в системе ограничений знаки становятся равенствами).

    В предыдущем моём комментарии есть ссылка, там как раз есть пример с разными знаками в системе неравенств.

    admin, помогите, пожалуйста, разобраться с вводом данных моей задачи. Заранее извиняюсь за столь глупый вопрос.
    Ограничения:
    2*y1+5*y2=1
    6*y1+1*y2=1
    Функция:
    1*y1+1*y2 –> max

    1. admin Автор статьи 11.04.2017 в 11:38

    Здравствуйте! Вот такие данные будут у Вас:

    1 2 5
    1 6 1
    0 -1 -1

    Будет ли программа работать для более, чем двух переменных? Что нужно менять в коде, кроме входной матрицы?

    1. admin Автор статьи 22.05.2017 в 22:03

    Будет. В коде ничего менять не нужно.

    Спасибо вам огромнейшее!

    Здравствуйте. Простите за глупый вопрос, а как запустить эту программу?

    1. admin Автор статьи 17.02.2018 в 22:20

    Здравствуйте! Нужно создать проект консольного приложения на C#, например, в Visual Studio, добавить в проект класс Simplex (из данной статьи) и код в классе Program заменить на тот, что представлен в статье.

    Сделал так, как и описали. Но в 21 строке 13 и 29 столбцы помешает как ошибку : simplex является “пространство имен” но используется как “тип”. Не подскажете в чем причина может быть?

    1. admin Автор статьи 17.02.2018 в 23:39

    Изменили в файле с классом Simplex название пространства имен “Simplex” на то, которое у вас в проекте?

    Я как понял. Program.cs здесь ничего не меняем из Вашего кода. А в simplex.cs меняем namespace Simplex на namespace имя проекта, правильно?

    Один фиг не получается )))

    А если вот такая задача:
    целевую функцию минимизировать:
    801*x000 + 391*x001 + 705*x002 + 596*x010 + 472*x011 + 821*x012 + 490*x020 + 261*x021 + 710*x022 + 590*x100 + 322*x101 + 373*x102 + 496*x110 + 514*x111 + 600*x112 + 492*x120 + 405*x121 + 591*x122 + 632*x200 + 535*x201 + 533*x202 + 375*x210 + 564*x211 + 597*x212 + 288*x220 + 372*x221 + 505*x222
    Ограничения
    1*x000 + 1*x001 + 1*x002 + 1*x010 + 1*x011 + 1*x012 + 1*x020 + 1*x021 + 1*x022 = 1
    1*x100 + 1*x101 + 1*x102 + 1*x110 + 1*x111 + 1*x112 + 1*x120 + 1*x121 + 1*x122 = 1
    1*x200 + 1*x201 + 1*x202 + 1*x210 + 1*x211 + 1*x212 + 1*x220 + 1*x221 + 1*x222 = 1
    1*x000 + 1*x001 + 1*x002 + 1*x100 + 1*x101 + 1*x102 + 1*x200 + 1*x201 + 1*x202 = 1
    1*x010 + 1*x011 + 1*x012 + 1*x110 + 1*x111 + 1*x112 + 1*x210 + 1*x211 + 1*x212 = 1
    1*x020 + 1*x021 + 1*x022 + 1*x120 + 1*x121 + 1*x122 + 1*x220 + 1*x221 + 1*x222 = 1
    1*x000 + 1*x010 + 1*x020 + 1*x100 + 1*x110 + 1*x120 + 1*x200 + 1*x210 + 1*x220 = 1
    1*x001 + 1*x011 + 1*x021 + 1*x101 + 1*x111 + 1*x121 + 1*x201 + 1*x211 + 1*x221 = 1
    1*x002 + 1*x012 + 1*x022 + 1*x102 + 1*x112 + 1*x122 + 1*x202 + 1*x212 + 1*x222 = 1
    x000 >= 0
    x001 >= 0
    x002 >= 0
    x010 >= 0
    x011 >= 0
    x012 >= 0
    x020 >= 0
    x021 >= 0
    x022 >= 0
    x100 >= 0
    x101 >= 0
    x102 >= 0
    x110 >= 0
    x111 >= 0
    x112 >= 0
    x120 >= 0
    x121 >= 0
    x122 >= 0
    x200 >= 0
    x201 >= 0
    x202 >= 0
    x210 >= 0
    x211 >= 0
    x212 >= 0
    x220 >= 0
    x221 >= 0
    x222 >= 0

    1. admin Автор статьи 04.10.2018 в 12:08

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

    А как построить матрицу с такой задачей? хотя бы напишите пожалуйста строку с целевой функцией и двумя различными ограничениями

    1. admin Автор статьи 06.10.2018 в 00:43

    Посмотрите выше мой ответ на комментарий Михаила (от 11.04.2017). И подобно его примеру можно построить матрицу.

    Нужно учесть, что у вас задача минимизации, поэтому необходимо сделать min(f(x)) = max(-f(x)).

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

    1 1 1 …
    1 1 1 …

    0 801 391 …

    Так и не смог понять, как нужно записать выражение вида =>. Можете привести пример?

    1. admin Автор статьи 21.11.2018 в 19:11

    Посмотрите мой комментарий от 20.12.2016 в 22:09. Там есть вся информация по данному вопросу.

    Ссылка на основную публикацию
    Интересные частоты для прослушивания
    В случае начала войны с очень большой долей вероятности интернет будет отключен. Так же будут перебои с электричеством, поэтому, единственным...
    Знак принадлежности в маткаде
    Подведем некоторый итог. Математические выражения содержат, как правило, самые различные, в том числе специфичные символы, набор которых в Mathcad выполняется...
    И снова здравствуйте как пишется пунктуация
    1 ответ Фраза «и снова здравствуйте» зачастую используется в разговорной речи в ироничном значении «я вернулся», «это опять я». На...
    Исходник симплекс метода в питоне
    Вчера я защитил курсовую работу по теме «Симплекс-метода» и решил поделиться своими наработками с читателем. Ниже представлена осноная часть пояснительной...
    Adblock detector