Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.
Функция (9.1) называется целевой функцией (или линейной формой) задачи (9.1)-(9.4), а условия (9.2)-(9.4) - ограничениями данной задачи. Вычислить значение линейной формы , как скалярное произведение соответствующих столбцов симплекс-таблицы, и значения оценок векторов условий относительно базиса в соответствии с формулой как скалярное произведение столбцов и симплекс-таблицы без коэффициента , т.е. по расчетной формуле Если , то - оптимальный опорный план и, тогда, в столбце симплекс-таблицы записано решение ЗЛП, а именно, значения базисных компонент оптимального опорного плана и соответствующее ему максимальное значение линейной формы. Если же в каждом столбце с отрицательными оценками найдется хотя бы один положительный элемент , то для построения нового опорного плана необходимо найти вектор, который будет вводиться в базис. Определить вектор, исключаемый из базиса для чего необходимо заполнить последний столбец t симплекс-таблицы нулевой итерации путем деления элементов столбца на соответствующие им по номеру положительные элементы разрешающего столбца , т.е.
План
Содержание
Определение ЗЛП
Первый алгоритм симплекс - метода
Алгоритм обратной матрицы
О конечности симплекс - метода
Алгоритм построения начального опорного плана
Алгоритм искусственного базиса
Список литературы
Список литературы
1. Гасс С. Линейное программирование. М., 1961.
2. Данциг Дж. Линейное программирование, его применения обобщения. М., 1966.
3. Еремин И.И., Евстафьев Н.Н. Введение в теорию линейного и выпуклого программирования, М., 1976.
4. Сборник задач по высшей математике, Ч.4 Методы оптимизации (под ред. А.В. Ефимова), М., 1990.
