АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Разрешимость задачи линейного программирования

Прочитайте:
  1. I. Иммунология. Определение, задачи, методы. История развитии иммунологии.
  2. II -А. Задачи СИТУАЦИОННЫЕ по диагностике в
  3. II. Основные задачи
  4. II. Целевые задачи
  5. II. Целевые задачи
  6. II. Целевые задачи
  7. II. Целевые задачи
  8. II. Целевые задачи
  9. II. Целевые задачи
  10. II.Целевые задачи

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

Если ОДП ограничена, то задача всегда разрешима. Для случая двух переменных это достаточно очевидно. Для задачи линейного программирования в общем виде это утверждение тоже верно.

Если ОДП не ограничена, то задача в некоторых случаях разрешима, а в некоторых нет.

Например, рассмотрим задачу, ОДП которой была построена на рисунке 13. Если при этом целевая функция по-прежнему максимизируется, то найти оптимальный план невозможно. В самом деле, можно сдвигать линию уровня в направлении градиента до бесконечности, и при этом она всегда будет пересекать ОДП. Крайнего положения этой линии не существует, т.е. условия позволяют получить сколь угодно большую прибыль. Целевая функция задачи не ограничена. Поэтому невозможно указать тот допустимый план, который даст максимальную прибыль, и задача будет неразрешима.

Предположим теперь, что в условиях той же задачи числа 108 и 140 представляют собой не прибыль от тонны карамели, а, например, затраты труда в человеко-часах на производство одной тонны. Необходимо минимизировать общие трудозатраты: min (108х1 + 140х2). Тогда линия уровня будет сдвигаться не в направлении градиента, а против него, и можно будет определить ее крайнее положение. На рисунке 17 пунктирной линией показано крайнее положение линии уровня, дальше которого ее невозможно сдвинуть против градиента, так как тогда она перестанем пересекать ОДП. Оптимальный план представляет собой точку пересечения прямых, которые соответствуют ограничениям по сахарному песку и патоке.

Итак, задача линейного программирования разрешима, если ее ОДП не пуста и ограничена в направлении экстремизации.


Дата добавления: 2015-01-18 | Просмотры: 1720 | Нарушение авторских прав


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |

При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)