4. Вычислительные процедуры симплекс-метода

Симплекс-алгоритм состоит из следующих шагов.

Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю n - m (небазисных) переменных.

Шаг 1. Из числа текущих небазисных (равных нулю) переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае осуществляется переход к шагу 2.

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

Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход к шагу 1.

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

W - 3х₁ - 2х₂ = 0 (целевая функция),

х~+2х, +з, =6~

2х"-+ х, ~~, =8

~ "+ "' '+ ~~- (ограничения). [ 3 х, +в,=2

Как отмечалось ранее, в качестве начального пробного решения используется решение системы уравнений, в которой две (=6 - 4) переменные принимаются равными нулю. Это обеспечивает единственность и допустимость получаемого решения. В рассматриваемом случае очевидно, что подстановка х~=х~ - - 0 сразу же приводит к следующему результату: ~,=6, з,=8, з,=1 и з,=2 (т. е. решению, соответствующему точке А на рис. 3.2). Поэтому точку А можно использовать как начальное допустимое решение. Величина W в этой точке равна нулю, так как и х,, и х, имеют нулевое значение. Поэтому, преобразовав уравнение целевой функции так, чтобы его правая часть стала равной нулю, можно убедиться в том, что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение. Это имеет место во всех случаях. когда начальный базис состоит из остаточных переменных.

4. Методические рекомендации студенту по организации самостоятельной работы

Общая трудоемкость освоения дисциплины «Математические модели в управлении» составляет 6 зачетных единиц, 216 часов, из них 108 часов аудиторных занятий и 108 часов, отведенных на самостоятельную работу студента.

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

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

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

1 На Рис. 2. Показаны не относительные адреса переменных F4 и F5, а их имена Переменная_х₁ и Переменная_х₂.

2 Задача из книги Таха Х. "Введение в исследование операций" _М.: Мир, 1985 г.

3 Отличие не дефицитности ресурса от его избыточности состоит в том, что исключение избыточного ограничения не влияет ни на пространство решений, ни на оптимум, тогда как исключение исходного ограничения, соответствующего недефицитному ресурсу, всегда влияет на пространство решений, но не всегда на оптимум.