Симплекс-метод решения задач линейного программирования #256597

На яндекс не посылайте пжл - там куча ссылок на дурацкие рефераты - замучался уже искать нормальную статью. Нужна ссылка с нормальным описанием сабжа

Нашел в гугле: и т.д.

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

В поиск (С)

Я офигел уже по этим дрянным сайтам с рефератами копаться. Сейчас сам еще на Гугле посмотрю, хотя жутко его не перевариваю.

а зря...

google.com юзай = там сортировка по количеству ссылок, поэтому наверху находятся правильные статьи.

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

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

+8 Помню намучался с ним когда курсовую писал...

Гм.. Еще больше запутался. Ладно буду образовываться ;)

Если остались полезные ссылки или книги в эл.виде - поделись пожалуйста.

вопрос не рассматривался в 3-м классе входит в типовую программу по высшей математике вуза.

Ахринеть... Меня одно слово "симплекс" в дрожь бросает...

К сожалению не осталось -  учебу закончил все поудалял...

Странно, нам в МИФИ не давали такой материал. Хотя возможно, я это прогулял;)..

Школу не нужно было прогуливать

Симплекс :) дерьмовый метод.... только для линейной системы.... движение по точкам.. и только для выпуклой области

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

А литературу про другие способы не скинешь? ОдинЭсил много.

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

Например,

Спасибо! Буду изучать.

посмотри, там вроде есть раздел лекций.

и замкнутой

В самом низу ссылка на готовую компоненту для 1С.

Спасибо. Но мне нужно понять суть метода.

Ни хрена себе, МИФИ. Это даже в пединститутах на ЧМ дают.

Леонид Витальевич Канторович (6 января 1912, Санкт-Петербург — 7 апреля 1986, Москва) — советский математик и экономист, лауреат Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов». Один из создателей теории линейного программирования. ... В 1938 году консультировал фанерный трест по проблеме эффективного использования лущильных станков. Канторович понял, что дело сводится к задаче максимизацию линейной формы многих переменных при наличии большого числа ограничений в форме линейных равенств и неравенств. Он модифицировал метод разрешающих множителей Лагранжа для ее решения и понял, что к такого рода задачам сводится колоссальное количество проблем экономики. В 1939 году опубликовал работу «Математические методы организации и планирования производства», в которой описал задачи экономики, поддающиеся открытому им математическому методу и тем самым заложил основы линейного программирования. В годы войны преподавал в Военно-морской инженерной академии, после войны возглавлял отдел в Институте математики и механики ЛГУ. В 1949 году стал лауреатом Сталинской премии «за работы по функциональному анализу». 28 марта 1958 года избран членом-корреспондентом АН СССР (экономика и статистика). С 1958 года возглавляет кафедру вычислительной математики. Одновременно возглавлял отдел приближенных вычислений Математического института им. Стеклова Ленинградского отделения АН СССР. В середине 1948 года по распоряжению И.В. Сталина, расчетная группа Канторовича была подключена к разработке ядерного оружия.

Я - системотехник по образованию.

не находишь, что две недели - многовато для ответа? особенно для системотехника?

Просто рылся по своим темам и увидел...

Up ну ветку. Появилось несколько вопросов: 1. При иттерациях может ли получиться, что ведущий элемент равен нулю? 2. Может ли получиться, что мы не можем определить ведущую строку? Т.е. элемент в ведущем столбце равен нулю или отрицателен?

up ^ что-то ветки быстро тонут..

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

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

^

уже весь лоб расшиб с этим методом. Убиться об стену?..

Есть тексты на Паскале. Могу прислать, или переделать в 1С, но это за деньги. А что за задача? Может и бесплатно сделаю. Мой тел.: 980-2417.

Да я уже сам на 1С написал - могу прислать)

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

Добавлю о себе: 25 лет отработал в ВЦ АН СССР, поэтому о вычислительных методах представление имею.

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

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

