Курсовая работа: Применение симплекс-метода
Содержание:
Введение …………………………………………………..
Постановка задачи
Описание метода
Математическая постановка задачи …………………….
Листинг программы………………………………………..
Блок-схема………………………………………………….
Заключение…………………………………………………
Список литературы………………………………………..
Введение
Целью данной курсовой работы является решение конкретной задачи линейного программирования методом улучшенного симплекс-метода. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства. Каждая из этих задач является частным случаем общей задачи линейного программирования.
Для решения задач линейного программирования созданы специальные методы. Изучению одного из них, а именно улучшенному симплекс-методу, посвящена эта курсовая работа.
Постановка задачи
На основе изученного алгоритма симплекс-метода разработать программу по следующему заданию: Исходная матрица коэффициентов заносится в память как матрица А, правые части ограничений заносятся в столбец 0. Таким образом, в матрицу входят М+2 строк, М ограничений, целевая функция и искусственная целевая функция. Она имеет P строк помимо строки 0, которые содержат исходные, новые и искусственные переменные. Матрица B состоит из столбцов значений переменных и значений целевой функции, матрицы обращения размерностью m x m, двух строк симплекс - множителей и последнего столбца, в котором все элементы, кроме последних двух, равны 0, а последние два равны – 1:
b́1 β11 β 1m 0
b΄2 β21 β 2m 0
B= b́m βm1 β mm 0
-z΄0 π1 πm 1
-ẃ0 ơ1 ơ m 1
Необходимо перевести данную программу с помощью языка Turbo Pascal .
Для проверки работоспособности программы необходимо ввести данные из следующего задания:
Найти такие неотрицательные x1 , x2 , что
2х1 – х2 ≤ 4,
x1 – 2x2 ≤ 2,
x1 + x2 ≤ 5,
и минимизировать функцию -3x1 + x2 = z.
Сделаем несколько замечаний относительно преимуществ и недостатков улучшенного симплекс-метода и симплекс-метода. При использовании улучшенного симплекс-метода исходная матрица ограничений запоминается. В симплекс методе ее элементы меняются при прохождении итераций. Таким образом, поскольку в улучшенном симплекс-методе нужны также обращение базиса и симплекс - множители, недостатком улучшенного симплекс-метода является большая потребность в машинной памяти.
Большим преимуществом улучшенного симплекс-метода является уменьшение количества вычислений. Таким образом, количество вычислений в задаче линейного программирования напрямую связано, скорее, с количеством ограничений, чем с количеством переменных, которые в общем случае значительно больше.
Улучшенный симплекс-метод непосредственно вычисляет обращение базиса и симплекс - множители. Эти величины не надо извлекать из окончательной таблицы. Это может помочь при последующем устойчивости решения.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--