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

ФАКУЛЬТЕТ “КОМПЬЮТЕРНЫЙ ИНЖИНИРИНГ”
КАФЕДРА “ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ”
ПРЕДМЕТ:
ПРОЕКТИРОВАНИЕ АЛГОРИТМОВ

на тему:

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


Выполнила: студентка 733-20
группы Гиматдинова Лилия
«____» _____________ 20____ г.
Приняла: преподавательница Порубай.О.В


Оценка: __________________
«____» _____________ 20____ г.

Фергана 2023

Оглавление

1. Введение 3
2. Общая постановка задачи 3
3. Cтандартная форма задачи 4
4. Каноническая форма задачи 4
5. Геометрическая интерпретация ЗЛП 5
6. Общий алгоритм симплексного метода ЗЛП 10
7. Литература 17

1. Введение

Задача линейного программирования (ЗЛП) состоит в определении значений упорядоченной совокупности переменных x_j, j = 1(1)n при которых линейная целевая функция достигает экстремального значения и при этом выполняются (удовлетворяются) все ограничения (они также линейные) в форме равенств или неравенств. Требуется найти план Х  = <x₁, x₂, ..., x_n>, который обеспечивает получение целевой функцией с экстремальным значением. Идеи моделей линейного планирования (программирования) впервые были высказаны и опубликованы советским математиком Л. В. Канторовичем в 1939 году в работе "математические методы организации и планирования производства". В 1975 году Л. В. Канторович и Т. Купманс получили Нобелевскую премию по экономическим наукам с формулировкой «за их вклад в теорию оптимального распределения ресурсов». В 1947 г. очень близкие идеи высказаны американским математиком Дж. Данцигом. А еще позднее стали массово появляться работы, посвященные проблемам выбора оптимальных решений в силу их исключительной важности. Признание приоритета за Л. В. Канторовичем не оспаривалось практически никогда, а после присуждения Нобелевской премии тем более. 
2. Общая постановка задачи
Задача линейного программирования (ЗЛП) состоит в определении значений упорядоченной совокупности переменных x_j, j = 1(1)n при которых линейная целевая функция достигает экстремального значения и при этом выполняются (удовлетворяются) все ограничения в форме равенств или неравенств. Требуется найти план Х  = <x₁, x₂, ..., x_n>, который обеспечивает получение целевой функцией экстремального значения

а) Если система ограничений ЗЛП обладает хотя бы одним решением, она называется совместной в противном случае несовместной; б) Допустимое множество решений ЗЛП не пусто, если система ограничений совместна; в) Множество допустимых решений ЗЛП (если оно не пусто) в общем случае является многогранным множеством. Линейная функция Q(X_<n>) называется функцией цели, целевой функцией (ЦФ), множество планов {X_<n>} удовлетворяющих системе ограничений (2) – (5), ­­- множеством допустимых решений (альтернатив) и обозначается символом R, X_<n>є Ω  Допустимый план X_<n>є Ω, доставляющий целевой функции (1) экстремальное значение, называется оптимальным. Задача в форме (1) – (5) представляет общую задачу линейного программирования.
3. Cтандартная форма задачи
Если все ограничения задачи заданы в виде строгих равенств и на переменные величины наложено условие неотрицатаельности x_j ≥0, j = 1(1)n, то такую формулировку называют стандартной:

Экстремумы функций в общем случае связаны простыми соотношениями