Написание курсовой работы по симплекс-методу: теория, алгоритм и практическая реализация

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

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

1. Изучить теоретические основы линейного программирования и математическую модель симплекс-метода.
2. Детально описать пошаговый алгоритм решения задач симплекс-методом.
3. Выполнить постановку практической задачи и перевести ее в формальную математическую модель.
4. Решить поставленную задачу с помощью симплекс-таблиц, подробно комментируя каждую итерацию.
5. Проанализировать полученные результаты и дать им экономическую интерпретацию.
6. Рассмотреть потенциальные сложности метода и его реальные области применения.

Структура работы полностью соответствует этим задачам. Она включает в себя введение, три главы, раскрывающие теоретические, алгоритмические и практические аспекты метода, а также заключение с основными выводами.

Глава 1. Теоретические основы, на которых строится решение

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

Любая задача ЛП состоит из трех ключевых компонентов:

• Переменные решения — неизвестные величины, которые нам нужно определить (например, объемы производства разных товаров).
• Целевая функция — линейное выражение, которое связывает переменные и которое мы стремимся максимизировать (например, прибыль) или минимизировать (например, издержки).
• Система ограничений — набор линейных уравнений и/или неравенств, которые описывают условия задачи (например, ограниченность сырья или рабочего времени).

Хотя идеи оптимизации существовали и ранее, современное линейное программирование и его основной метод решения были разработаны американским математиком Джорджем Данцигом в 1947 году. Эта разработка стала настоящим прорывом, позволившим решать сложные экономические и военные задачи планирования.

Геометрическая интерпретация метода помогает интуитивно понять его суть. Система ограничений определяет на плоскости (или в многомерном пространстве) некую область допустимых решений, которая представляет собой выпуклый многогранник (политоп). Важнейшее свойство задач ЛП заключается в том, что оптимальное решение всегда находится в одной из вершин этого многогранника. Симплекс-метод, по сути, представляет собой «умный» способ перемещения по этим вершинам, на каждом шаге улучшая значение целевой функции, пока не будет найдена оптимальная вершина.

Для удобства вычислений задачи ЛП приводят к стандартным формам. Каноническая форма — это система линейных уравнений с неотрицательными переменными, к которой задача приводится путем введения дополнительных переменных. Эти переменные превращают неравенства в равенства и имеют ясный экономический смысл — например, остаток неиспользованного ресурса.

1.2. Сущность и математическая модель симплекс-метода

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

В основе метода лежат ключевые понятия:

• Опорное решение: любое решение системы ограничений.
• Допустимое решение: опорное решение, в котором все переменные неотрицательны (xᵢ ≥ 0).
• Базисное решение: решение, в котором часть переменных (базисные) выражена через остальные (свободные), приравненные к нулю. Каждое такое решение соответствует одной из вершин многогранника ограничений.

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

• Базисные переменные: переменные, находящиеся в текущем базисе (составляют основу решения на данной итерации).
• Свободные члены: значения базисных переменных и целевой функции.
• Коэффициенты при переменных: все коэффициенты системы ограничений.
• Индексная строка (строка Z): строка, содержащая оценки коэффициентов целевой функции, которая служит для проверки решения на оптимальность.

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

Глава 2. Пошаговый алгоритм, который приводит к решению

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

