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

Свойства задач линейного программирования. Графический метод решения задач линейного программирования

Алгоритм симплекс-метода решения общей задачи линейного программирования | Алгоритм симплекс-метода | Методы искусственного базиса | Двойственная задача ЛП. Экономическая интерпретация двойственной задачи ЛП | Экономическая интерпретация двойственной задачи | Постановка транспортной задачи | Метод потенциалов-метод решения транспортной задачи |


Читайте также:
  1. B. Неклассическая методология
  2. C. Постнеклассическая методология
  3. D) сохранения точных записей, определения установленных методов (способов) и сохранения безопасности на складе
  4. D.2. Методы оценки технических уязвимостей
  5. GR: основная цель, задачи и средства GR-менеджера
  6. I 7 D I РЕЛИГИЯ И НАУЧНЫЕ МЕТОДЫ
  7. I РЕЛИГИЯ И НАУЧНЫЕ МЕТОДЫ

Рассмотрим следующую основную задачу ЛП:

при ограничениях:

.

Перепишем ограничения этой задачи в векторной форме:

, (1.3)

где – k-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членов системы ограничений основной задачи:

План называется опорным планом основной задачи линейного программирования, если его положительные коэффициенты (x j>0) стоят при линейно независимых векторах P j.

 
 

Так как векторы P jявляются k-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше числа k.

Опорный план называется невырожденным, если он содержит ровно k положительных компонент, в противном случае он называется вырожденным.

Свойства задач линейного программирования тесным образом связаны со свойствами выпуклых множеств.

Пусть – произвольные точки евклидова пространства . Выпуклой линейной комбинацией этих точек называется сумма: , где – произвольные неотрицательные числа, сумма которых равна 1.

Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и отрезок прямой, соединяющий эти точки.

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

Первое свойство задач ЛП

Теорема 1.1. Множество планов любой задачи линейного программирования является выпуклым (если оно не пусто).

Непустое множество планов задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

Второе свойство задач ЛП

Теорема 1.2. Если задача ЛП имеет оптимальный план, то экстремальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если экстремальное значение целевая функция принимает более чем в одной вершине, то она принимает его на ребре (грани), содержащем эти вершины.

Теорема 1.3. Если система векторов линейно независима и такова, что , где все , то точка является вершиной многогранника решений.

Теорема 1.4. Если – вершина многогранника решений, то векторы P j, соответствующие положительным , линейно независимы.


Дата добавления: 2015-11-14; просмотров: 62 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Общая и основная задачи ЛП| Графический метод

mybiblioteka.su - 2015-2024 год. (0.007 сек.)