Основные теоретические сведения

Общая идея симплекс-метода. Геометрическая иллюстрация

Симплекс-метод основан на направленном переходе от одного опорного плана к другому, при котором значение целевой функции возрастает. Такой переход возможен, если уже известен какой-нибудь исходный опорный план.

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

Симплекс-метод решения задачи линейного программирования не следует путать с симплекс-методом решения задачи безусловной минимизации.

Рассмотрим применение симплекс-метода на примере задачи, для которой исходный опорный план легко определяется из формы записи ограничений.

Пусть ЗЛП записана в каноническом виде:

при условиях

где a_ij, b_i и c_j – заданные постоянные числа, причем все b_i>0.

Табличная запись условий задачи

Исследование опорного плана на оптимальность, а так же переход к новому опорному плану удобнее вести, если условия задачи записать в виде симплекс-таблицы.

Таблица 1

В столбце C_б симплекс-таблицы записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса.

В столбце P₀ записывают положительные компоненты исходного опорного плана, в нем же в результате вычислений получают компоненты оптимального плана. Столбцы векторов представляют собой коэффициенты разложения этих векторов по векторам данного базиса.

В табл. 1 первые строк определяются исходными данными, а показатели (m+1)-й строки вычисляются. На пересечении этой строке со столбцом P₀ записывают значение целевой функции, которое она принимает на данном опорном плане, а в столбце вектора P_j − значение величины Δ_j= −c_j.

Величина z_j находится как скалярное произведение вектора P_j (j=1,…,n) на вектор P₀. Значение целевой функции F ₀ равно скалярному произведению вектора P₀ на вектор C_б.

3 Признак оптимальности опорного плана

В симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то опорный план является оптимальным.

Для определения оптимальности опорного плана рассчитывается значение целевой функции при выбранном опорном плане
X =( b₁, b₂,…,0,…,0) ^T:

Величина показывает, на сколько изменится при увеличении компоненты .

Если для любого j, то, очевидно, что увеличение компоненты приведет к уменьшению значения функции

Следовательно, если для любого j, то данный опорный план является оптимальным, а максимальное значение функции найдено и равно:

4 Переход от одного опорного плана к другому, более близкому к оптимальному. Симплексное преобразование

Для определения вектора, подлежащего исключению из базиса, находят для всех . Пусть этот минимум достигается при i = l. Тогда из базиса исключают вектор P_l, а число a_lk называют разрешающим элементом. Столбец и строку, на пересечении которых находится разрешающий элемент, называют направляющими.

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

а коэффициенты разложения векторов P_j − по векторам нового базиса по формулам

Элементы (m+1)-й строки новой таблицы могут быть вычислены либо по формулам

Варианты заданий

Решить ЗЛП симплексным методом:

Номер варианта	Задание	Номер варианта	Задание
1.		26.
2.		27.
3.		28.
4.		29.
5.		30.
6.		31.
7.		32.
8.		33.
9.		34.
10.		35.
11.		36.
12.		37.
13.		38.
14.		39.
15.		40.
16.		41.
17.		42.
18.		43.
19.		44.
20.		45.
21.		46.
22.		47.
23.		48.
24.		49.
25.		50.

Список литературы

1. Дорогов В. Г., Теплова Я. О. Введение в методы и алгоритмы принятия решений: учебное пособие / под ред. Проф. Л. Г. Гагариной. – М.: ИД «ФОРУМ»: ИНФРА-М, 2014, - 240 с.

2. Орлов А. И. Теория принятия решений: учебник М.: Издательство «Экзамен», 2006. – 573 с. (Серия «Учебник для вузов»).

3. Орлов А. И. Принятие решений. Теория и методы разработки управленческих решений. М.: ИКЦ «МарТ»; Ростов н/Д: Издательский центр «МарТ», 2005. 496 с.

4. Грешилов А. А. Прикладные задачи математического программирования: Учеб. пособие – 2-е изд. – М.: Логос, 2006. – 288 с.: ил.

№ п.п.	Ф.И.О. студента	номер вариа-нта
1	Арестов Алексей Николаевич	9
2	Артемьев Станислав Александрович	41
3	Буратчук Сергей Владимирович	26
4	Валиахметов Рафаэль Маратович	27
5	Васильев Алексей Юрьевич	5
6	Дегтярев Дмитрий Анатольевич	16
7	Дюдьбин Иоанн Алексеевич	36
8	Ишмуратов Вячеслав Салаватович	33
9	Ишутин Артем Евгеньевич	32
10	Мамишев Алексей Хафизович	46
11	Марку Павел Александрович	3
12	Митюков Игорь Олегович	28
13	Осипов Геннадий Николаевич	34
14	Подшиваленко Евгений Юрьевич	20
15	Гафарова Рузиля Айдаровна	10
16	Сагманова Гузель Ильдаровна	13
17	Студенский Данил Сергеевич	18
18	Туманов Никита Сергеевич	43
19	Файзуллин Фидан Фларитович	39
20	Хабибуллин Урал Робертович	30
21	Хуббутдинов Урал Ульфатович	21
22	Шегай Виктор Валерьевич	38
23	Юлдашев Адил Азатович	47
24	Юмагулов Максим Вадимович	37
25	Атнабаев Ришат Махмутович	22
26	Бакиев Руслан Фанитович	31
27	Банников Максим Викторович	11
28	Баранов Роман Григорьевич	25
29	Вахитов Данис Дамирович	42
30	Войкин Рим Фагимович	12
31	Давыдов Евгений Андреевич	40
32	Дербенев Александр Анатольевич	35
33	Закурдаева Ирина Владимировна	24
34	Иващенко Василий Юрьевич	23
35	Кантюков Альберт Альфредович	17
36	Колобов Сергей Андреевич	29
37	Ковалев Евгений Николаевич	8
38	Кожевников Алексей Олегович	1
39	Лопуха Руслан Викторович	14
40	Лыгин Евгений Евгеньевич	4
41	Муратов Рустем Юнирович	45
42	Расщупкина Аделина Александровна	6
43	Сагитов Айрат Минниярович	2
44	Старков Александр Андреевич	44
45	Сулейманов Ильнур Рамилович	50
46	Ульмасов Вадим Радикович	19
47	Урманцев Ильдар Фарвазович	48
48	Федоров Виктор Николаевич	7
49	Шабашов Сергей Анатольевич	15
50	Шаяхметов Марат Ринатович	49

Дата добавления: 2020-04-08; просмотров: 157; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!