Курсовая работа (т): Системы линейных неравенств
Дана линейная функция
и система неравенств (ограничений)
Причем
Из всех неотрицательных решений системы 
найти
такое, которое максимизирует линейную функцию 
Пример : Максимизировать форму
при выполнении ограничений
и при
Переходим к таблице
1
-2
-2
-1
-2
3
-3
2
6
3
-3
-2
6
0
2
-2
2
z =
-1
-1
-1
0
Переменные Первая строка содержит отрицательный свободный
член. Из отрицательных коэффициентов этой строки выбираем -1. Сделав шаг
модифицированного жорданова исключения, получим таблицу
1
2
2
-1
2
-1
-7
2
2
7
1
-2
10
4
6
-2
6
z =
1
1
-1
2
не содержащую уже отрицательных свободных
членов, и можем перейти к отысканию оптимального решения. Над отрицательным
коэффициентом z- строки -1 находится лишь один положительный коэффициент 2. Его
делаем разрешающим. После шага модифицированного жорданова исключения получим
1
3/2
-3/2
1/2
3
-1/2 1/2
1
6
-6
1
12
3
-1
1
8
z =
1/2
-5/2
1/2
3
Над отрицательным коэффициентов z- строки -5/2
нет положительных, поэтому линейная форма может принимать сколь угодно большое
значение.
Для решения минимизации формы достаточно решить
задачу максимизации полученной формы при ограничениях (2.2) и z = - max Z
Алгоритм симплекс-метода монотонный, т.е. каждый
шаг монотонно приближает нас к искомому значению.
2.3 Практическое применение симплекс метода
Основную задачу линейного программирования можно
экономически интерпретировать следующим образом.
Пусть для производства некоторого продукта
имеется n различных технологий. При этом пусть используется m ингредиентов
(различные виды сырья и прочие производственные факторы), причем по j-й
технологии расходуется в единицу времени Список литературы
линейный неравенство симплекс
решение
Зуховицкий
С.И. и Авдеева Л.И. Линейное и выпуклое программирование, М. Наука 1967 - 460с.
Куликов
Л.Я. Алгебра и теория чисел: Учебное пособие для педагогических институтов. -
М.: Высшая школа, 1979. - 559 с.
Новоселов,
С.И. Специальный курс элементарной алгебры [Текст]/С.И.Новоселов. 6-е изд. -
М.: Высшая школа,1962.-564с.
=
=
=
=
неотрицательны,
поэтому мы их не исключаем.
=
=
=
=
=
=
=
=
единиц
i-го ингридиента, общий запас которого равен 
,
и производится 
единиц продукта.
Пусть 
-
время, в течении которого производство ведется по j-й технологии. Тогда при
«плане» 
будет
произведено 
единиц продукта и
израсходовано 
единиц i-го
ингредиента. Естественно возникает задача: отыскать оптимальное сочетание.
Математическая модель этой задачи и будет основная задача линейного
программирования: максимизировать линейную форму.