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

Симплекс-метод может быть использован для решения большого комплекса задач внутризаводского планирования: формирование специфицированной годовой производственной программы выпуска предприятия, плана загрузки различных групп оборудования, календарное распределение производственной программы выпуска, в том числе и для нашей задачи – расчета количественного состава оборудования / 6, 7 /.

Общий вид задачи, решаемой симплекс-методом, следующий: найти максимальное значение функции

F(x) = c₁x₁+c₂x₂+…+c_nx_n max

при ограничениях, которые могут быть представлены в виде равенств:

a₁₁x₁+a₁₂x₂+a₁₃x₃+…+a_1nx_n = b₁;

a₂₁x₁+a₂₂x₂+a₂₃x₃+…+a_2nx_n = b₂;

………………………………….

a_m1x₁+a_m2x₂+a_m3x₃+…+a_mnx_n = b_m

и неравенств:

x₁ 0, x₂ 0, …, x_n 0,

где x₁, x₂, …, x_n, - переменные; с₁, с₂, …, с_n, a₁₁, a₁₂,…, a_mn, b₁, b₂, …, b_m – коэффициенты при искомых переменных.

Основная идея симплекс-метода состоит в следующем:

1) принимается за базу одна из возможных программ – отправная (опорный план);

2) осуществляется ее пошаговое улучшение, пока не будет получен оптимум по заданной критериальной функции.

Решение задач симплекс-методом предусматривает выполнение следующих процедур:

1) формирование целевой функции;

2) определение ограничительных условий – функциональных ограничений, которые могут иметь вид неравенств;

3) преобразование ограничений из неравенств в систему равенств путем ввода вспомогательных, свободных переменных (последние имеют экономическое содержание и характеризуют резерв, неиспользованный остаток тех ресурсов, по которым введено ограничение);

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

5) ввод в исходный вариант плана реальных переменных и, прежде всего тех, которые в наибольшей степени реализуют целевую функцию, максимизируют ее;

6) определение числового значения вводимой переменной – величины программы.

Алгоритм решения задачи симплекс-методом включает следующие шаги:

Шаг 1. Формирование целевой функции и системы ограничительных условий.

Шаг 2. Перевод неравенств в систему равенств.

Шаг 3. Построение исходной симплекс-таблицы (таблица 1.3.1).

Шаг 4. Проверка: все ли c_i 0? (i=1, (n+m)). Если есть c_i 0, то переходим к шагу 5, в противном случае – допустимое базисное решение является оптимальным.

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

Базис	x1	x2	…	xn	xn+1	…	xn+m	Bj
xn+1 xn+2 … xn+m	a11 a21 … am1	a12 a22 … am2	… … … …	a1n a2n … amn	…	… … … …	…	b1 b2 … bm
L	c1	c2	…	cn		…

Шаг 4. Проверка: все ли c_i 0? (i=1, (n+m)). Если есть c_i ³ 0, то переходим к шагу 5, в противном случае – допустимое базисное решение является оптимальным.

Шаг 5. Выбор разрешающего столбца и выбор вводимой переменной по условию

.

Шаг 6. Проверка: все ли a_jr 0? (i=1, m). Если все a_jr £ 0, то целевая функция является неограниченной, и решение найти нельзя, в противном случае – переход к шагу 7 (r – индекс разрешающего столбца, j – индекс строки).

Шаг 7. Выбор разрешающей сроки и выбор выводимой переменной по условию

.

Примечание. Индексы r (столбец) и s (строка) определяют разрешающий элемент.

Шаг 8. Пересчет элементов симплекс-таблицы по формулам:

,

, ; ,

, ,

и переход к шагу 4.

Логическая схема расчетов симплекс-методом представлена на рисунке 1.3.2.

Рисунок 1.3.2 – Логическая схема расчетов симплексным методом