Пусть , тогда из системы (4) найдем значения базисных неизвестных: , . Полученное таким образом решение системы (4) называется начальным допустимым базисным решением

6. Подставим в целевую функцию (2) вместо базисных переменных их выражения через свободные:

. (5)

Для полученного базисного решения значение целевой функции .

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

Пример 6. Найти начальное допустимое базисное решение задачи линейного программирования

, .

Решение. Для системы ограничений составим расширенную матрицу: .

Выберем в первой строке разрешающий элемент, например . Умножим первую строку на и вычтем ее из второй строки (): . Разделим вторую строку на : . Выберем во второй строке разрешающий элемент, например . Умножим вторую строку на и вычтем ее из первой строки (): .

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

Выберем в первой строке отрицательный элемент, например (можно взять ) и сделаем его разрешающим. Для этого разделим первую строку на : . Первую строку прибавим ко второй (): . Матрица имеет разрешенный вид и все свободные члены отрицательные.

Из полученной разрешенной матрицы составим систему ограничений: . Переменные соответствующие разрешающим элементам - базисные, а - свободные. Выразим базисные переменные через свободные: . Подставим вместо свободных переменных любые числа, например нули: . Отсюда - начальное допустимое базисное решение.

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

Задания для решения в аудитории

1. Найти начальное допустимое базисное решение задачи линейного программирования:

, .

2. Найти начальное допустимое базисное решение задачи линейного программирования:

, .

Указание: сначала выбрать в первой строке разрешающий элемент , потом в третьей – .

Дата добавления: 2015-06-27