Содержание:
Введение …………………………………………………..
Постановка задачи
Описание метода
Математическая постановка задачи …………………….
Листинг программы………………………………………..
Блок-схема………………………………………………….
Заключение…………………………………………………
Список литературы………………………………………..
Введение
Целью данной курсовой работы является решение конкретной задачи линейного программирования методом улучшенного симплекс-метода. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства. Каждая из этих задач является частным случаем общей задачи линейного программирования.
Для решения задач линейного программирования созданы специальные методы. Изучению одного из них, а именно улучшенному симплекс-методу, посвящена эта курсовая работа.
Постановка задачи
На основе изученного алгоритма симплекс-метода разработать программу по следующему заданию: Исходная матрица коэффициентов заносится в память как матрица А, правые части ограничений заносятся в столбец 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.
Сделаем несколько замечаний относительно преимуществ и недостатков улучшенного симплекс-метода и симплекс-метода. При использовании улучшенного симплекс-метода исходная матрица ограничений запоминается. В симплекс методе ее элементы меняются при прохождении итераций. Таким образом, поскольку в улучшенном симплекс-методе нужны также обращение базиса и симплекс - множители, недостатком улучшенного симплекс-метода является большая потребность в машинной памяти.
Большим преимуществом улучшенного симплекс-метода является уменьшение количества вычислений. Таким образом, количество вычислений в задаче линейного программирования напрямую связано, скорее, с количеством ограничений, чем с количеством переменных, которые в общем случае значительно больше.
Улучшенный симплекс-метод непосредственно вычисляет обращение базиса и симплекс - множители. Эти величины не надо извлекать из окончательной таблицы. Это может помочь при последующем устойчивости решения.
Описание метода
Для решения задач линейного программирования существует множество методов. Рассмотрим один из них.
Улучшенный (модифицированный) симплекс-метод
Для начала расскажем, что такое симплекс-метод. Слово SIMPLEX в обычном смысле означает простой, несоставной, в противоположность слову COMPLEX.
Данный метод получил несколько различных форм (модификаций) и был разработан в 1947 году Г. Данцигом.
Сущность симплекс-метода заключается в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.
В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях и несколько оптимальных решений, но все они обеспечат экстремум целевой функции. Таким образом, если найти какой-либо базисный план, а затем улучшить его, то получится оптимальное решение. На этом принципе и построен симплекс-метод.
Одним из модификаций симплекс-метода является улучшенный симплекс-метод.
В литературе этот метод встречается также под названием метода обратной матрицы или модифицированного симплекс-метода.
При решении задач линейного программирования, в которых n (количество переменных) существенно больше m (количество ограничений), улучшенный симплекс-метод требует по сравнению с другими значительно меньшего количества выч
Одними из наиболее популярных услуг на рынке IT-технологий являются создание и продвижение лендингов. Они способны положительно влиять на деятельность любого бизнес-проекта в интернете. Судя по многочисленным отзывам, заказавшие создание лендингов люди ни разу не пожалели о потраченных деньгах. Они вложили в будущее, которое неразрывно связано с интернетом. Всё больше и больше предпринимателей обращаются к услугам разных агентств, веб-студий, чтобы заказать создание лендинга у профессионалов.