Виды экономических задач линейного программирования

Понятие линейного программирования. Виды задач линейного программирования

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

Линейное программирование – математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах n -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

Задача линейного программирования (ЛП), состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Линейное программирование применяется при решении следующих экономических задач:

1. Задача управления и планирования производства.

2. Задач определения оптимального размещения оборудования на морских судах, в цехах.

3. Задача определения оптимального плана перевозок груза (транспортная задача).

4. Задача оптимального распределения кадров.

5. Задач о смесях, диете (планирование состава продукции) и т.д.

3. МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ЕЁ ПРЕДСТАВЛЕНИЕ В ЭЛЕКТРОННЫХ ТАБЛИЦАХ MS EXCEL.

Традиционно наукой управления называют построение детально разработанных моделей, в результате анализа которых принимаются управленческие решения. Сегодня миллионы менеджеров для анализа деловых задач применяют электронные таблицы. Современные электронные таблицы имеют много мощных средств, которые можно использовать для более точного анализа моделей, в результате чего могут приниматься более взвешенные и близкие к оптимальным решения. С учетом все более широкого применения электронных таблиц в процессе управления будущим специалистам необходимо владеть профессиональными навыкам разработки моделей – как «спланировать» чистый рабочий лист так, чтобы получить полезную и практическую модель деловой ситуации, не углубляясь в алгоритмические и математические тонкости расчетов.

Основные этапы создания модели линейного программирования в Excel:

1. Написание и проверка символической модели линейного программирования. Модель записывается на бумаге в математическом виде.

2. Создание и отладка табличной модели линейного программирования. На основе символической модели ЛП создается ее представление в Excel.

3. Попытка оптимизации модели с помощью надстройки ПОИСК РЕШЕНИЯ.

4. ИСПОЛЬЗОВАНИЕ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ.

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

Поиск решения – это надстройка, которая предназначена для оптимизации моделей при наличии ограничений. Она состоит из двух программных компонентов: программы написанной на языке Visual Basic, который транслирует представленную на рабочем письме информацию для внутреннего представления, которая используется другой программой. Вторая программа находится в памяти компьютера в виде отдельного программного модуля. Она выполняет оптимизацию и возвращает найденное решение первой программе, которая возобновляет данные на рабочем листе. С помощью ее можно найти оптимальное значение формулы, которая сохраняется в целевой ячейке. Эта процедура работает с группой ячеек, которые непосредственно связанные с формулой в целевой ячейке. Чтобы получить результат по формуле в целевой ячейке, процедура изменяет значение в ячейках, которые влияют на поиск. Для того, чтобы уменьшить множественное число значений, которые используются в модели задачи, применяют ограничение. Эти ограничения могут содержать ссылку на другие ячейки, которые влияют на поиск.

Общий алгоритм работы с надстройкой Поиск решения.

1. В меню Сервис выбрать команду Поиск решения.
2. В поле Установит целевую ячейку введите адрес ячейки, в которй находится формула, для оптимизации модели.
3. Для того, чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Максимальному значению. Для того, чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение Минимальному значению. Для того, чтобы целевая ячейка приобретала значение конкретного числа, установите переключатель в положение Значение и введите соответствующее число.
4. В поле Изменяя ячейки введите адреса ячеек, которые изменяют свои значения, разделяя их запятыми. Изменяемые ячейки должны быть прямо или непрямо связанные с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
5. В поле Ограничения введите все ограничения, которые налагаются на поиск решения.
6. Нажмите кнопку Выполнить.
7. Для сохранения найденного решения установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение. Для возобновления входных данных установите переключатель в положение Восстановить исходные значения.
8. Для того, чтобы прервать поиск решения, нажмите клавишу Еsс. MS Excel пересчитает лист с учетом найденных значений ячеек, которые влияют на результат.

Алгоритм роботи з надбудовою Поиск решения.

5. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩИ ПРОГРАММЫ MS EXCEL.

