02.27.2023

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

1. Уловние примнения симплекс-метода
2. Алгоритм симплекс-метода на примере решения задачи

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

Этапы решения задачи ЛП симплекс-методом
1. Построение математической модели поставленной экономической задачи
2. Построение первончальноо опорного плана адачи
3. Улучшение полученного опорного плана до потимального
4. Анализ полученного решения

ДЛя решения задач линейного программирования симплекс-методом необходимо:
1. Систему неравенств преобразовать в уравнения, где все свободные члены неотрицательные

Система огранчиений является системой уравнений с базисом

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

Свободные члены всех уарвнений в системе неотрицательны

Целевая функция должна стремиться только к максимуму.

Симплекс-таблица

Ресурсы нужны для того, чтобы составить систему ограничений.
Если речь идет о целевой функции, то речь, как правило, идет о доходе (прибыли).

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

Пусть:
$x_{1}$ - площадь пшеницы,
$x_{2}$ - площадь подсолнуча,
$x_{3}$ - площадь люцерны.

Первое ограничение: ограничение по площади пашни
$x_{1} + x_{2} + x_{3}\geq 320$

Второе ограничение: ограничение по затратам труда:
$15x_{1} + 19x_{2} + 10x_{3}\leq 5000$

Третье ограничение: тоже по затратам труда:
$40x_{1} + 30x_{2} + 48x_{3}\leq 192000$

Четвертое условие: условие неотрицательности
$x_{1}>0, x_{2}>0, x_{3}>0$

Целевая функция - выручка
$f(x)=55.01*0.818x_{1}+24*1.821x_{2}+32.69*0.406x_{3}$
$f(x)=45x_{1}+43.7x_{2}+13.4x_{3}\to max$

Приведем задач к каноническому виду.
Каноническая форма - все ограничения в канонической форме являются ограничениями-равенствами с неотрицательными правыми частями. Все переменные неотрицательные.

Чтобы неравенство привести к форме уравнений (равенства) необходимо к левой части каждого неравенства прибавить балансирующую (или дополнительную, или базисную) переменную. Количество введенных базисных переменных должно совпадать с количеством огрничений в задаче.

Если в неравенстве стоит знак >=, то базисная переменная вводится со знаком -
Если в неравенстве стоит знак <=, то базисная переменная вводится со знаком +
В целевую функицю базисные переменные также вводятся, но с нулевыми значениями.

Вводим дополнительные переменные. Также обозначем их через $x$, но продолжаем инексацию.
$x_{4}$ - количество неиспользуемой площади пашни (га)
$x_{5}$ - количество неиспользованного труда (в человеко-часах)
$x_{6}$ - количество неиспользованных удобрений

Все шесть переменных неотрицательные (дополняем условие неотрицательности).

$f(x)=45x_{1}+43.7x_{2}+13.35x_{3}+0x_{4}+0x_{5}+0x_{6} \to max$

Заполнение симплекс-таблицы

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

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

Критерии оптимальности плана

• В хажачах на максимум - все окэффициенты индексной строки должны быть положительны
• В задачах на минимум - все оэффициенты индексной строки жолжны быть отрицательны

Если хотя бы один коэффициент иднексной строки не удовлетворяет этим условиям оптимальности - план не оптимален

Улучшение опорного плана
Для того, чтобы улучшить план, ннебохдимо выбрать ключевой элемент матрицы.
Ключевой элемент находится на переечении ключевого столбца и ключевой строки

1. Выберем ключевой столбец матрицы - Выбирается наименьший элемент из индексной строки
2. Выбираем ключевую строку - для этого столбец свободных членов поэлементно делят на ключевой столбец и выбирают из полученных чисел минимальное
   Ключевой строкой является $x_{5}$. Ключевой элемент находится на пересечении $x_{5}$ и $x_{1}$

Делим значение ключевой строки на ключевой элемент.
5000:19, 15:19, 10:19, и т.п...

Элементцы ключевого столбца (кроме ключевого элемента) приравниваются к нулю

Все остальные элементы таблицы (включая индексную строку)

Элемент новой симплекс-таблицы
=
Элемент предыдущей симплекс-таблицы
-
соответствующий элемент ключевого столбца симплекс-таблицы
*
элемент начальной строки новой симплекс-таблицы в соответствующем столбце

]]

Построение вектора-градиента

1. Ставим первую точку на начало системы координат
2. Подставляем единицу в целевую функцию. Получаем 2 координаты для второй точки
3. Проводим вектор от начала системы координат до второй точки. Получаем вектор-градиент
4. Далее проводим перпендикуляр от вектора-градиента до такой точки фигуры-пересечения, что является ближе всего к КОНЦУ вектора
5. Мысленно "двигаем" перпендикуляр в ОБРАТНОМ НАПРАВЛЕНИИ до того, пока не достигнем последней точки.