Simplex Method

Данная практическая работа идёт в рамках курса "Теория систем и системного анализа"

---

Цель практической работы:

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

---

Задание:

Составление плана продаж, максимизирующий прибыль.

---

Цель исследования:

Научиться применять симплексный метод для решения оптимизирующей задачи.

---

Задачи по практике:

• Проанализировать предметную область.
• Составить математическую модель предметной области.
• Решить задачу максимизации прибыли по составленной модели.
• Провести анализ на чувствительность при изменении имеющихся показателей прибыли и издержек обращения.

---

Анализ предметной области.

Торговое предприятие для организации продажи трех видов продукции располагает ресурсами труда и площади. Известны общий объем ресурсов на квартал, а также нормативы их затрат, издержки обращения и прибыль от продажи. Известны:

• общий объем трудовых ресурсов и площади;
• Нормативы расходования ресурсов для каждого вида продукции (на 1 усл. единицу товарооборота);
• Прибыль и издержки обращения по каждому из видов продукции (на 1 усл. единицу товарооборота).

Необходимо решить задачу максимизации прибыли, с учетом всех имеющихся данных.

---

Математическая модель предметной области.

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

• $c_i$ - цена i-го товара,
• $x_i$ – количество i-го товара.

$$c_1 x_1+c_2 x_2+c_3 x_3→max$$

$$ \begin{cases} & a_{11} x_1+a_{12} x_2+a_{13} x_3≤v_1 \\ & a_{21} x_1+a_{22} x_2+a_{23} x_3≤v_2 \end{cases} $$

$$x_1 x_2 x_3≥0$$

• $a_{ji}$ – нормативы расходования ресурсов j-го вида (труд, площадь), i-го вида продукции.
• $v_j$ – общий объем ресурсов j-го вида (труд, площадь)

Таблица коэффициентов: (добавляем 2 дополнительных переменных x4 x5)

Базис	$C_b$	$B^{-1}P_0$	$B^{-1}P_1$	$B^{-1}P_2$	$B^{-1}P_3$	$B^{-1}P_4$	$B^{-1}P_5$
$x_4$	0	10	68	6	4	2	1
$x_5$	0	20	60	2	3	6	0

---

Решение задачи максимизации прибыли по данной модели.

Классический симплекс метод решает задачу минимизации целевой функции, поэтому в нашем случае (мы ищем максимум) необходимо будет умножить нашу целевую функцию на -1, решить задачу минимизации и результат также умножить на -1. Канонизация и Симплекс метод реализованы на языке Python с использованием библиотеки Numpy для работы с массивами.

Код - Solution simplex method

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

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

Первая задача анализа на чувствительность определяет влияние изменения коэффициента целевой функции (цены на продукцию в задаче планирования выпуска продукции) на оптимальное решение.

Необходимо найти интервалы изменения издержек каждого товара, при неизменном оптимальном решении.

---

Алгоритм:

В случае изменения коэффициентов целевой функции следует сделать следующее:

• В последней симплексной таблице, соответствующей оптимальному решению, производится замена строки коэффициентов целевой функции и осуществляется пересчет оценок Δ" 𝑗 = 1. . 𝑛. Таким образом, изменение коэффициентов целевой функции не влияет на допустимость решения, но влияет на его оптимальность.

• Если все оценки останутся неположительными (в случае минимизации целевой функции) или неотрицательными (в случае максимизации целевой функции), то полученное решение остается оптимальным.
• При получении положительной оценки (в случае минимизации целевой функции) или отрицательной оценки (в случае максимизации целевой функции), решение остается допустимым (так как коэффициенты разложения вектора 𝑃. не изменяться), но перестает быть оптимальным. Поэтому следует произвести далее пересчет симплексной таблицы по правилам простого симплексного метода.

Код - Analysis sensitivity