- •Курсовая работа
- •Введение
- •Глава 1. Постановка основной задачи линейного программирования
- •Линейное программирование
- •1.2. Симплекс метод решения задач линейного программирования
- •1.3. Двойственная задача линейного программирования
- •Глава 2. Построение модели и решение задачи определения оптимального плана производства в ооо «Мельник»
- •2.1. Построение экономико-математической модели
- •2.2. Определение оптимального плана производства симплексным методом
- •2.3. Решение задачи оптимизации в табличном процессоре ms Excel
- •Заключение
- •Список использованной литературы
Глава 1. Постановка основной задачи линейного программирования
Линейное программирование
Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Такие задачи находят обширные приложения в различных сферах человеческой деятельности. Систематическое изучение задач такого типа началось в 1939 – 1940 гг. в работах Л.В. Канторовича.
К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.
Круг задач, решаемых при помощи методов линейного программирования достаточно широк.Это, например:
задача об оптимальном использовании ресурсов при производственном планировании;
задача о смесях (планирование состава продукции);
задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или);
транспортные задачи (анализ размещения предприятия, перемещение грузов).
Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:
математические модели большого числа экономических задач линейны относительно искомых переменных;
данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
многие задачи линейного программирования, будучи решенными, нашли широкое применение;
некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.
Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
В общем виде модель записывается следующим образом:
целевая функция
(1.1) при ограничениях
(1.2) требования неотрицательности
(1.3) где xj – переменные (неизвестные);
- коэффициенты задачи линейного программирования.
Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).
Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.
Вектор, удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.
1.2. Симплекс метод решения задач линейного программирования
Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.
Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.
Допустимым решением (допустимым планом) задачи ЛП, данной в стандартной форме, называется упорядоченное множество чисел (х1, х2, …, хn), удовлетворяющих ограничениям; это точка в n-мерном пространстве.
Множество допустимых решений образует область допустимых решений (ОДР) задачи ЛП. ОДР представляет собой выпуклый многогранник (многоугольник).
В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах.
Базисным называется решение, при котором все свободные переменные равны нулю.
Опорное решение — это базисное неотрицательное решение. Опорное решение может быть невырожденным и вырожденным. Опорное решение называется невырожденным, если число его ненулевых координат равно рангу системы, в противном случае оно является вырожденным.
Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным и обозначается .
Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.
Симплекс-метод - это универсальный метод решения задач ЛП, представляющий собой итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области допустимых решений до тех пор, пока не достигнет оптимального значения.
С его помощью можно решить любую задачу линейного программирования.
В основу симплексного метода положена идея последовательного улучшения получаемого решения.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным.
Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
способ определения какого-либо первоначального допустимого базисного решения задачи;
правило перехода к лучшему (точнее, не худшему) решению;
критерий проверки оптимальности найденного решения.
Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.