Например, максимизировать x1 + x2 при 2*x2 <= 40, x1-x2 <=10 Явно количество решений будет не ограничено. Но на какой иттерации мы сможем это увидеть и выйти из цикла?

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

В Вашем примере решение единственное: х1 = 30, х2 = 20. Признак окончания: вектор максимизируемой функции (1,1) - линейная комбинация векторов ограничений (0,1) и (1,-1) с неотрицательными коэффициентами: (1,1) = 2*(0,1)+1*(1,-1)(это называется лемма Фаркаша).

Спасибо. В примере я действительно ошибся. Я принял за истину, что программа, которую написал я, работает правильно. Но ошибся. Сейчас проверил с помощью TORA - на 3-ей иттерации есть ответ. если изменить так: 2*x1 + x2 максимизировать. x1 - x2 <= 10 2*x1 <= 40 x1, x2 >=0 задача не имеет решения. Если "ведущий элемент" является отрицательным - является ли это достаточным условием для прекращения вычислений? Вот прикладная задача, которая встретилась мне пару лет назад: Предприятие выпускало и продавало продукцию. Причем в программе отражались только расходные накладные. Так продолжалось в течении 3-х лет. До звонка из налоговой, что их будут проверять. Мне была поставлена задача - программно сформировать документы поступления материалов и выпуска продукции, так, что бы остатков продукции на складе было достаточно для проведения реализации на каждый момент времени. Нормы расходов материалов на продукцию были одноуровневыми. Основной критерий был - минимальное отклонение от текущих запасов. Тогда я решил задачу простым перебором. Работало очень долго, но к счастью правильно. Сейчас я озадачился "правильным" путем решения задач такого рода. Для изучения выбрал книгу Хемди А. Таха "Исследование операций" - очень интересно. Но есть отдельные вопросы больше прикладного характера, на которые я не смог найти ответы. Так же интересна тема целочисленного программирования. Например метод "Ветвей и границ" подразумевает вычисления оптимального значения с помощью Симплекс метода, затем добавления в исходное задание условия для соблюдения условия целочисленности и опять вычисления с помощь симплекс метода. Будет ли такой способ решения быстрее простого перебора?

1. Да, не имеет: можно неограниченно увеличивать х2. 2. По поводу целочисленного программирования. В этот класс зачастую относят многие задачи дискретного характера, которые имеют значительную содержательную специфику. Связано это с тем, что любую задачу перебора можно сформулировать как задачу целочисленного программирования. Тут ситуация, вкратце, такова. Для переборных задач было интересно узнать, можно ли их решать за время, ограниченное полиномом по размерности. Году в 1972 (если не ошибаюсь) была работа (автора сейчас не назову, вертятся имена Карп и Кук), в которой было показано, что любая переборная задача может быть сведена (за полином по размерности) к задаче 3-выполнимости (выполнимости конъюктивной нормальной формы). Т.е. получилось так, что если можно отрешать за полином задачу 3-выполнимости, то и любую переборную задачу тоже можно за полином. Потом было показано, что практически все интересные переборные задачи (вроде коммивояжера) являются такими универсальными переборными задачами. Полиномиальных алгоритмов для универсальных задач не известно (наверное, их и нет в природе). Довольно большой список таких задач приведен в книге Гэрри и Джонсон (кажется 1982г.). При этом, некоторые переборные задачи "практически" решаются неплохо (например, задача о ранце). Кстати, симплекс-метод тоже может иметь экспоненциальное число шагов, но возможность решения задачи линейного программирования за полином показал году в 1985 мой коллега Леонид Хачиян (большой был шум), сейчас, к сожалению, покойный. Этот метод (эллипсоидов) хотя и имеет полиномиальную теоретическую оценку, на практике не используется, а используются разновидности симплекс-метода. Применительно к методу ветвей и границ (вернее сказать, схеме), то здесь скорость сильно зависит от возможности построить "хорошую" оценочную функцию. Скажем, для задачи о ранце схема работает неплохо, а для коммивояжера - неважно. Если у Вас есть переборная задача, было бы неплохо почувствовать ее характер:  к какой из универсальных задач она ближе всего. Если это не универсальная задача, то наверняка она сводится к потоку в сети.

