Решение задачи нелинейного программирования

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

Цель работы: с помощью сформулированной задачи нелинейного программирования проверить работу нескольких онлайн-калькуляторов и проанализировать результат.

Задание: Придумать задачу, решаемую симплекс-методом. Эта задача должна быть решена при помощи программного обеспечения (любого) или с использованием онлайн-калькулятора. Для начала ПО должно быть протестировано, т. е. необходимо проверить правильность вычислений на уже решенном примере. Желательно найти несколько видов программ, отличающихся реализуемым алгоритмом, и сравнить их между собой. В отчете предоставить формулировку исходной задачи и ее решение с использованием ПО (подробно). Укажите, какую программу или интернет-ресурс вы считаете наиболее подходящим для решения подобных задач и почему.

Выполнение.

Было найдено три онлайн калькулятора решающих ЗЛП симплекс методом:

• • http://www.math.u-gu.ru/index.php?id=46
• • http://www.mathzone.ru/online/1/
• • http://www.kontrolnaya-rabota.ru/s/equal-many/simplex-method.HYPERLINK «http://www.kontrolnaya-rabota.ru/s/equal-many/simplex-method.ru» ru задача онлайн калькулятор симплекс

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

Есть три типа злаков: овсе, кукуруза и рис. Необходимо составить 1 кг комбикорма так, чтобы в нем содержалось не менее 125 ккал, не менее 2 грамм витамина С и цена была минимальной. Все необходимые данные предоставлены в таблице ниже.

Оптимальным решением данной задачи является x₁=0, x₂=1/3, x₃=2/3.

Решение это задачи в первом онлайн калькуляторе:

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

Проверим второй онлайн калькулятор:

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

Во втором калькуляторе было предложено добавить сразу четыре дополнительных переменных x₄, x₅, x₆, x₇.После этого выданные калькулятором результаты были сравнены с «истинными» результатами решения.

Получается, что ответы не сходятся. Данный калькулятор не подходит для решения ЗЛП симплекс методом.

Проверим третий онлайн калькулятор:

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

Теперь используя третий онлайн калькулятор решим задачу, придуманную ранее.

Есть три вида провайдеров: Домолинк, Зеленая точка и МТС. Скорость скачивания, цена и бонус (если есть 1, если нет 0) указаны в таблице.

Требуется выбрать провайдер, скорость скачивания которого не менее10 Мб/с, юонус обязателен, а, а цена не менее 490 руб/м.

Решение.

L = 650*x1 + 490*x2 + 350*x3 при условиях:

10*x1 + 100*x2 + 10*x3 >= 10.

x1 + x2 + x3 >= 1.

650*x1 + 490*x2 + 350*x3 >= 490.

Избавимся от неравенств в уравнениях.

10*x1 + 100*x2 + 10*x3 — x4 + z1 = 10.

x1 + x2 + x3 — x5 + z2 = 1.

650*x1 + 490*x2 + 350*x3 — x6 + z3 = 490.

Из уравнений выражаем искусственные переменные:

z1 = -10*x1 — 100*x2 — 10*x3 + x4 + 10,.

z2 = -x1 — x2 — x3 + x5 + 1,.

z3 = -650*x1 — 490*x2 — 350*x3 + x6 + 490.

W = -z1 — z2 — z3.

W = 661*x1 + 591*x2 + 361*x3 — x4 — x5 — x6 — 501.

Начальная симплекс таблица:

x1 x2 x3 x4 x5 x6 z1 z2 z3.

z1 10 100 10 -1 0 0 1 0 0 10 ;

z2 1 1 1 0 -1 0 0 1 0 1 ;

z3 650 490 350 0 0 -1 0 0 1 490 ;

G 650 490 350 0 0 0 0 0 0 0 ;

W -661 -591 -361 1 1 1 0 0 0 -501 ;

Ответ: найдено оптимальное решение данной задачи.

Наиболее оптимальным, подходящий по всем параметрам, оказался провайдер Домолинк.

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