Таблицы решения задач

На данной странице установлена программа на языке Java апплеткоторая решает on-line онлайн ЛП бесплатно. Для решения задачи ЛП применен. В окне Java Control Panel выбираем вкладку Security Безопастность нажимаем кнопку Edit Site List, кнопку add и вставляем в свободное поле путь к этой страницы из адресной таблицы решения задач браузера. Далее нажимаем кнопки ОК, после этого перезагружаем компьютер. Для запуска апплета нажмите на кнопку "Simplex". Если над этой строкой не видна кнопка "Simplex", то на компьютере не установлена Java. После нажатия на кнопку таблицы решения задач Simplex » выводится первое окно для ввода числа переменных и числа ограничений задачи на симплекс-метод. После нажатия на кнопку «Решить» выводится окно с результатами решения задачи на симплекс-метод. Окно состоит из двух частей, в верхней части находится текстовое поле, содержащее описание приведения исходной задачи к канонической форме, которая используется для составления первой симплекс-таблицы. В нижней части окна в панели со вкладками расположены симплекс-таблицы каждой итерации с небольшим текстовым полем внизу с указанием разрешающего столбца, разрешающей строки и другой информации, что делает программу обучающей. Во вкладке с оптимальной последней таблицей в текстовом поле приведено полученное оптимальное решение задачи. Замеченные ошибки и комментарии по работе апплета присылайте на или звоните 8 962 700 77 06, за что мы таблицы решения задач Вам очень благодарны. Программа М-метод Программа для решения транспортной задачи Здесь приведено ручное не апплетом решение двух задач симплекс-методом аналогичным решению апплетом с таблицы решения задач объяснениями для того, чтобы понять алгоритм решения задач. Запишем задачу в канонической форме, т. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: -система ограничений должна быть системой уравнений с базисом; -свободные члены всех уравнений в системе должны быть неотрицательны. Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу Итерация 0т. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т. Для этого надо выбрать разрешающий столбец, т. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке в задаче на максимум — в начальной итерации это столбец x 2 коэффициент -6. Затем выбирается разрешающая строка, т. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца столбец «Отношение» — в начальной итерации это строка s 3 коэффициент 20. Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации переменная x 2 заменит в базисе s 3. Заметим, что в z-строке отношение не ищется, там ставится таблицы решения задач " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение таблицы решения задач бесконечно. Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный с единицей вместо разрешающего элемента и нулями вместо остальных элементов. Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент он равен 1 таблицы решения задач данном случае этой таблицы, получим строку x 2 в таблице «Итерации 1». Строку x 2 таблицы "Итерации 1" мы получили таблицы решения задач 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом: 2 Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке z-строке в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и таблицы решения задач эту строку с первой строкой z таблицы решения задач строкой таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом. На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы таблицы решения задач 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0. На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 таблицы решения задач таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0. Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица таблицы решения задач всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы. Получили, так называемую, М-задачу: Данная система является системой с базисом, в которой R 1, R 2 и x 4 базисные переменные, а x 1, x 2 и x 3 свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу: итерация 0 - В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными R с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в таблицы решения задач. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы в базисе нет искусственных переменных разрешающий столбец будет определяться по z-строке, таблицы решения задач и в задаче с начальным базисом. В данной таблице разрешающий столбец х 2, он выбран по наибольшей по модулю отрицательной оценке -7. Разрешающая строка R 2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и таблицы решения задач задаче без искусственных таблицы решения задач. Это значит, что на следующей итерации переменная х 2 из свободной перейдет в базисную, а переменная R 2 из таблицы решения задач — в свободную. Запишем следующую симплекс-таблицу: итерация 1 - Разрешающий столбец х 1, разрешающая строка R 1, R 1 выходит из базиса, x 1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет: итерация 2 - Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R 1, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Особые случаи применения симплекс-метода 1 Когда прямая если рассматривается двухмерная задача линейного программирования, а в общем случае гиперплоскостьпредставляющая целевую функцию параллельна прямой гиперплоскостисоответствующей одному из неравенств-ограничений которое в точке оптимума выполняется, как точное равенство целевая функция принимает одно и тоже оптимальное значение на некотором множестве точек границы области допустимых решений. Эти решения называются таблицы решения задач оптимальными решениями. Наличие альтернативных решений можно определить по оптимальной симплекс-таблице. Если в z-строке оптимальной таблицы есть нулевые коэффициенты небазисных переменных, то есть альтернативные решения. Для других типов ограничений использются искусственные переменные. Если задача имеет решение, то в оптимальной таблице в базисе таблицы решения задач искусственных переменных R i. Если они там есть, то задача не имеет решений.