Линейное программирование: методы решения задач - Контрольная работа

Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения элементарных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные. Целевая функция - функцию переменных задач, которая характеризует качество выполнения задачи, и экстремум которой требуется найти.Графический метод решения задачи линейного программирования - основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные . Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми: . линейное программирование потенциал моделирование Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию : Найти точку многоугольника решений, в которой прямая опорная и функция при этом достигает минимума. Если многоугольник решений ограничен (см. рисунок), то прямая дважды становится опорной по отношению к многоугольнику решений (в точках и ), причем минимальное значение принимает в точке .В общем виде, когда в задаче участвуют N - неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n - мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Но, во-первых, все опорные решения неизвестны и их нужно находить, а во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс - метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. Имея систему ограничений, приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m <n), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Вычисления по симплекс - методу организуются в виде симплекс - таблиц, которые являются сокращенной записью задачи линейного программирования в канонической форме.Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Совместное рассмотрение таких пар двойственных задач оказывается весьма эффективным средством теоретического исследования проблем линейного программирования и построения различных вычислительных методов. Двойственная задача - одно из фундаментальных понятий теории линейного программирования; инструмент, позволяющий установить, оптимально ли данное допустимое решение задачи ЛП, без непосредственного сравнения его со всеми остальными допустимыми решениями. К каждой задаче ЛП можно построить своего рода симметричную: функционалы оптимальных решений у обеих задач совпадают, но если в прямой задаче они отражают наиболее эффективную комбинацию ресурсов, которая дает максимум целевой функции, то в другой, двойственной - наиболее эффективную комбинацию расчетных цен (оценок) ограниченных ресурсов.Задача формулируется как найти при условиях , где - стоимости провоза по дугам, - производсво ( ) / потребление (-) - решение Матрица ограничений транспортной задачи состоит из столбцов , содержащих всего два ненулевых элемента - 1 для производителя и-1 для потребителя. Метод потенциалов является модификацией симплекс-метода, в котором базисная матрица представлена в виде дерева . Двойственные переменные симплекс-метода для транспортной задачи называются потенциалами. Проверка оптимальности плана легко трактуется с экономической точки зрения - если стоимость продукта в точке потребления больше стоимости в точке производства цена перевоза, по этой дуге следует везти.2) Построим прямую 2x1 5x2 = 432 по двум точкам. Для нахождения первой точки приравниваем x1 = 16. Для нахождения второй точки приравниваем x2 = 0. Построим прямую 3x1 4x2 = 424 по двум точкам. Для нахождения первой точки приравниваем x1 = 141.Пошаговое описание решения задачи: 1) По данным таблицы из пункта 1 составляем математическую модель: F=34*X1 50*X2 =>max Столбец свободных членов не содержит отрицательных чисел, но отрицательные коэффициенты есть в индексной строке. 5) Определение новой базисной переменной: В качестве ведущего выберем столбец, соответствующий переменной x2, так как в индексной строке это наибольший коэффициент по модулю. 6) Определение новой свободной переменной: Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (432: 5, 424: 4, 532: 3) = 862/5 Следовательно, 1-ая строка является ведущей.2) Составим Матрицу задачи: F - Коэффициент целевой функции. В последней строке на

Содержание

Задача № 1

Задача № 2

1. Перечень сокращений, терминов и их определение

2. Описание используемых методов

2.1 Графический метод

2.2 Симплекс-метод

2.3 Двойственная задача

2.4 Метод потенциалов

3. Решение задачи с помощью нескольких методов

3.1 Решение задачи графическим методом

3.2 Решение задачи симплекс-методом

3.3 Формулировка двойственной задачи

3.4 Моделирование и решение транспортной задачи методом потенциалов

4. Решение симплекс задачи с помощью MS Excel

4.1 Решение двойственной задачи с помощью MS Excel

4.2 Решение транспортной задачи с помощью MS Excel

5. Заключение

6. Список используемой литературы

1. Перечень сокращений, терминов и их определение

Целью данного курсового проекта было - составить план производства требуемых изделий, обеспечивающий максимальную прибыль от их реализации, свести данную задачу к задаче линейного программирования, решить ее симплекс - методом, методом двойственной задачи и методом потенциалов (транспортная задача). В ходе выполнения работы данная цель была полностью выполнена. Симплекс задача и двойственная задача, взаимозаменяемые задачи, иначе говоря, для проверки одной можно использовать другую.

В данной работе было наглядно рассмотрено решение задач с помощью MS Excel.

Данные задачи используются в разных областях, например, в математике или экономике. Следовательно, можно сделать вывод, что данная курсовая работа может служить наглядным образцом для решения подобных задач.

1. Аттеков А.В. Галкин С.В. Зарубин В.С. Методы оптимизации: Учебник для вызов / Под. Ред.В.С. Зарубина, А.П. Крищенко. - 2-е изд., Стереотип. - М. Изд - во МГТУ им. Н.Э. Баумана, 2033

2. Пинегина М.В. Математические методы и модели в экономике: Учеб. Пособие для студентов вузов экономических специальностей. - М: Издательство "Экзамен", 2004.

3. Краев М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: Учебник. - 2-е изд., испр. - М.: Дело, 2003.

4. Ларионов А.И., Новоселов А.Л., Юрченко Т.И. Экономико - математические методы в планировании: Учеб. Для сред. Спец. Заведений. - 2-е изд, перераб, И доп. - М.: Высш. шк. 1991.

5. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. Пособие. - 3-е изд. - М.: Дело, 2004

Размещено на