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

(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»).

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

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

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

Фенология Березняковского школьного заповедника
Мы все живём в окружении природы в той или иной степени следим за её состоянием. Поздние заморозки, повреждающие цветущие растения, длительная засушливая погода весной или зимние о ...