Оптимальное программирование

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

Специальность «Государственное и муниципальное управление»

Контрольная работа по дисциплине:

«Экономико-математические методы»

на тему: «Оптимальное программирование»

Содержание

Введение

1. Теория оптимального программирования

2. Основные понятия линейного программирования

3. Области применения линейного программирования

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

Заключение

Список использованных источников

Введение

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

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

Оптимальное программирование -- применение в экономике методов математического программирования. Часто эти термины определяют как однозначные.

Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

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

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

1. Теория оптимального программирования

Оптимальное программирование [optimal programming] -- применение в экономике методов математического программирования. Часто эти термины определяют как однозначные. Однако, по-видимому, правильнее другое толкование: Оптимальное программирование, включает, с одной стороны, экономические дисциплины, использующие математику (способы разработки планов и программ, т. е. оптимальное планирование, методы регулирования хозяйственной деятельности, расчета оптимальных цен и т. п.), а с другой -- собственно математическое программирование, которое применяется как в экономике, так и за ее пределами.

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

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

Модель задачи математического программирования включает:

1) совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.);

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

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

2. Основные понятия линейного программирования

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

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

Изучение подобных задач привело к созданию новой научной дисциплины линейного программирования и открыло новый этап в развитии экономико-математических методов.

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

· математические модели очень большого числа экономических задач линейны относительно искомых переменных;

· эти типы задач в настоящее время наиболее изучены;

· для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

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

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

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

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

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

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

Математическая модель любой задачи линейного программирования включает в себя:

· максимум или минимум целевой функции (критерий оптимальности);

· систему ограничений в форме линейных уравнений и неравенств;

· требование неотрицательности переменных.

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

3. Области применения линейного программирования

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

- математические модели большого числа экономических задач линейны относительно искомых переменных;

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

- многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования

,

.

Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства:

,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

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

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

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

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

Транспортная задача -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Рассмотрим пример решения транспортной задачи.

Х_is - количество товара, которое необходимо перевезти

i - склад

s - магазин

Целевая функция:

L(x) = 2_x11 + 9_x12 + 7_x13 + x₂₁ + 5_x23 +5_x31 + 4_x32 + 100_x33 + 2_x41 + 3_x42 +

+ 6_x43 min

Ограничения по запасам:

x₁₁ + x₁₂ + x₁₃ = 25

x₂₁ + x₂₂ + x₂₃ = 50

x₃₁ + x₃₂ + x₃₃ = 35

x₄₁ + x₄₂ + x₄₃ = 75

Ограничения по потребностям:

x₁₁ + x₂₁ + x₃₁ + x₄₁ = 45

x₁₂ + x₂₂ + x₃₂ + x₄₂ = 90

x₁₃ + x₂₃ + x₃₃ + x₄₃ = 50

Область допустимых решений:

x_is > или = 0

x_is = целое число, т.к. мы находим количество штук.

Решение:

Заключение

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

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

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

Список использованных источников

1. Волошин, Г. Я. Методы оптимизации в экономике. Учебное пособие/ Г. Я. Волошин. М: ДиС, 2004. 320 c.

2. Глухих И.Н. Теория систем и системный анализ: Электронное учебное пособие. - Тюмень: Тюменский государственный университет, 2003.

3. Дубина А.Г., Орлова С.С., Шубина И.Ю., Хромов А,В. Excel для экономистов и менеджеров. СПб.:Питер,2004. 295 с.

4. Карманов В.Г. Математическое программирование: учебное пособие для студентов вузов. М.: Физматлит, 2001. 264 с.

5. Кузнецов А.В. Математическое программирование: учебное пособие для вузов. М.: Высшая школа, 1976. 352 с.

Размещено на Allbest.ru