ты только что убедился в том, что симплекс-метод не является устойчивым методом. Всего лишь.

"Будет ли такой способ решения быстрее простого перебора?" для достаточно большой размерности задачи, корифеи утверждают, что нет гарантии найти оптимум простым перебором. Не назову источник, ибо запомнил на лекции :) и на истинность не проверял-не пришлось. :)

Да нет, вполне работоспособный. Практически число шагов 3*N*M, N - число переменных, M -число ограничений. Примеры, где он "падает" - экзотические и не имеют практического значения. Вообще, важнее сама модель, насколько она адекватна решаемой задаче.

Очень интересный вопрос возник. А каким образом решать задачи с множественным ограничением? Например модернизируем немного задачу ранца: Есть n предметов по v весу каждый и полезности p каждого. Турист может нести вес T. Как вычислить набор предметов с МИНИМАЛЬНЫМ весом и МАКСИМАЛЬНОЙ полезностью, что бы они при этом укладывались в рюкзак?

не правильно выразился не с "множеством ограничений", а с множеством условий минимизации/максимизации.

(полезностью - вес) -> max

Можно ссылку на первоисточник. Или краткие мат. выкладки?

55 это я сам придумал :)

Может есть еще варианты решения таких задач?

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

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

вы случайно не олимпидную задачу решаете, год так за 2004?

процен зависит от количества дней просрочки?

угу:) ее:) Только это вроде 2003 год. Я эту задачу решил сначала просто: засунул все данные в одну ТЗ, затем упорядочил ее по Сумма/Процент/ДатаВозможнойВыплаты (точный порядок не помню, но суть в этом) и за несколько проходов по ТЗ с конца распределил долги по суммам оплат. Сейчас озадачился как решить такую задачу Симплекс-методом. Ну и помимио олимпиады бывают еще и прикладные задачи, как в . P.S. если Вы можете поделиться опытом по Олимпиадам - буду признателен за общение по ICQ.

+ ответ таким образом получился один-в один как в примере:)

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

Я за целевые функции принял платеж на каждую "ДатуВозможногоПлатежа" (ДатаОплатыПокупателя + 1). А за целевые функции сумму платежей и сумму штрафов. Если книжка в эл. виде - можно мне на мыло кинуть?

очепятка: за переменные я принял платежи на каждую дату.

ограничения такие должны быть x11    x12    x13    x14    <=1000    выплата 5 числа x21    x22    x23    x24    <=30000    выплата 7 числа x31    x32    x33    x34    <=35000    выплата 9 числа x41    x42    x43    x44    <=45000    выплата 12 числа x51    x52    x53    x54    <=60000    выплата 12 числа Д1    Д2    Д3    Д4

ЦФ x11*0+x21*0,02*2+x31*0,02*4+x41*0,02*7+x51*0,02*11+x12*0+x22*0,03*2.. ->min минимальный размер штрафа

+ еще ограничения на полную сумму выплат по каждому договору. Я все это прекрасно понимаю. У меня затык в нахождении оптимального решения, удовлетворяющему минимизации функции G1 и максимизации функции G2. А вот здесь ошибка. Процент-то по задаче сложный... А он рассчитывается как POW(1 + Процент, КоличествоДнейПросрочки) - 1.

например для x21 это будет x21*(POW(1.02, 2)-1)

+ограничения по долгу поставщику x11+x21+x31+x41+x51=20 000,00, !только здесь нужно еще убрать штрафы, т.к. х11 включает штраф

нет, если мы считаем штраф, как x21*(POW(1.02, 2)-1) - тогда штраф получается сверху.

У меня возникала еще мысль, что такая модель не учитывает проценты, набегающие на остаток долга по договору. Будет ли такое ограничение избыточным?

up

Упорно не получается решить эту задачу симплексом. Может я не с того конца пытаюсь?..

up ну еще