Решение транспортных задач симплекс методом онлайн

Программа М-метод скачать Программа для решения транспортной задачи скачать Здесь приведено ручное не апплетом решение двух задач симплекс-методом аналогичным решению апплетом с подробными объяснениями для того, чтобы понять алгоритм решения задач. Запишем задачу в канонической форме, то есть ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:

На данной странице установлена программа на языке Java апплет , которая решает on-line онлайн задачу линейного программирования ЛП бесплатно. Для решения задачи ЛП применен симплекс-метод. Для работы апплета реализующего симплекс-метод на вашем компьютере должна быть установлена Java, ссылка для установки http: В окне Java Control Panel выбираем вкладку Security Безопастность нажимаем кнопку Edit Site List, кнопку add и вставляем в свободное поле путь к этой страницы из адресной строки браузера.

Для улучшения решения перейдем к следующей итерации , получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец , то есть переменную, которая войдет в базис на следующей итерации. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке в задаче на максимум — в начальной итерации это столбец x 2 коэффициент Затем выбирается разрешающая строка , то есть переменная, которая выйдет из базиса на следующей итерации.

Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы. Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис. Получили, так называемую, М-задачу:. Данная система является системой с базисом, в которой R 1 , R 2 и x 4 базисные переменные, а x 1 , x 2 и x 3 свободные переменные, свободние члены всех уравнений неотрицательны.

Далее нажимаем кнопки ОК, после этого перезагружаем компьютер. Для запуска апплета нажмите на кнопку "Simplex". Если над этой строкой не видна кнопка "Simplex", то на компьютере не установлена Java. Замеченные ошибки и комментарии по работе апплета присылайте на mathelp6 gmail. Программа для решения транспортной задачи скачать. Здесь приведено ручное не апплетом решение двух задач симплекс-методом аналогичным решению апплетом с подробными объяснениями для того, чтобы понять алгоритм решения задач.

Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу Итерация 0 , то есть таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Решение не является оптимальным, так как в z — строке есть отрицательные коэффициенты.

В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно. Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный с единицей вместо разрешающего элемента и нулями вместо остальных элементов. Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом: На месте -6 в первой строке z-строке в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1".

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

Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 и сложим эту строку с первой строкой z - строкой таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 В столбце x 2 появился ноль 0 , цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом. На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 В столбце х 2 получен необходимый 0.

Это значит, что на следующей итерации переменная х 2 из свободной перейдет в базисную, а переменная R 2 из базисной — в свободную. Разрешающий столбец х 1 , разрешающая строка R 1 , R 1 выходит из базиса, x 1 входит в базис. Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R 1 , который не влияет на оптимальность, когда искусственные переменные вышли из базиса.

Когда строка "Оценка" выйдет из таблицы в базисе нет искусственных переменных разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х 2 , он выбран по наибольшей по модулю отрицательной оценке Разрешающая строка R 2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных.

Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0. Например для z -строки имеем:. Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем. Разрешающий столбец х 1 , разрешающая строка s 2 , s 2 выходит из базиса, х 1 входит в базис.

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

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации переменная x 2 заменит в базисе s 3. Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ".

На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 и сложим эту строку с s 2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 В столбце х 2 получен нужный 0.

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

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

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