Разработка модели и решение задачи линейного программирования

Основные главы по теме:

1. искусственного базиса при решении задачи линейного программирования.
2. Симплекс метод решения задач линейного программирования
3. Метод искусственного базиса решения задач линейного программирования
4. Экономическая и геометрическая интерпретация задачи целочисленного программирования

Краткое содержание глав:

искусственного базиса при решении задачи линейного программирования.
Структура данной работы состоит из введения, основной части, заключения и списка литературы.

Линейное программирование
Линейное программирование –  это раздел математики о методах  решения задач связанных с  нахождением экстремумов линейных функций, нескольких переменных при  наличии линейных ограничений на ети переменные.
Задача линейного  программирования –  состоит из целевой  функции системы ограничений  и условий не отрицательности  и формулируется следующим образом: Найти экстремум целевой функции и соответствующие ему переменные при условии, что эти переменные удовлетворяют системы ограничений и условия не отрицательности. 
Виды  задач линейного  программирования.
Вид задачи определяется по системе ограничений.
Задача называется стандартной, если система ограничений состоит только из неравенств.
Задача называется канонической, если система ограничений состоит только из уравнений.
…

Симплекс метод решения задач линейного программирования
Симплекс-метод был разработан и впервые применён для решения задач в 1947 г. американским математиком Дж. Данцигом.
Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трёхмерное пространство, и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.
Допустимым решением (допустимым планом) задачи ЛП, данной в стандартной форме, называется упорядоченное множество чисел (х1, х2, …, хn), удовлетворяющих ограничениям; это точка в n-мерном пространстве.
Множество допустимых решений образует область допустимых решений (ОДР) задачи ЛП. ОДР представляет собой выпуклый многогранник (многоугольник).
…

Метод искусственного базиса решения задач линейного программирования
Метод искусственного базиса применяется к решению задач линейного программирования в общем случае, когда система ограничений не имеет предпочитаемого вида. Рассмотрим следующий пример.
Задача о диете. Симпатичная девушка узнала из дамского журнала, что для того чтобы волосы стали более шелковистыми, организм должен получать ежедневно не менее 40 г питательного вещества А, не менее 4 г питательного вещества Б и не менее 30 г питательного вещества В. Девушка знает, что в 1 кг яблок содержится 10 г вещества Б и 50 г вещества В, а в 100 г огурцов содержится 40 г вещества А и по 20 г веществ Б и В. Цена яблок – 60 руб. за 1 кг, цена огурцов – 50 руб. за 1 кг. Требуется помочь девушке составить рацион, помогающий увеличить шелковистость волос и при этом имеющий наименьшую стоимость.
Решение.
…

Заключения по теме:

Из 1-го хранилища необходимо груз направить в 4-й станцию (80), в 5-ю станцию (10) Из 2-го хранилища необходимо груз направить в 1-й станцию (40), в 2-й станцию (90), в 5-ю станцию (30) Из 3-го хранилища необходимо весь груз направить в 3-й станцию. Из 4-го хранилища необходимо груз направить в 1-й станцию (50), в 3-й станцию (10) Потребность 3 станции остается неудовлетворенной на 20 ед.

В курсовой работе изложены основные подходы и методы решения задач линейного программирования на примере задачи об оптимальном использовании ресурсов, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы организации производства на предприятии, повысить доход, уменьшить издержки. Все это влияет на конечный результат деятельности, бизнеса. Классическим методом решения задачи об оптимальном использовании ресурсов стал симплекс-метод, получившим также в литературе название метода последовательного улучшения плана. Этот метод может быть использован для решения большого комплекса задач внутризаводского планирования: формирование специфицированной годовой производственной программы выпуска предприятия, плана загрузки различных групп оборудования, календарное распределение производственной программы выпуска и т.д.

Данный метод решения применяется при наличии в системе ограничений и условий-равенств, и условий-неравенств, и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных Ri со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Таким образом из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом). Если в оптимальном решении М-задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении M-задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.