Пример. Кондитерский цех для изготовления трех видов карамели А, В, С использует три основных вида сырья: сахар, патоку и фруктовое пюре. Нормы затрат сахара на изготовление 1кг карамели каждого вида соответственно уровни: 0,8кг; 0,5кг; 0,6кг; патоки – 04кг; 0,4кг; 0,3кг; фруктового пюре – 0кг; 0,1кг; 0,1кг. Конфеты можно производить в любых количествах (реализация обеспечена), но запас сырья ограниченный: запасы сахара – 80кг, патоки – 60кг, фруктового пюре – 12кг. Прибыль от реализации 1кг карамели вида А составляет 10грн., вида В – 11грн., вида С – 12грн.

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

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник

Линейное программирование в экономике

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

Основы экономико-математического моделирования и линейного программирования

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

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

Все формы математического моделирования любого экономического объекта предполагают последовательную реализацию следующих этапов:

1. описание экономической задачи;
2. построение математической модели (т.е. математическая формализация экономической ситуации);
3. практическое использование математической модели, получение решения и его анализ на допустимость, устойчивость и другие критерии;
4. экономическая интерпретация полученного решения.

Характеристика линейного программирования

Линейное программирование является одним из разделов этой математической теории, которая зачастую используется в науке для решения экономических задач. Впервые теоретические основы линейного программирования были сформулированы и опубликованы в 1939 году советским математиком и экономистом Л.В. Канторовичем. В том числе и за эту работу он в 1975 году был удостоен Нобелевской премии по экономике.

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

Общая задача линейного программирования (еще называется стандартной задачей) заключается в нахождении минимума линейной целевой функции, которая принимает следующий вид:

Рисунок 1. Линейная функция. Автор24 — интернет-биржа студенческих работ

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

Кроме того, допускаются и другие приемы работы с представлением задачи линейного программирования. Так, если в задаче, нацеленной на определение максимальной величины, поменять знаки у коэффициентов (плюс на минус, или наоборот), то задача уже будет нацелена на определение минимальной величины.

Существует несколько «классических» экономических задач, решение которых находится с помощью применения методов линейного программирования. Перечислим эти примеры:

• задача производственного планирования – заключается в составлении хозяйствующим субъектом такого плана производства продукции нескольких видов (при ограниченном объеме имеющихся у него материальных, трудовых и финансовых ресурсов), реализация которого принесет ему максимальный доход;
• задача потребителя – заключается в совершении покупателем (потребителем) выбора между продуктами, которые представлены в магазине, т.е. могут быть им приобретены при ограниченном объеме имеющихся у него денежных средств (бюджетное ограничение); причем этот выбор должен принести ему наибольшее удовлетворение;
• транспортная задача – заключается в составлении такого плана перевозок продукции со станций хранения до пунктов доставки (с учетом ограничений по объемам загрузки транспортных средств и потребностям пунктов доставки), реализация которого позволит минимизировать объем издержек, вызванных этими перевозками.

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

Методы решения задач линейного программирования

Для решения общей задачи линейного программирования в большинстве случаев специалисты обращаются к такому известному методу, как симплекс-метод. Он был разработан американским математиком Джорджем Бернард Данцигом и впервые представлен публике в 1949 году.

Этот метод справедливо считается одним из самых эффективных алгоритмов решения задач линейного программирования – при решении прикладных задач он неоднократно демонстрировал хорошие результаты. Залог успеха симплекс-метода состоит в его комбинаторном характере, т.е. он предполагает, что при поиске оптимального решения необходимо последовательно перебрать все вершины многогранника допустимых решений.

Ещё один метод решения задач линейного программирования – это метод эллипсоидов, который относится к категории полиномиальных алгоритмов. Его разработчиком (относительно задач линейного программирования) считается советский математик Л. Хачиян, который предложил данный метод в 1979 году.

Метод эллипсоидов кардинальным образом отличается от симплекс-метода, так как имеет некомбинаторную природу. В вычислительном плане этот метод оказался неперспективным, однако именно он стал предвестником создания и использования методов внутренней точки. Методы внутренней точки трактуют задачу линейного программирования непрерывно, поэтому поиск осуществляется вдоль траекторий в пространстве переменных задачи.

Источник