Общая характеристика симплекс метода
Симплекс метод - это универсальный метод для решения линейных систем уравнений или неравенств и линейного функционала [25].
Общая идея симплекс метода для решения ЗЛП (задачи линейного программирования) состоит в:
- умении находить начальный опорный план;
- наличии признака оптимальности опорного плана;
- умении переходить к нехудшему опорному плану.
Пусть ЗЛП представлена системой ограничений в каноническом виде:
.
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.
Пусть система ограничений имеет вид
Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные . Получим систему, эквивалентную исходной:
,
которая имеет предпочтительный вид
.
В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю .
Пусть далее система ограничений имеет вид
Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему
Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные
входят в левую часть (при ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план
не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные . В целевую функцию переменные , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом -М для задачи на максимум, где М - большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.
Пусть исходная ЗЛП имеет вид
(2.1)
(2.2)
(2.3)
причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:
Экологические заметки
Технологический процесс добычи марганцевой руды и влияние на окружающую среду (на прим. Ордженекидзовского ГОКа)
Актуальность работы высока. Она
заключается в том чтобы исследовать негативное воздействие оказываемое на
окружающую среду при добыче и обработке марганцевых руд.
Для того, чтоб ...
Управление загрязнением окружающей среды
Стремительное развитие всех отраслей
промышленности, энергетики, транспорта, увеличение численности населения,
урбанизация и химизация всех сред деятельности человека приводят к на ...
Разработка программного модуля для нахождения оптимальных предельно-допустимых выбросов в атмосферу от группы источников
В нашей стране существует государственная система управления выбросами
промышленных источников загрязнения атмосферы (ИЗА) [1-4]. Целью системы
является достижение и поддержание на ...