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


Download 490.31 Kb.
bet1/11
Sana18.06.2023
Hajmi490.31 Kb.
#1585862
TuriЗадача
  1   2   3   4   5   6   7   8   9   10   11
Bog'liq
Лиля-1




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

на тему:



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


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


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

Фергана 2023

Оглавление


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

1. Введение


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

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

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


Download 490.31 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8   9   10   11




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling