Первый этап - решение вспомогательной задачи
Пусть в ЗЛП (3.18) расширенная матрица системы линейных уравнений (3.36) не является К-матрицей. Рассмотрим следующую вспомогательную задачу: найти вектор , максимизирующий функцию
(3.74)
при условиях
, (3.75)
, , , , . (3.76)
Переменные называются искусственными переменными вспомогательной задачи (ВЗ) (3.74-3.76). Обозначим множество планов ВЗ. Очевидно, что множество 0, так как вектор , а функция 0 ограничена сверху, следовательно, ВЗ (3.74-3.76) всегда разрешима, т.е.существует вектор такой, что = ( ) =d.
Рассмотрим расширенную матрицу системы (3.75)
(3.77)
которая является К-матрицей ВЗ (3.74-3.76), т.е. ВЗ может быть решена симплекс-методом.
Предположим, что ВЗ решена симплекс-методом, на S-й итерации которого получен ее оптимальный опорный план
= , ( ) = d, (3.78)
определяемый К-матрицей ВЗ.
(3.79)
Очевидно, что матрица
(3.80)
является расширенной матрицей системы линейных уравнений, равносильной системе (3.36).
Теорема 1.7. Если ( ) = d = 0 , то вектор =( ,…, )
является опорным планом ЗЛП (3.18) , если ( ) = d < 0, то множество планов ЗЛП (3.18) пусто.
Из теоремы 1.7 следует, что при решении ВЗ (3.74-3.76) симплекс-методом могут представиться следующий три случая:
На S-й итерации симплексного метода ни одна из искусственных переменных не является базисной, ( , ) , т.е. матрица = (3.61) является К-матрицей ЗЛП (3.18), а план =( , …, ) -опорным планом ЗЛП (3.18), определяемым этой К-матрицей.
На S-й итерации симплексного метода в числе базисных оказались искусственные переменные, например,
, p m,
т.е.
= n + 1, = n + 1, …, = n + p
причем
, .
Тогда вектор является вырожденным оптимальным опорным планом вспомогательной задачи линейного программирования, а матрица (3.61) содержит p < m единичных столбцов и не является К-матрицей основной задачи.
Однако в этом случае матрицу можно преобразовать в К-матрицу основной задачи линейного программирования, определяющую ее исходный опорный план.
Для этой цели рассмотрим любую r -ю строку из первых Р строк матрицы ( ).
Среди элементов ( ) этой строки есть хотя бы один элемент, отличный от нуля, так как в противном случае ранг матрицы А меньше m.
Выберем этот элемент в качестве направляющего с совершим один шаг метода Жордана-Гаусса преобразования матрицы с выбранным направляющим элементом. В результате базисная искусственная переменная будет заменена одной из основных переменных , а элементы ( n+1) стобца матрицы не изменятся.
После р таких шагов метода Жордана-Гаусса матрица будет преобразована в К-матрицу основной задачи линейного программирования, определяющую ее исходный опорный план
=( , …, ).
Очевидно, этот опорный план будет вырожденным.
На S-й итерации симплексного метода в числе базисных оказались искусственные переменные , p m , причем хотя бы одна не равна нулю. В этом случае множество Р планов ЗЛП (3.18) пусто.
- Учебное пособие
- Оглавление
- 2. Элементы линейной алгебры 21
- 3. Линейное программирование 48
- 4. Теория двойственности в линейном программировании 98
- 5. Целочисленные модели исследования операций 137
- 6. Экономические задачи, сводящиеся к транспортной модели 160
- Введение в исследование операций
- 1.1 Основные определения
- Этапы исследования операций
- Домашнее задание №1
- 2. Элементы линейной алгебры
- 2.1. Алгебра матриц
- 2.1.1. Виды матриц
- 2.1.2. Действия над матрицами
- Домашнее задание №2
- 2.2. Вычисление определителей
- Домашнее задание №3
- 2.3. Решение систем алгебраических уравнений
- 2.3.1. Основные понятия и определения
- 2.3.2. Формулы крамера и метод обратной матрицы
- 2.3.3. Метод жордана-гаусса
- Домашнее задание №5
- 2.4. Векторное пространство
- 2.4.2. Размерность и базис векторного пространства
- Домашнее задание №6
- 2.5. Решение задач линейной алгебры с помощью ms excel
- 3. Линейное программирование
- 3.1. Постановки задачи линейного программирования
- 3.1.1. Общая постановка задачи линейного программирования
- 3.1.2. Основная задача линейного программирования
- 3.1.3. Каноническая задача линейного программирования
- 3.2. Графический метод решения злп
- Домашнее задание №7
- Домашнее задание №8
- 3.3. Анализ решения (модели) на чувствительность
- Домашнее задание №9
- 3.4. Решение линейных моделей симплекс-методом.
- Переход от одной к-матрицы злп к другой к-матрице
- Алгоритм симплекс-метода
- Домашнее задание №10
- 3.4. Двойственный симплекс-метод (р-метод)
- Определение р-матрицы злп
- Условия перехода от одной р-матрицы злп к другой
- Алгоритм р-метода
- Решение задач р-методом
- Домашнее задание №11
- Домашнее задание №12
- 3.5. Решение злп двухэтапным симплекс-методом
- Первый этап - решение вспомогательной задачи
- Второй этап - решение исходной задачи
- Домашнее задание №13
- 4. Теория двойственности в линейном программировании
- 4.1. Определение и экономический смысл двойственной злп
- 4.2. Основные положения теории двойственности
- Получение оптимального плана двойственной задачи на основании теоремы 4
- На первой итерации получен оптимальный план злп (4.24).
- 4.3. Решение злп с помощью Ms Excel
- 4.4. Анализ решения злп на основе отчетов ms excel
- 5. Целочисленные модели исследования операций
- 5.1. Метод ветвей и границ решения целочисленных задач линейного программирования (цзлп)
- X1, х2 0, целые.
- Подробное описание метода
- 5.2. Задача коммивояжера
- Применение метода ветвей и границ для решения задачи коммивояжера
- Ветвление
- Построение редуцированных матриц и и вычисление оценок снизу
- Формирование списка кандидатов на ветвление
- 6. Экономические задачи, сводящиеся к транспортной модели
- 6.1.Транспортная задача линейного программирования
- Методы составления первоначальных опорных планов
- Метод потенциалов решения транспортной задачи
- Проверка выполнения условия оптимальности для незанятых клеток
- Выбор клетки, в которую необходимо поместить перевозку
- Построение цикла и определение величины перераспределения груза
- Проверка нового плана на оптимальность
- Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке
- 6.2.Экономические задачи, сводящиеся к транспортной модели
- Оптимальное распределение оборудования
- Формирование оптимального штата фирмы
- Задача календарного планирования производства
- Модель без дефицита
- Модель с дефицитом
- 6.3.Задача о назначениях
- Венгерский алгоритм
- Оптимальное исследование рынка
- Оптимальное использование торговых агентов