Основные теоретические положения симплексного метода при решении задач линейного программирования

 

От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 6.

От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на 4.

От элементов строки 4 отнимает соответствующие элементы строки 1, умноженные на 50.

От элементов строки 6 отнимает соответствующие элементы строки 1, умноженные на -1.

От элементов строки L отнимает соответствующие элементы строки 1, умноженные на -100.

 

базисные  переменные	x1	x2	x3	x4	x5	x6	x7	x8	свободные  члены
x8	0	0	1     40	0	0	0	1     2	1	100
x4	0	0	- 3     20	1	0	0	1	0	300
x5	0	0	- 1     10	0	1	0	2	0	200
x6	0	0	- 5     4	0	0	1	5	0	1000
x1	1	0	0	0	0	0	- 1	0	0
x2	0	1	1     40	0	0	0	1     2	0	100
L	0	0	5     2	0	0	0	- 30	0	10000

 

X ₁ = (0 , 100 , 0 , 300 , 200 , 1000 , 0 , 100)

L =  10000   -5/2 x₃ + 30 x₇

Значение функции L для  данного решения: L (X ₁) = 10000

Шаг 4

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

За ведущую выберем  строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Обратите внимание, что  отношение мы вычисляем только для  положительных элементов столбца 7.

 

базисные  переменные	x1	x2	x3	x4	x5	x6	x7	x8	свободные  члены	отношение
x8	0	0	1     40	0	0	0	1     2	1	100	200
x4	0	0	- 3     20	1	0	0	1	0	300	300
x5	0	0	- 1     10	0	1	0	2	0	200	100
x6	0	0	- 5     4	0	0	1	5	0	1000	200
x1	1	0	0	0	0	0	- 1	0	0	-
x2	0	1	1     40	0	0	0	1     2	0	100	200
L	0	0	5     2	0	0	0	- 30	0	10000	-

 

Разделим элементы строки 3 на 2.

 

базисные  переменные	x1	x2	x3	x4	x5	x6	x7	x8	свободные  члены	отношение
x8	0	0	1     40	0	0	0	1     2	1	100	200
x4	0	0	- 3     20	1	0	0	1	0	300	300
x5	0	0	- 1     20	0	1     2	0	1	0	100	100
x6	0	0	- 5     4	0	0	1	5	0	1000	200
x1	1	0	0	0	0	0	- 1	0	0	-
x2	0	1	1     40	0	0	0	1     2	0	100	200
L	0	0	5     2	0	0	0	- 30	0	10000	-

 

От элементов строки 1 отнимает соответствующие элементы строки 3 .

От элементов строки 2 отнимает соответствующие элементы строки 3 .

От элементов строки 4 отнимает соответствующие элементы строки 3, умноженные на 5.

От элементов строки 5 отнимает соответствующие элементы строки 3, умноженные на -1.

От элементов строки 6 отнимает соответствующие элементы строки 3 .

От элементов строки L отнимает соответствующие элементы строки 3, умноженные на -30.

 

базисные  переменные	x1	x2	x3	x4	x5	x6	x7	x8	свободные  члены
x8	0	0	1     20	0	- 1     4	0	0	1	50
x4	0	0	- 1     10	1	- 1     2	0	0	0	200
x7	0	0	- 1     20	0	1     2	0	1	0	100
x6	0	0	- 1	0	- 5     2	1	0	0	500
x1	1	0	- 1     20	0	1     2	0	0	0	100
x2	0	1	1     20	0	- 1     4	0	0	0	50
L	0	0	1	0	15	0	0	0	13000

 

X ₂ = (100 , 50 , 0 , 200 , 0 , 500 , 100 , 50)

L =  13000 - x₃ -15 x₅

Значение функции L для  данного решения: L (X ₂) = 13000

Учитывая, что все x _i 0, по условию задачи, наибольшее значение функции L равно свободному члену 13000, т.е. мы получили оптимальное решение.

Теперь можем записать ответ.

Ответ:

X _опт = (100 , 50 , 0 , 200 , 0 , 500 , 100 , 50)

Значение функции: L = 13000

 

 

ЗАКЛЮЧЕНИЕ

 

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

Задачи линейного программирования решаются несколькими методами:

1. графический метод;
2. симплекс-метод;
3. двойственный симплекс-метод.

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

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

 

 

СПИСОК ЛИТЕРАТУРЫ

 

1. Хемди А. Таха «Введение в исследование операций». — 7-е изд. — М.: «Вильямс», 2007.
2. Акулич И.Л. «Математическое программирование в примерах и задачах». — М.: Высшая школа, 1986.
3. Томас Х. Кормен и др. «Алгоритмы: построение и анализ». — 2-е изд. — М.: «Вильямс», 2006.
4. Большакова И. В., Кураленко М. В. «Линейное программирование. Учебно-методическое пособие к контрольной работе».
5. Барсов А. С. «Что такое линейное программирование?», «Гостехиздат», 1959.
6. Карманов В. Г. «Математическое программирование». — 3-е изд. — М.: «Наука», 1986.
7. Данциг Джордж Бернард «Воспоминания о начале линейного программирования»
8. Гилл Ф., Мюррей У., Райт М. «Практическая оптимизация». Пер. с англ. — М.: «Мир», 1985.
9. Максимов Ю. А. «Алгоритмы линейного и дискретного программирования». — М.: МИФИ, 1980.
10. Плотников А. Д. «Математическое программирование». — 2006
11. Е.В. Шикин, А.Г. Чхартишвили «Математические методы и модели в управление». – М.: Дело, 2002 – 440 с.