logo

Решение контрольных по математике!!!

Home Методички по математике Математическое программирование (Составитель Е. М. Колодная) 13. Переход к новому, нехудшему опорному плану (третий пункт алгоритма)

13. Переход к новому, нехудшему опорному плану (третий пункт алгоритма)

1 В таблице 5 выбираем разрешающий элемент, руководствуясь следующими правилами:

А) выбрать в Z-строке симплекс-таблицы наибольший положительный элемент. Пусть это будет , тогда столбец будет разрешающим;

Б) найти отношения для положительных элементов () столбца ;

В) выбрать среди этих отношений наименьшее, скажем , тогда элемент разрешающий (генеральный).

2 Перейти от данной таблицы к следующей таблице по правилам работы с симплекс-таблицей (см. шаг Жордановых исключений).

Замечание: При решении задачи ЛП на максимум целевой функции ее можно преобразовать в эквивалентную ей задачу на минимум и решать вышеизложенным методом.

Пример 7

Воспользуемся результатами, полученными в предыдущем примере (см. таблицу 11). Так как в Z – строке есть положительный элемент, то найденный опорный план не оптимален. Поскольку максимальный положительный элемент Z-строки находится в столбце , то этот столбец будет разрешающим. Составим отношения свободных членов к соответствующим положительным элементам этого столбца (см. таблицу 12). По наименьшему отношению выберем разрешающую строку. Так как , то -строка будет разрешающей. На пересечении разрешающего столбца и разрешающей строки найдем разрешающий элемент « (таблица 12).

Таблица 12

СП

БП

1

X12

X21

Отношения

X11=

6,2

0

0,8

6,2/0,8

X22=

6

0,5

0

X3=

3,8

1

–0,8

X4=

4

–0,5

1

4/1

Z

61,6

–6

2,4

Шаг Жордановых исключений переводит таблицу 12 в таблицу 13.

Таблица 13

СП

БП

1

X12

X4

X11=

3

0,4

–0,8

X22=

6

0,5

0

X3=

7

0,6

0,8

X21=

4

–0,5

1

Z

52

–4,8

–2,4

Так как в Z-строке нет положительных элементов, то полученный план оптимален. Найдем его, приравняв свободные переменные к нулю, а базисные переменные – к свободным членам, т. е.

СП:

БП: ,

Следовательно, и .

Так как в Z-строке нет нулевых элементов, то полученный оптимальный план единственен.

Экономический смысл полученного решения задачи примера 2: для того чтобы затраты были минимальными необходимо, чтобы оборудование А1 выпускало 3 ч продукцию Р1, оборудование А2 выпускало 4 ч продукцию Р1 и 6 ч продукцию Р2. При этом продукция будет выпущена с минимальными затратами, равными 52 усл. ден. ед. и в заданный срок.

 
Яндекс.Метрика
Наверх