1. Шаг 0: Приведение задачи к канонической форме. Все ограничения-неравенства типа «≤» преобразуются в равенства путем добавления новых неотрицательных (балансовых) переменных. Целевая функция переносится в общую систему с противоположным знаком.
2. Шаг 1: Построение первой симплекс-таблицы. Составляется начальная таблица. В качестве первого базиса обычно выбираются введенные на предыдущем шаге балансовые переменные. Это соответствует исходной точке (часто — началу координат), с которой начинается поиск.
3. Шаг 2: Проверка на оптимальность. Анализируется индексная строка (Z) таблицы. Если все коэффициенты в ней (для задачи на max) неотрицательны, то текущее решение является оптимальным. Алгоритм завершен. Если есть отрицательные коэффициенты — переходим к следующему шагу.
4. Шаг 3: Определение ведущего столбца (входящая переменная). Среди отрицательных коэффициентов индексной строки выбирается наибольший по модулю. Столбец, в котором он находится, становится ведущим. Переменная, соответствующая этому столбцу, будет введена в базис на следующей итерации, так как она обеспечивает наибольший прирост целевой функции.
5. Шаг 4: Определение ведущей строки (выходящая переменная). Для каждого положительного элемента ведущего столбца вычисляются симплекс-отношения: значение из столбца свободных членов делится на соответствующий элемент из ведущего столбца. Строка, для которой это отношение минимально, выбирается как ведущая. Переменная, стоявшая в базисе в этой строке, будет выведена из базиса. Элемент, стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.
6. Шаг 5: Пересчет симплекс-таблицы. Строится новая таблица. Базисная переменная меняется. Все элементы новой таблицы пересчитываются по специальным правилам (например, по «правилу прямоугольника» или методом Жордана-Гаусса).
7. Шаг 6: Возврат к Шагу 2. С новой таблицей мы повторяем процедуру: проверяем ее на оптимальность и, если она не достигнута, продолжаем итерации до тех пор, пока условие оптимальности не будет выполнено.

Глава 3. Практическая реализация. Как поставить задачу и подготовить данные

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

Формулировка прикладной задачи:

Мебельная фабрика производит две модели продукции: столы и стулья. Для производства одного стола требуется 3 единицы древесины и 1 час рабочего времени. Для производства одного стула требуется 1 единица древесины и 2 часа рабочего времени. Прибыль от реализации одного стола составляет 8 денежных единиц, а от одного стула — 5 денежных единиц. На складе имеется 150 единиц древесины, а общий фонд рабочего времени составляет 100 часов. Необходимо составить такой производственный план, чтобы прибыль фабрики была максимальной.

Теперь формализуем эту задачу.

1. Идентификация переменных. Обозначим за x₁ — количество столов, а за x₂ — количество стульев, которые планируется произвести.
2. Построение целевой функции. Наша цель — максимизировать общую прибыль (Z). Она складывается из прибыли от продажи всех столов и всех стульев.
   
   Z = 8x₁ + 5x₂ → max
3. Формализация ограничений. У нас есть два ключевых ресурса: древесина и рабочее время.
   • Ограничение по древесине: На все столы (x₁) и стулья (x₂) уйдет 3x₁ + 1x₂ единиц древесины. Этот объем не может превышать запасы на складе.
     
     3x₁ + x₂ ≤ 150
   • Ограничение по времени: На производство потребуется 1x₁ + 2x₂ часов. Этот объем не может превышать доступный фонд времени.
     
     x₁ + 2x₂ ≤ 100
   • Условие не отрицательности: Количество продукции не может быть отрицательным.
     
     x₁ ≥ 0, x₂ ≥ 0

Итоговая математическая модель задачи выглядит так:

Z = 8x₁ + 5x₂ → max

при ограничениях:

3x₁ + x₂ ≤ 150

x₁ + 2x₂ ≤ 100

x₁, x₂ ≥ 0

Для внесения в симплекс-таблицу приведем модель к каноническому виду, введя балансовые переменные x₃ и x₄:

3x₁ + x₂ + x₃ = 150

x₁ + 2x₂ + x₄ = 100

Z — 8x₁ — 5x₂ = 0

Теперь все готово для начала итерационного процесса вычислений.

3.2. Итерационный процесс решения, представленный в симплекс-таблицах

На основе полученной канонической модели строим первую симплекс-таблицу. В начальном базисе — наши балансовые переменные x₃ и x₄, которые показывают остатки ресурсов. Значения производственных переменных x₁ и x₂ равны нулю.

Таблица 1 (Начальная итерация)

Проводим анализ таблицы согласно алгоритму:

1. Проверка на оптимальность: В строке Z есть отрицательные элементы (-8, -5). Решение не оптимально.
2. Выбор ведущего столбца: Выбираем наибольший по модулю отрицательный элемент: -8. Ведущий столбец — x₁. Будем вводить в план столы.
3. Выбор ведущей строки: Считаем симплекс-отношения: для первой строки 150 / 3 = 50; для второй 100 / 1 = 100. Выбираем минимальное: 50. Ведущая строка — первая (переменная x₃). Она покинет базис.
4. Ведущий элемент: На пересечении столбца x₁ и строки x₃ стоит число 3.

