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

Задача математического программирования, сводимая к системе линейных уравнений или неравенств, включая критерий эффективности, становится задачей линейного программирования.

Уравнения – ограничения определяют область допустимых решений (ОДР).

Критерий эффективности определяет выбор вершины ОДР.

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

Из линейности граней и выпуклости ОДР, линейности w вытекает следующие свойства ЗЛП:

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

• Решение отсутствует, если ОДР не ограничена в направлении перемещения опорной поверхности.

• В невырожденном случае в вершине ОДР все свободные переменные равны нулю, число свободных переменных определяется мерностью пространства представления ОДР.

• В вырожденном случае число равных нулю переменных в вершине ОДР больше числа свободных переменных.

• Множество переменных естественно разбивается на два подмножества: свободные и базовые. Поисковые методы решения в случае многомерных пространств ориентированы на невырожденный случай ЗЛП и процесс поэтапной замены свободных переменных на базовые.

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

   • В.М. Панченко а.В. Панов
   • Учебное пособие
   • Введение
   • 1. Основные свойства и модели линейного программирования
   • Граф-схема решения задачи линейного программирования
   • 1.2. Алгебраическая модель решения задачи линейного программирования
   • 1.3. Геометрическая форма представления процесса решения
   • 1.4. Свойства задач линейного программирования
   • Симплекс-метод решения задачи линейного программирования
   • 2.1. Иллюстрация процесса поиска решения
   • 2.2. Алгебраическое решение
   • 2.3. Табличный вариант замены переменных
   • 2.4. Система «тренажер»
   • 2.5. Система правил замены переменных
   • 3.2. Формирование конкретной системы данных задачи линейного программирования
   • 3.3. Программа Random (Windows-версия)
   • 3.4. Экономическое содержание двойственности
   • 4.2. Составление опорного плана тз по методу минимума стоимостей перевозки
   • 4.3. Сравнение планов по критерию стоимости
   • 4.4. Проверка лучшего опорного плана на оптимальность
   • 4.5. Улучшение плана по методу циклических перестановок
   • Заключение
   • Библиографический список
   • 117454, Москва, пр-кт Вернадского, 78