Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Определение исходного базиса

Читайте также:
  1. III. Определение размера единовременной социальной выплаты
  2. IV. Определение массы груза, опломбирование транспортных средств и контейнеров
  3. АЭС определение, особенности компоновки.
  4. в) Определение, задачи, перечень работ и документация по бронированию граждан, пребывающих в запасе и работающих в организациях здравоохранения.
  5. Вопрос 9 Определение сторон света по компасу, небесным светилам и местным признакам.
  6. ВОССТАНОВИТЕЛЬНАЯ МЕДИАЦИЯ Определение медиации
  7. Выберите правильное определение клиренса

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

1. Система записана неравенством вида ≤ (меньше или равно).

2. Ограничения задачи линейного программирования выражены ли­нейными уравнениями

3. Ограничения задачи выражены неравенством вида ≥ (больше или равно). При ограничениях, записанных по первой форме, в уравнения вводятся свободные переменные (по одной свободной переменной в каж­дом соотношении), которые и включаются в исходный базис.

Если ограничения записаны в виде равенств (вторая форма ограни­чений), то возможны следующие приемы.

1. Если некоторая переменная входит только в j-e уравнение (соот­ношение), причем с коэффициентом, равным единице, то ее можно вклю­чить в исходный базис.

2. Ограничения, выраженные в виде равенств, записываются в следующем виде:

где: уi - искусственная переменная, ввод которой делается с целью построения исходного базиса.

Чтобы окончательное решение имело смысл, каждая искусственная переменная у,- на заключительной симплекс-итерации должна обращать­ся в нуль. Если на последней симплекс-итерации по крайней мере одна из переменных уi войдет в базис с положительным значением, то это означает несовместимость условий задачи, т. е. задача не имеет допусти­мых решений.

3. Если ограничения задачи выражены неравенством ≥, то в левую часть неравенств вводятся неотрицательные переменные с коэффициен­том (-1). В полученных уравнениях дополнительные переменные не могут быть приняты за базисные, так как они входят в уравнения с от­рицательным коэффициентом. Для нахождения допустимого исходного базиса, в этом случае может быть задан конкретный набор переменных, предназначенный для формирования исходного базиса.

При некоторых итерациях вычислительные процедуры, предписан­ные правилами 1 и 2, в части, касающейся перехода от одного базиса к другому, могут оказаться неоднозначно определенными. Например, когда в результате оценки коэффициентов в строке 0 две или более двух пере­менных являются по правилу 1 в равной степени «перспективными» с точки зрения улучшения пробного решения, выбор одной из этих пере­менных осуществляется произвольным способом.

Если, согласно правилу 2, две или более двух переменных промежу­точного базиса должны одновременно принять нулевые значения в силу включения в очередной базис новой переменной, из старого базиса под­лежит исключению только одна из них. Другие переменные из упомяну­тых переменных остаются в базисе, принимая при этом нулевые значе­ния. Базис, полученный в результате такой замены, называется вырож­денным.

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


Дата добавления: 2015-08-09; просмотров: 349 | Нарушение авторских прав


Читайте в этой же книге: Системы контроля и регулирования движения подвижного состава | РУКОВОДИТЕЛЬ КОЛЛЕКТИВА | СТИМУЛЫ И НАКАЗАНИЯ | АВТОМОБИЛЬНЫМИ ПЕРЕВОЗКАМИ | ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД | МЕТОД ПОТЕНЦИАЛОВ | МАРШРУТИЗАЦИЯ ПЕРЕВОЗОК | ОБСЛУЖИВАНИЯ В ОРГАНИЗАЦИИ ПЕРЕВОЗОК | РЕШЕНИЕ ЗАДАЧ В СЕТЕВОЙ ФОРМЕ | ОБЩИЕ ПОЛОЖЕНИЯ |
<== предыдущая страница | следующая страница ==>
Вычислительная процедура симплексного метода| Анализ модели на чувствительность

mybiblioteka.su - 2015-2024 год. (0.004 сек.)