Теперь выполняем пересчет всех ячеек и получаем новую таблицу.

Таблица 2 (Итерация 1)

Повторяем анализ для новой таблицы:

1. Проверка на оптимальность: В строке Z остался отрицательный элемент (-7/3). Решение все еще не оптимально.
2. Выбор ведущего столбца: Отрицательный элемент только один, он и определяет ведущий столбец. Ведущий столбец — x₂. Будем вводить в план стулья.
3. Выбор ведущей строки: Считаем отношения: для первой строки 50 / (1/3) = 150; для второй 50 / (5/3) = 30. Выбираем минимальное: 30. Ведущая строка — вторая (переменная x₄).
4. Ведущий элемент: На пересечении стоит число 5/3.

Снова производим пересчет и получаем финальную таблицу.

Таблица 3 (Финальная итерация)

Финальный анализ:

1. Проверка на оптимальность: В строке Z все элементы (8/5, 7/5) неотрицательны. Решение оптимально! Алгоритм завершен.

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

3.3. Анализ полученного решения и его экономическая интерпретация

Получение финальной симплекс-таблицы — это не конец, а начало самой важной части практической работы: интерпретации результатов. Числа, которые мы получили, имеют конкретный экономический смысл.

1. Формулировка оптимального плана.
Смотрим на столбец свободных членов в финальной таблице. Переменная x₁ (столы) вошла в базис и ее значение равно 40. Переменная x₂ (стулья) также в базисе со значением 30.

Оптимальный план производства: необходимо произвести 40 столов и 30 стульев.

2. Расчет максимального значения целевой функции.
Значение в строке Z и столбце свободных членов показывает итоговую прибыль. Z = 470.

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

3. Анализ теневых цен (двойственных оценок).
Это продвинутый анализ, который показывает ценность ресурсов. Смотрим на значения в Z-строке в столбцах, которые соответствуют изначально введенным балансовым переменным (x₃ и x₄).

• Коэффициент для x₃ равен 8/5 (или 1.6). Это теневая цена древесины. Она означает, что каждая дополнительная единица древесины (сверх имеющихся 150) способна увеличить общую прибыль на 1.6 денежных единиц.
• Коэффициент для x₄ равен 7/5 (или 1.4). Это теневая цена рабочего времени. Каждый дополнительный час времени увеличит прибыль на 1.4 денежных единиц.

4. Анализ дефицитных и избыточных ресурсов.
Поскольку обе балансовые переменные (x₃ и x₄) в итоговом решении равны нулю (они не в базисе), это означает, что оба ресурса — и древесина, и рабочее время — являются дефицитными. Они использованы полностью, без остатка.

(Проверка: 3*40 + 1*30 = 120 + 30 = 150; 1*40 + 2*30 = 40 + 60 = 100).

Выводы по практической части: Симплекс-метод позволил не только найти оптимальный объем выпуска продукции (40 столов, 30 стульев) для получения максимальной прибыли (470 д.е.), но и определить, какие ресурсы наиболее ценны для предприятия. Анализ теневых цен показывает, что руководству выгоднее инвестировать в увеличение запасов древесины, так как это даст больший прирост прибыли.

Как анализировать потенциальные сложности, включая вырожденность и зацикливание

Хотя на практике симплекс-метод работает очень эффективно, хорошая курсовая работа должна демонстрировать понимание и его потенциальных «узких мест». Существуют особые случаи, которые могут усложнить процесс решения.

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

2. Проблема зацикливания (cycling).
Это редкий на практике, но теоретически возможный феномен, когда алгоритм начинает циклически повторять одну и ту же последовательность симплекс-таблиц, не сдвигаясь с места и не достигая оптимального решения. Геометрически это означает «топтание» на одной вырожденной вершине. Для предотвращения зацикливания существуют специальные модификации алгоритма, например, правило Блэнда, которое предписывает более строгий порядок выбора входящих и выходящих переменных, гарантируя выход из цикла.

