Мои Конспекты
Главная | Обратная связь


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

Вершины многогранника называются угловыми точками.



3. Оптимальное решение (глобальный максимум) достигается хотя бы в одной угловой точке выпуклого многогранника, число которых конечно. Отсюда, принципиальный путь поиска оптимального решения: перебрать все угловые точки (их конечное число!) и среди них выбрать ту в которой целевая функция достигает максимума. Однако, как отмечается в [13] , технические сложности подобной процедуры настолько существенны, что за исключением простейших случаев, этот метод практически бесполезен.

Поэтому, необходимо научиться отбрасывать заведомо “плохие” угловые точки и работать только с перспективными, не прибегая к грaфикам.

Именно это и реализовал Данциг в разработанном им симплекс-методе. Суть метода – “направленный перебор”, когда вначале находят, какую нибудь угловую точку, а затем переходят к таким соседним угловым точкам, в которых значения целевой функции увеличиваются. Такой направленный перебор позволяет резко сократить число шагов (итераций).

Ясно, что для реализации симплекс- метода необходимо математически:

- выбрать начальное опорное решение (угловую точку)

- проверить его на оптимальность

- при необходимости перейти к лучшему

- уметь распознавать ситуации отсутствия оптимального решения.

Рассмотрим этапы “ручного” cимплекс - метода, когда необходимые преобразования осуществляются в таблицах стандартного вида.

Пример:

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

Табл.1

Ресурсы Запасы (ресурсов) Расходные коэффициенты
1 2 3
труд 6 5 4
сырье 3 2 4
оборудование 5 3 3
Прибыль, у.е.   9 10 16

Менеджеру фирмы требуется составить оптимальный план выпуска изделий (принять решение) из условия максимальной прибыли.

Начинаем, как всегда, с построения математической модели :

1.

х1, х2, х3 – количество изделий каждого вида.

1 + 5х2 + 4х3 ≤ 120

1 + 2х2 + 4х3 ≤ 96

1 + 3х2 + 3х3 ≤ 180 → ограничения модели

х1, х2, х3 ≥ 0

F= 9х1 + 10х2 + 16х3 → max

2. Приводим задачу к каноническому виду:

1 + 5х2 + 4х3 + х4 = 120

1 + 2х2 + 4х3 + х5 = 96

1 + 3х2 + 3х3 + х6 = 180

х1,.. х6 ≥ 0

F= 9х1 + 10х2 + 16х3 → max

4, х5, х6 – балансовые переменные).

3. Составляем исходную симплекс-таблицу (заметим, что в разных учебных пособиях форма симплекс- таблицы различна!):

Табл. 2

Базисн. перем. х1 х2 х3 х4 х5 х6 вi Оцен. отн.
х4
х5
х6
Оцен. строка -9 -10 -16  

В первом столбце указаны базисные переменные. Напомним, что им в матрице системы соответствует определитель не равный нулю (набор единичных столбцов в таблице). В столбце вi указаны правые части уравнений, а в последнем столбце – оценочное отношение (смысл поясним позже).