6. Алгоритм искусственного базиса
Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.
Расширенная М-задача применительно к исходной задаче записывается следующим образом:
|
(10.4) |
|
(10.5) |
|
(10.6) |
;
;
.
Здесь
- достаточно большое число.
Начальный
опорный план задачи (10.4) – (10.6) может
быть назначен непосредственно, так как
в матрице условий этой задачи уже
сформирована единичная подматрица,
которая и составит его базис
.
Поэтому вектор
с компонентами
,
и будет являться начальным опорным
планом задачи (10.4) – (10.6). Переменные
называются искусственными
переменными.
Таким образом, исходная задача линейного программирования с неизвестным заранее начальным опорным планом сводится к М-задаче, начальный опорный план которой может быть указан непосредственно. В процессе решения этой расширенной задачи можно либо вычислить оптимальный план исходной задачи, либо убедиться в её неразрешимости, если оказывается неразрешимой М-задача.
Список литературы.
1. Гасс С. Линейное программирование. М., 1961.
2. Данциг Дж. Линейное программирование, его применения обобщения. М., 1966.
3. Еремин И.И., Евстафьев Н.Н. Введение в теорию линейного и выпуклого программирования, М., 1976.
4. Сборник задач по высшей математике, Ч.4 Методы оптимизации (под ред. А.В. Ефимова), М., 1990.
5. Карманов В.Г. Математическое программирование, М.,1986.
6. Мину М. Математическое программирование, М., 1990.
7. Юдин Д.Б. Гольдштейн Е.Г. Линейное программирование, М.,1969.