Алгоритм симплекс-метода

Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра экономической математики, информатики и статистики (ЭМИС)

Алгоритм симплекс-метода

Отчёт по практической работе №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 → 𝑚𝑖𝑛