X Международная студенческая научная конференция Студенческий научный форум - 2018

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

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

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

Вычисления следует вести по следующей схеме:

1) отыскивается начальный план, где основные переменные этого плана выражаются через неосновные;

2) выражается значение минимизируемой функции L(x) через неосновные переменные x_j;

3) выбирается та из неосновных переменных, введение которой в план способно улучшить L(x);

4) определяется, какая из основных переменных должна быть при этом исключена из плана и сделана неосновной;

5) вновь вводимая в план переменная выражается через переменную, выводимую из плана, и другие неосновные переменные;

6) все остальные основные переменные и значение минимизируемой функции L(x) выражаются через новые неосновные переменные.

Впервые основы линейного программирования были изложены в 1939 году в работе Леонида Витальевича Канторовича «Математические методы организации и планирования производства», в которой сформулирован новый класс экстремальных задач с ограничениями и разработан эффективный метод их решения.

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

Общая задача линейного программирования была впервые поставлена в 1947 году Джорджом Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. Группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием Project SCOOP. Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе 1952 года.

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

Библиографический список

1. Информатика : Энциклопедический словарь для начинающих / под ред. Д.А. Поспелова. М. : Наука, 1994.

2. Самарский А.А. Компьютеры, модели, вычислительный эксперимент / А.А. Самарский. М : Наука, 1988.

3.Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.

4.Хемди А. Таха. Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8.

Код для цитирования: Скопировать