Алгоритм симплекс-метода
Автор: YuliaGolysheva • Октябрь 29, 2020 • Практическая работа • 1,123 Слов (5 Страниц) • 395 Просмотры
Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра экономической математики, информатики и статистики (ЭМИС)
Алгоритм симплекс-метода
Отчёт по практической работе №3 по дисциплине
«Теория принятия решений»
Студент группы
___________ /
«__»_________20__г.
Проверил:
Ст.преподаватель каф. ЭМИС
_________ / И. Ю. Гендрина
«__»_________20__г.
Томск 2020
Задание 1. Решить графически, симплекс-методом в общем виде и с помощью симплекс-таблиц:
[pic 1]
Решение:
Графически
1) Рассмотрим неравенство 1 системы ограничений.
- 2 x1 + x2 ≤ 2
Построим прямую: - 2 x1 + x2 = 2
Пусть x1 =0 => x2 = 2
Пусть x2 =0 => - 2 x1 = 2 => x1 = -1
Найдены коородинаты двух точек (0, 2) и (-1 ,0). Соединяем их и получаем необходимую прямую
Знак неравенства ≤. Следовательно, нас интересуют точки, расположенные ниже построенной прямой
[pic 2]
2) Рассмотрим неравенство 2 системы ограничений.
- x1 + 2 x2 ≤ 16
Построим прямую: - x1 + 2 x2 = 16
Пусть x1 =0 => 2 x2 = 16 => x2 = 8
Пусть x2 =0 => - x1 = 16 => x1 = -16
Найдены коородинаты двух точек (0, 8) и (-16 ,0). Соединяем их и получаем необходимую прямую
Знак неравенства ≤. Следовательно, нас интересуют точки, расположенные ниже построенной прямой.
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
[pic 3]
3) Рассмотрим неравенство 3 системы ограничений.
x1 + x2 ≤ 5
Построим прямую: x1 + x2 = 5
Пусть x1 =0 => x2 = 5
Пусть x2 =0 => x1 = 5
Найдены коородинаты двух точек (0, 5) и (5 ,0). Соединяем их и получаем необходимую прямую
Знак неравенства ≤. Следовательно, нас интересуют точки, расположенные ниже построенной прямой.
Объединим данное условие с предыдущим рисунком. В итоге получим область допустимых решений, изображенную на рисунке.
[pic 4]
4) Строим вектор С = (1, -1), координатами которого являются коэффициенты функции F.
[pic 5]
Будем перемещать "красную" прямую, перпендикулярно вектору С, от левого верхнего угла к правому нижнему.
В точке, в которой "красная" прямая в последний раз пересечет область допустимых решений, функция F достигает своего наибольшего значения.
Функция F достигает наибольшего значения в точке A.
Координаты точки A (5,0) известны.
Вычислим значение функции F в точке A (5,0).
F (A) = 1 * 5 - 1 * 0 = 5
x1 = 5, x2 = 0, F max = 5
[pic 6]
Симплекс-методом в общем виде
1. Приведем к каноническому виду.
а) 𝑚𝑎𝑥 → 𝑚𝑖𝑛: 𝐿 ′ (𝑋) = −𝐿(𝑋) = −𝑥1 + 𝑥2 = 0 − 𝑥1 + 𝑥2 → 𝑚𝑖𝑛
...