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

Если какие-либо точки линейного пространства, то выпуклой линейной комбинацией этих точек называется сумма

,

где - произвольные неотрицательные числа, удовлетворяющие условию .

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

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

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

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

Базисные планы с неотрицательными компонентами называются опорными

Справедливы теоремы.

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

.

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

Теорема 1.3. 1. Целевая функция f задачи линейного программирования достигает своего экстремального значения в вершине многогранника области допустимых решений (единственное решение).

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

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

,

можно перейти к нахождению максимума функции

.

3. Содержание

   • Задачи линейного программирования
   • Постановка задачи
   • Задачи для решения
   • 1.2. Свойства решений задач линейного программирования
   • Графический метод решения задач линейного программирования Случай двух переменных
   • Случай многих переменных
   • 1.4.2.Симплексный метод
   • Этап 1. Определение начального опорного плана.
   • Случай вырождения
   • Задачи для решения
   • Метод искусственного базиса
   • Задачи для решения
   • 1.5. Теория двойственности в линейном программировании
   • 1.5.1. Постановка задачи
   • Некоторые частные случаи
   • 1.5.2. Основные теоремы двойственности
   • Задачи для решения
   • 1.5.3. Геометрическая интерпретация двойственных задач
   • 1.5.4. Двойственный симплекс – метод
   • Этап 1. Определение начального опорного плана (псевдоплана).
   • Этап 2. Определение оптимального плана.
   • Задачи для решения
   • 1.6. Экономическая интерпретация двойственности
   • 1.6.1. Анализ моделей на чувствительность.
   • Использование графического метода.
   • Использование симплекс-метода.
   • Использование графического метода.
   • Использование симплекс-таблицы.
   • Использование графического метода.
   • Использование симплекс-таблицы.
   • Использование графического метода.
   • Использование симплекс-таблицы.
   • Использование графического метода.
   • Использование симплекс-таблицы.
   • Применение компьютера Инструкция по использованию надстройки «Поиск решения»
   • 1.10. Решение задачи с использованием