Студопедия


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

I этап. Запись задачи в симплекс-таблицу




Между системой ограничений задачи и симплекс-таблицей взаимно однозначное соответствие:

· Строчек в таблице столько, сколько равенств в системе ограничений (+2); а столбцов столько, сколько переменных (+2).

· Базисные переменные заполняют первый столбец, свободные и базисные – верхнюю строку таблицы.

· Каждая строка таблицы соответствует уравнению.

· Коэффициенты целевой функции записываются с противоположными знаками.

· В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена.( На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблице к другой должно увеличиваться). Итак, нашей системе ограничений соответствует табл. 1 и можно переходить ко II этапу решения.

Таблица 1

свобод. базис -х3 -х4 -х5 правые части  
50/1=50
-
80/2=40 min
F –5 –3  

II этап. Проверка опорного плана на оптимальность.

Данной таблице соответствует опорный план: . Свободные переменные равны 0, а базисные переменные принимают значения чисел столбца свободных членов. Значение целевой функции

Наша задача проверить, является ли данный опорный план оптимальным, для этого необходимо просмотреть индексную строку – строку целевой функции F.

Возможны ситуации:

1) в индексной F–строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу. Переходим к IV этапу;

2) в индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция неограниченно возрастает;

3) в индексной строке есть отрицательный элемент, в столбце которого есть хотя бы один положительный. Тогда переходим к III этапу, улучшаем опорный план, пересчитывая таблицу.

III этап. Улучшение опорного плана.

1. Из отрицательныхэлементов индексной F–строки выберем наибольший по модулю, назовем соответствующий ему столбец разрешающим и пометим .

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

В нашем примере, элемент – разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей.




Таблица 2

свобод. базис -х3 -х4 -х5 правые части  
50/1=50
-
80/2=40 min
-F –5 –3  

3. Выбрав разрешающий элемент, делаем перечет таблицы по следующим правилам.

3.1. В новой таблице, таких же размеров, что и ранее, переменные при разрешающем элементе меняем местами, что соответствует смене базисов. В нашем примере: входит в базис, вместо , которая выходит из базиса, и теперь свободная (меняются местами элементы столбцов Х1 и Х5).

3.2. На месте разрешающего элемента (который теперь в столбце Х5)записываем обратное ему число

3.3. Элементы разрешающей строки делятся на разрешающий элемент.

3.4. Элементы разрешающего столбца делятся на разрешающий элемент и записываются с противоположным знаком

Таблица 3

свобод. базис -х3 -х4 -х5 правые части  
         
         
X1  
-F          

3.5. Все остальные элементы табл. 2.6 пересчитываем по правилу прямоугольника (в любом порядке).

Правило прямоугольника:

Пусть мы хотим посчитать элемент, например Соединяем пересчитываемый элемент мысленно с разрешающим, находим произведение .



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

Итак, . Записываем 10 на место, где было 50.

Аналогично:

, , , .

Имеем в новом базисе пересчитанную табл. 2.8.

Таблица 4

свобод. базис -х3 -х4 -х5 правые части  
 
40/1=40
X1 40*2/1=80
-F  

Базисными переменными теперь являются переменные . Значение целевой функции стало равно 200, т.е. увеличилось. Чтобы проверить данное базисное решение на оптимальность, надо перейти опять ко II этапу.

Для этого проверим индексную строку и, увидев в ней отрицательный элемент , назовем ему соответствующий столбец – разрешающим. Составим соотношения правых частей к только положительным элементам разрешающего столбца, выберем среди них минимальное: . Определим разрешающий элемент 1, теперь пересчет осуществляем согласно правилам 3.1–3.5.

свобод. базис -х3 -х4 -х5 правые части  
 
 
 
-F  

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





Дата добавления: 2015-04-12; просмотров: 1017; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома - страшная бессонница, которая потом кажется страшным сном. 8431 - | 6996 - или читать все...

Читайте также:

 

3.85.143.239 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.003 сек.