Основная задача линейного программирования
Получение оптимального плана-решения в задачах с линейной структурой. Классификация методов линейного программирования. Модель основной задачи линейного программирования в разных формах записи. Графический метод решения задачи линейного программирования.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 14.11.2014 |
| Размер файла | 36,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Линейное программирование. Основная задача линейного программирования
Содержание
1. Классификация методов линейного программирования
2. Основная задача линейного программирования и её модель в различных формах записи
3. Графический метод решения задачи линейного программирования
линейный задача программирование графический
1. Классификация методов линейного программирования
Большое число экономических задач сводится к линейным математическим моделям. Традиционно оптимизационные линейные математические модели называются моделями линейного программирования. Этот термин появился, когда программирование на компьютере еще не было развито, и соответственно не очень удачному переводу английского «programmation». Линейное программирование возникло в СССР. В конце 30-х годов XX в. советский экономист-математик Леонид Витальевич Канторович открыл класс этих задач и придумал некоторые частные методы их решения. В 1975 г. фактически за это открытие он был удостоен Нобелевской премии по экономике, что уже свидетельствует о большой важности задач линейного программирования.
С чисто математической точки зрения задачи линейного программирования интересны тем, что здесь неприменимы методы нахождения экстремумов с помощью производной.
Под линейным программированием понимается линейное планирование, т.е. получение оптимального плана-решения в задачах с линейной структурой.
Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств и для которых методы математического анализа оказываются непригодными. Линейное программирование представляет собой наиболее часто используемый метод оптимизации.
Методы линейного программирования подразделяются на группы:
1) группа симплексных методов (точные);
2) группа распределительных методов (точные и приближённые).
Точные - методы перебора вариантов решения задачи в итоге дающие оптимальный вариант. Используются при машинном решении задач.
Приближённые - позволяют получить только один из допустимых вариантов решения задачи. Используются для получения первого варианта в точных распределительных методах или для ручного решения задачи.
Каждая группа методов имеет свою базовую задачу. Для группы симплекс-методов базовой является «Основная задача линейного программирования», для группы распределительных методов - «Транспортная задача».
2. Основная задача линейного программирования и ее модель в различных формах записи
Постановка задачи.
Пусть некоторое предприятие имеет m видов производственных ресурсов. Порядковый номер ресурсов - i, т.е. i=1, 2,…, m.
Наличие каждого вида ресурсов известно и обозначается bi.
Предположим, что предприятие может производить n видов продукции. Порядковый номер продукции - j, т.е. j=1, 2, …, n.
Необходимо определить какое количество единиц продукции каждого вида надо производить (xj), чтобы получить максимум этой продукции в стоимостном выражении, если известны затраты на производство единицы продукции каждого вида ресурса (aij) и цена реализации (cj).
Развернутая форма записи модели.
I. Целевая функция - описывает выход продукции в стоимостном выражении:
Z=c1x1+c2x2+…+cnxnmax.
II. Система основных ограничений - описывает с помощью математической зависимости тот факт, что расходы производственных ресурсов не должны превышать их наличие:
a11x1+a12x2+…+a1nxn b1;
a21x1+a22x2+…+a2nxn b2;
………………………….
am1x1+am2x2+…+amnxn bm.
III. Условие неотрицательности переменных величин:
x10, x20, …, xn0.
Замечание: в постановке с выбором другого критерия оптимальности целевая функция может стремиться к минимуму. Кроме того система ограничений может быть смешанной, т.е. содержать не только неравенства (,), но и равенства.
Структурная форма записи модели.
В такой форме модели даются в специализированной литературе. В этой форме записи отражается структура и тип ограничений, структура функции, какие переменные входят в функцию Z и в ограничения.
I. max.
II. , i=1,2,…,m.
III. xj0, j=1,2,…,n.
Замечание: одной формулой можно описать ограничения, имеющие одинаковую структуру и тип и включающие в себя одни и те же переменные.
Существуют также векторная, матричная и табличная формы записи модели.
Размещено на Allbest.ru
...Подобные документы
Сущность линейного программирования. Изучение математических методов решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Нахождение точек наибольшего или наименьшего значения функции.
реферат [162,8 K], добавлен 20.05.2019Общее понятие вектора и векторного пространства, их свойства и дополнительные структуры. Графический метод в решении задачи линейного программирования, его особенности и область применения. Примеры решения экономических задач графическим способом.
курсовая работа [1,2 M], добавлен 14.11.2010История зарождения и создания линейного программирования. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей. Методы составления начального опорного плана. Понятие потенциала и цикла. Задача, двойственная к транспортной.
курсовая работа [166,7 K], добавлен 17.07.2002Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлен 25.11.2011Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлен 01.05.2011Статистический подход к измерению правовой информации. Графический метод решения задач линейного программирования. Методика решения задач линейного программирования графическим методом. Количество информации как мера неопределенности состояния системы.
контрольная работа [79,4 K], добавлен 04.06.2010Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций.
курсовая работа [126,5 K], добавлен 21.05.2010Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Сущность графического метода нахождения оптимального значения целевой функции. Особенности и этапы симплексного метода решения задачи линейного программирования, понятие базисных и небазисных переменных, сравнение численных значений результатов.
задача [394,9 K], добавлен 21.08.2010Системы линейных уравнений и интерпретация их решений как пересечение гиперплоскостей в n-мерном координатном пространстве. Размерность и подпространства линейного пространства. Оптимизационные задачи линейного программирования. Суть симплекс-метода.
курсовая работа [132,2 K], добавлен 10.01.2014Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.
задача [26,1 K], добавлен 27.11.2015Предназначена библиотеки "simplex" для оптимизации линейных систем с использованием симплексного алгоритма. Построение экономико-математической модели формирования плана производства. Основные виды транспортных задач, пример и способы ее решения.
курсовая работа [477,9 K], добавлен 12.01.2011Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.
контрольная работа [551,9 K], добавлен 27.08.2009Однородные системы линейных неравенств и выпуклые конусы. Применение симплекс-метода для отыскания опорного решения системы линейных неравенств, ее геометрический смысл. Основная задача линейного программирования. Теорема Минковского, ее доказательство.
курсовая работа [807,2 K], добавлен 03.04.2015Определение допустимого решения задачи линейного программирования методом введения искусственного базиса. Целочисленное линейное программирование с булевскими переменными. Поиск минимума функции методом градиентного спуска. Одномерная минимизация.
курсовая работа [281,7 K], добавлен 27.05.2013Основные понятия математического моделирования, характеристика этапов создания моделей задач планирования производства и транспортных задач; аналитический и программный подходы к их решению. Симплекс-метод решения задач линейного программирования.
курсовая работа [2,2 M], добавлен 11.12.2011
