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

Bachelor’s degree work is devoted to the consideration of the algorithm of the simplex method and its modification, followed by an example of use. The article describes the classic approach to solving linear problems and its disadvantages. We also conducted a comparative analysis of this algorithm and its modification, which allows us to get rid of some of the shortcomings. The algorithm of the simplex method, different from the classical one, has been developed. The presented specification is implemented in software and all numerical experiments on the methods are presented. A description of alternative solutions to linear problems is also presented. The results show that the proposed algorithm is more efficient than the traditional and modified simplex method, since it spends less time solving linear programming problems of the same complexity.

• Список иллюстраций
• Список таблиц
• Введение
• 1. Обзор предметной области
  • 1.1. Постановка задачи линейного программирования
    • 1.1.1. Каноническая форма задачи линейного программирования
    • 1.1.2. Графический способ решения задачи линейного программирования
  • 1.2. Симплекс метод
  • 1.3. Алгоритм симплекс метода
  • 1.4. Реализация алгоритма
  • 1.5. Вычислительная эффективность
  • 1.6. Выводы
• 2. Модификация метода
  • 2.1. Постановка задачи
  • 2.2. Применение правила выбора направления оптимизации
  • 2.3. Отличительные особенности алгоритмов
  • 2.4. Практическая реализация алгоритма
  • 2.5. Выводы
• 3. Альтернативные решения задач линейного программирования
  • 3.1. Постановка задачи
  • 3.2. Метод декомпозиции Данцига-Вулфа
  • 3.3. Алгоритм декомпозиции
  • 3.4. Выводы
• Заключение
• Список использованных источников