3. Другие особые случаи:

• Отсутствие решения: Если в задаче используются искусственные переменные (для ограничений типа «≥» или «=») и в финальном оптимальном решении хотя бы одна из них осталась в базисе с ненулевым значением, это означает, что система ограничений противоречива и допустимых решений не существует.
• Неограниченность целевой функции: Если на каком-то шаге мы выбрали ведущий столбец, но в нем нет ни одного положительного элемента, это сигнализирует о том, что целевая функция неограниченно возрастает в допустимой области. Решения нет, так как Z может стремиться к бесконечности.

Анализ таких ситуаций показывает глубокое понимание не только механики, но и математических основ метода.

Области применения симплекс-метода за пределами учебной аудитории

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

• Производство и логистика: Это классическая область применения. Метод используется для оптимизации производственных планов (как в нашем примере), управления запасами, оптимального раскроя материалов (минимизация отходов) и решени�� «задачи о диете» (составление рациона с минимальной стоимостью при соблюдении питательных норм).
• Транспортные задачи: Поиск оптимальных маршрутов для доставки товаров со складов потребителям с целью минимизации общих транспортных расходов. Это отдельный класс задач ЛП, который эффективно решается симплекс-методом.
• Финансовое планирование: Формирование оптимального инвестиционного портфеля. Инвестор стремится максимизировать доходность при заданных ограничениях на уровень риска и структуру активов.
• Составление расписаний: Оптимизация графиков работы персонала, расписаний авиарейсов, движения городского транспорта или учебных занятий с целью максимально эффективного использования ресурсов и удовлетворения всех требований.
• Энергетика: Оптимизация загрузки электростанций для удовлетворения спроса на энергию при минимальных затратах.

Эти примеры показывают, что освоение симплекс-метода открывает двери к решению множества практически значимых задач.

Заключение. Формулировка выводов и оформление списка литературы

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

На основе проделанной работы можно сформулировать следующие главные выводы:

1. Были изучены теоретические основы линейного программирования, включая его основные компоненты, геометрическую интерпретацию и формы представления задач. Разобрана математическая модель симплекс-метода, основанная на итерационном переходе по базисным решениям.
2. Был описан четкий пошаговый алгоритм решения задач симплекс-методом, который служит практическим руководством для выполнения вычислений.
3. Была успешно решена практическая задача по оптимизации производственного плана. В ходе решения был продемонстрирован процесс перевода текстовой задачи в математическую модель, итерационные вычисления в симплекс-таблицах и, что наиболее важно, проведен глубокий экономический анализ полученных результатов, включая оптимальный план, максимальную прибыль и теневые цены ресурсов.
4. Рассмотрены потенциальные сложности метода, такие как вырожденность и зацикливание, а также его многочисленные применения в реальной экономике.

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

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

Пример оформления списка литературы (согласно ГОСТ 7.0.5-2008):

1. Акулич, И. Л. Математическое программирование в примерах и задачах : учеб. пособие / И. Л. Акулич. — Москва : Высшая школа, 2011. — 319 с.
2. Вентцель, Е. С. Исследование операций: задачи, принципы, методология / Е. С. Вентцель. — 5-е изд., стер. — Москва : Дрофа, 2018. — 208 с.
3. Таха, Х. А. Введение в исследование операций / Х. А. Таха ; пер. с англ. — 8-е изд. — Москва : Вильямс, 2016. — 1095 с.
4. Красс, М. С. Математика для экономистов / М. С. Красс, Б. П. Чупрынов. — Санкт-Петербург : Питер, 2010. — 464 с.
5. Симплекс-метод [Электронный ресурс] // Википедия. Свободная энциклопедия. — Режим доступа: https://ru.wikipedia.org/wiki/Симплекс-метод (дата обращения: 14.08.2025).

Список использованной литературы

1. Лищенко «Линейное и нелинейное программирование», М. 2003
2. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М. 2000
3. Мину М. Математическое программирование. Теория и алгоритмы. М. 2004