Лекции по линейному программированию
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

 

Здесь мы сразу приведем формулировку этой теоремы.

Теорема (О дополняющей нежесткости): Для того, чтобы планы и Пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

Это условия дополняющей нежесткости. Из них следует: если какое-либо неравенство системы ограничений одной из задач не обращается в тождество оптимальным планом этой задачи, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в тождество, то есть, если:

То если то

Точно так же, если:

То если то

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

Отсюда следует вывод: Двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а избыточный ресурс (используемый не полностью) имеет нулевую оценку.

ПРИМЕР: Продукция в цехе может производиться тремя технологическими способами Объемы ресурсов и их расход в единицу времени для каждой технологии, а также производительности (эффективности) технологий (в денежных единицах за единицу времени работы по данной технологии) представлены в таблице данных.

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

Таблица данных

Ресурсы

Технологические способы

Объем

Ресурса

 

   

Рабочая сила (чел.-ч.)

15

20

25

1200

Сырье (т)

2

3

2,5

150

Электроэнергия (кВт. ч)

35

60

60

3000

Производительность технологического способа

300

250

450

   

План

   

ПРЯМАЯ ЗАДАЧА

ДВОЙСТВЕННАЯ ЗАДАЧА

РЕШЕНИЕ ПРЯМОЙ ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ

№ 1

300

250

450

0

0

0

   

0

15

20

25

1

0

0

1200

48

0

2

3

2,5

0

1

0

150

60

0

35

60

60

0

0

1

3000

50

300

250

450

0

0

0

№ 2

300

250

450

0

0

0

   

450

0,6

0,8

1

0,04

0

0

48

80

0

0,5

1

0

-0,1

1

0

30

60

0

-1

12

0

-2,4

0

1

120

-

30

-110

0

-18

0

0

№ 3

300

250

450

0

0

0

   

450

0

-0,4

1

0,16

-1,2

0

12

 

300

1

2

0

-0,2

2

0

60

 

0

0

14

0

-2,6

2

1

180

 

0

-170

0

-12

-60

0

Оптимальный план использования технологий:

Таким образом, первую технологию целесообразно использовать в течение 60 часов, третью - 12 часов, а вторую технологию применять вовсе даже нецелесообразно. При этом продукции будет выпущено на 23400 ден. единиц.

Решение двойственной задачи: Так как то первый и второй ресурсы использованы полностью. Третий ресурс избыточен Его двойственная оценка равна нулю: Следовательно, если при М технологическом способе суммарная оценка ресурсов, идущих на производство единицы продукции, выше дохода , то данный способ не должен внедряться Если же Й технологический способ используется в оптимальном плане, то суммарная оценка ресурсов, необходимых для производства единицы продукции, равна доходу .

Теперь проверим условия о дополняющей нежесткости.

ДЛЯ ПРЯМОЙ ЗАДАЧИ

ДЛЯ ДВОЙСТВЕННОЙ ЗАДАЧИ

Условия дополняющей нежесткости выполняются.

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство