- •Глава III
- •3.1. Метод жесткого многогранника
- •3.2. Метод случайного поиска
- •Рубежный тестовый контроль
- •2. Метод жесткого многогранника
- •Глава IV. Линейное программирование
- •4.1. Необходимые сведения
- •4.2. Примеры задач линейного программирования
- •4.3. Основная задача линейного программирования (озлп)
- •4.4. Эквивалентная задача линейного программирования
- •4.5. Симплекс-метод
- •4.6. Геометрическая интерпретация задачи линейного программирования
- •Рубежный тестовый контроль
4.4. Эквивалентная задача линейного программирования
Речь пойдет о такой постановке задачи линейного программирования, которая эквивалентна ОЗЛП. В этой постановке все ограничения имеют вид неравенств.
Будем исходить из постановки ОЗЛП
;
; (4.41)
.
Пусть – ранг матрицы A, тогда, используя систему уравнений , r компонент n-мерного вектора x можно выразить через остальные n-r компоненты.
Например, пусть , , тогда три переменные из набора можно выразить через остальные две. Это может быть осуществлено не единственным образом. Все зависит от того, сколько отличных от нуля миноров порядка r имеет матрицa A. Сколько базисных миноров, столько и вариантов. Рассмотрим, как это можно осуществить практически.
В матрице А выберем любой базисный минор. Из элементов этого минора образуем матрицу, которую назовем базисной матрицей . Далее r уравнений системы , элементы которых вошли в , назовем базисными уравнениями (базисной системой). Остальные уравнения назовем свободной системой. Из элементов базисных уравнений, которые не вошли в , сформируем свободную матрицу . Из элементов вектора x, которые соответствуют и сформируем соответственно базисный и свободный векторы, т.е. и . Наконец, обозначим через и векторы, сформированные из элементов вектора B, которые соответствуют базисным и свободным уравнениям. Поясним сказанное на примере.
Пусть
, .
В данном случае в качестве базисного минора выберем, например, минор, элементы которого располагаются в первом и третьем столбцах, в первой и второй строках, т.е.
.
Этот минор равен пяти, т.е. отличен от нуля, а потому назначение его в качестве базисного правомерно. Далее, как это было оговорено выше, запишем, что
, , , ,
, .
Используя введенные выше обозначения, базисную систему запишем в виде
. (4.42)
Поскольку определитель
,
то матрица – не особая, а потому для нее существует обратная матрица
, (4.43)
где – алгебраические дополнения элементов определителя . В таком случае из (4.42) находим, что
, (4.44)
тем самым вектор выражен через вектор . Целевую функцию задачи (4.41) запишем в виде
, (4.45)
где векторы и образованы такими элементами вектора , которые отвечают соответственно векторам и . Выразим F (4.45) также через вектор , для этого воспользуемся выражением (4.44):
,
т.е.
, (4.46)
где -мерная строка
(4.47)
и скалярная величина
. (4.48)
Поскольку все компоненты вектора x должны быть не отрицательными, то, как это следует из выражения (4.44),
. (4.49)
Левую и правую части неравенства умножим на в результате чего получаем, что
, (4.50)
т.е.
. (4.51)
Итак, от задачи (4.41) мы перешли к задаче (4.51), (4.46), т.е.
; (4.52)
; (4.53)
. (4.54)
Это и есть эквивалентная постановка задачи линейного программирования. Задача (4.52) – (4.54) формулируется так – найти такой неотрицательный вектор , который, удовлетворяя ограничениям (4.52), (4.53), доставляет минимум целевой функции (4.54).
Замечание. Переменные из рассмотрения не выпали. Если решение задачи (4.52) – (4.54) будет найдено, то найдутся из (4.44).
Пример. Цель примера – показать, как осуществляется переход от ОЗЛП к эквивалентной задаче.
Пусть имеем следующую задачу (ОЗЛП)
;
;
,
где
, , , .
В данном случае и , где
.
Условия теоремы Кронекера-Капелли выполнены.
Поскольку , то две переменные , , можно выразить через третью. В матрице А выбираем базисный минор
,
в таком случае
, (4.55)
Заметим, что
;
или
. (4.56)
Для задачи (4.52) – (4.54) согласно (4.47), (4.48) имеем
;
Окончательно имеем следующую задачу
; (4.57)
;
, (4.58)
где
, , , .