Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Задача максимизации ЦФ

Шаг 1. Пусть*,? = bt для i — 1,...,тих? =0для i> т. Тогда [х°/°]тявляется решением задачи (8.1) и, так какЬ > 0, это решение базисное допустимое.

Шаг 2. Выбор х,- зависит от значений с, и FJh i= 1,..., т ,j= 1,..., т.

Рассмотрим несколько случаев.

1°. Пусть коэффициент с, < 0 и некоторый Fjj < 0. Переменная х,- вектора xF, соответствующая этому столбцу, была равна нулю. Предположим, что теперь переменная х,- стала положительной. Обозначим новый вектор *’^ = [0 ••• х,- ••• 0]т. Тогда из

х'в = b- Fx' р при Fjj < 0 получим

Если (х'в )j > 0, то вектор х'внаходится в ОДР. Из (8.11) видно, что при Fjj< 0 компонента (хД, может увеличиваться до бесконечности. Отсюда следует вывод, что у/нет максимума, так как при с, < 0

Следовательно, необходимо выбрать другую х„ которой не соответствуют Cj < 0, Fjj < 0.

2°. Если С/ > 0, Fjj < 0, тогда

Поэтому в данном случае/° является наибольшей из всех возможных /и максимум достигнут.

3°. Имеются Cj < 0 и некоторые Fjj > 0.

Главная проблема связана с выбором /J,. В о - п е р в ы х, необходимо выбрать такое значение Fjj > 0, для которого операции со строками не нарушали бы условие Ь' > 0, т.е. необходимо, чтобы новое значение Ь’р , полученное путем деления j-й строки на Fjt и вычитания из р-й строки новой у-й строки, помноженной на Fpi, удовлетворяло условию

для всехр = 1,..., т, или

Во-вторых, в качестве опорного элемента надо выбрать такой, у которого коэффициент bp / Fpi наименьший.

Ограничения для каждой базисной переменной различны и в зависимости от значений они будут уменьшаться с разной скоростью. Поэтому надо найти отношения bj/ F^ для всех у и выбрать среди них минимальное, что определит крутизну наклона ребра. При увеличении свободной компоненты х, соответствующий базисный вектор первым станет нулевым.

Элемент Fp называется ведущим (опорным) элементом, строка у ведущей (опорной) строкой, столбец / ведущим (опорным) столбцом.

Исходя из сформулированных правил, выберем Fjt > 0 как опорный элемент, поделим элементыу-й строки на F^ и используем ее для получения нулевых элементов строк выше и ниже F». Таким образом, получается новый базисный столбец таблицы. Из формулы х'в = b- Fx' р = 0 следует, что в этом случае Xj примет значение bj / Fjj. Другие базисные переменные останутся неотрицательными.

Шаг 3. Свободная переменная xf стала базисной, а базисная Xj — свободной. Переставив столбцы местами, получим новую таблицу

где/ °' >/ °, потому что при с, < 0. Если условие

Ь' > 0 выполняется, то получается новое большее значение ЦФ и новая таблица.

Таким образом, из всех столбцов целесообразно выбрать

столбец, в котором с, < 0 имеет наибольшее абсолютное значение, так как это приведет к скорейшему уменьшению стоимости. Далее действия повторяются до тех пор, пока есть элементы с, < 0 и пока не появятся условия, при которых дальнейшая оптимизация невозможна. Однако если на некотором этапе bj= 0, может произойти зацикливание.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>