Общая характеристика симплекс метода

(2.4)

(2.5)

, , (2.6)

Задача (2.4)-(2.6) имеет предпочтительный план. Её начальный опорный план имеет вид

Если некоторые из уравнений (2.2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема.

Если в оптимальном плане

(2.7)

М-задачи (2.4)-(2.6) все искусственные переменные , то план является оптимальным планом исходной задачи (2.1)-(2.3).

Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М-задачу, которая имеет начальный опорный план

Решение исходной задачи симплексным методом путем введения искусственных переменных называется симплексным методом с искусственным базисом.

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

Теорема.

Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

Признаки оптимальности.

Теорема

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

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

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

I. Ограничения вида «0»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».

II. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1». а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).

Перейти на страницу: 1 2 3

Экологические заметки

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

Земельные ресурсы и охрана земель от загрязнения
Почвенный покров - важнейшее природное образование. Его роль в жизни общества определяется тем, что почва представляет собой основной источник продовольствия, обеспечивающий 95-97% ...

Использование водных ресурсов и гидролого-экологические проблемы водных объектов суши
Вода - одно из самых распространенных на Земле и необычных по своим свойствам химических соединений. Без воды невозможно существование самой жизни. Вода - носитель механической и ...