Краткий курс лекций Саратов 2012 министерство сельского хозяйства






НазваниеКраткий курс лекций Саратов 2012 министерство сельского хозяйства
страница2/7
Дата публикации21.01.2015
Размер1.23 Mb.
ТипУчебное пособие
e.120-bal.ru > Документы > Учебное пособие
1   2   3   4   5   6   7

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

Модели линейного программирования.
Нередко экономические задачи имеют не единственное решение и требуется выбрать лучшее – оптимальное из них. Моделирование таких задач сводится к задачам математического программирования (ЗМП).

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

Сформулируем в общем виде ЗМП:
(7)
при условиях
(8)
(9)
где целевая функция, условия (8) – специальные ограничения, условия (9) – общие ограничения ЗМП.

Точку , координаты которой удовлетворяют ограничениям (8) и (9), называют допустимым решением ЗМП.

Множество всех допустимых решений ЗМП называют допустимым множеством.

Допустимое решение , удовлетворяющее соотношению (7), называют оптимальным решением ЗМП.

Если в ЗМП целевая функция и функции , – линейные, то имеем общую задачу линейного программирования (ЗЛП):
(10)

(11)

(12)
В зависимости от вида специальных ограничений различают следующие ЗЛП:

    • каноническая ЗЛП, включающая в качестве ограничений (11) только уравнения, т. е.


;


    • стандартная ЗЛП, включающая в качестве ограничений (11) только неравенства, т. е.



Рассмотрим следующие примеры моделей, приводимых к ЗЛП.

Пример 1. Экономико-математическая модель задачи о планировании производства.

На заводе имеются запасы трех видов сырья: , и , из которого можно наладить производство двух видов товаров: и . Запасы сырья, норма его расхода на производство единицы товаров, а также прибыль от реализации единицы каждого товара приведены в таблице 1 (цифры условные).


Таблица 1

Сырье

Товары










Прибыль






3

1

1

25



3

2

4

34

Запасы

126

48

72





Необходимо составить такой план производства товаров, при котором прибыль от их реализации будет максимальной.

Решение.

План производства зададим числами и , где – количество единиц товара , которое следует произвести . Неизвестные и должны удовлетворять условиям
или , (13)

(14)
Поясним смысл первого неравенства системы (13). В левой части записано количество сырья , которое расходуется на выпуск единиц товара и единиц товара . Это количество не должно превышать имеющегося запаса сырья , т. е. 126 единиц. Аналогичный смысл имеют второе и третье неравенства системы (13).

Прибыль, предприятия от реализации плана (, ) производства товаров, очевидно, составит
. (15)
В интересах предприятия максимизировать эту прибыль. Следовательно, чтобы составить план производства товаров, при котором прибыль от их реализации будет максимальной нужно решить стандартную ЗЛП: при условиях (13) и (14):

Пример 2. Экономико-математическая модель задачи о диете.

Имеются два вида продуктов: и . Содержание в 1 кг питательных веществ A, B и C, ежесуточные потребности организма V в них и стоимость S 1 кг продуктов приведены в таблице 2
Таблица 2

Витамины

Продукты

A

B

C

S






1

3

1

8



3

1

8

16

V

6

9

8





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

Решение.

Пусть и – искомые количества продуктов и соответственно. Их стоимость составляет

Общее количество питательного вещества A в обоих видах продуктов равно . Оно должно быть не меньше 6 единиц: .

Аналогичные неравенства составим для питательных веществ B и C: и .

Очевидно, и .

Таким образом, получим следующую стандартную ЗЛП:
(16)
при условиях
(17)
Геометрический метод решения задач линейного программирования.
Геометрический метод решения ЗЛП – простой и наглядный способ решения стандартных ЗЛП с двумя переменными:
(18)
при условиях
(19)
Рассмотрим следующие геометрические объекты.
Выпуклые множества и их свойства.
Множество точек называется выпуклым, если оно вместе с произвольными двумя своими точками содержит весь отрезок, соединяющий эти точки.

Справедливо утверждение: пересечение любого числа выпуклых множеств есть выпуклое множество.

Каждое неравенство системы ограничений (19) геометрически определяет полуплоскость с граничной прямой , или , или .

Поясним сказанное. Рассмотрим, например, неравенство .

Посмотрим прямую L: (см. рис.2).

Рис. 2

Для того чтобы определить, какая полуплоскость удовлетворяет заданному неравенству, необходимо выбрать любую точку, не лежащую на L, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Как правило, в качестве «пробной» берут точку .

Подставим в заданное неравенство: . Получим истинное утверждение. Следовательно, заданному неравенству соответствует нижняя полуплоскость (заштрихованная на рис. 2), содержащая точку .

Полуплоскости, описываемые неравенствами (19) – выпуклые множества. Их пересечение – область допустимых решений ЗЛП, которая является также выпуклым множеством.

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

Ввиду неравенств и многоугольник решений всегда находится в первом квадранте координатной плоскости .

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

Прямая называется линией уровня функции F. Иными словами на множестве всех точек линии уровня функции F она сохраняет постоянное значение .
Алгоритм решения ЗЛП геометрическим методом.


  1. Строится многоугольник решений.

  2. Строится вектор набла, перпендикулярно ему проводятся линии уровня и при этом учитывают, что оптимальное решение ЗЛП находится в угловой точке многоугольника решений.

  3. Первая точка встречи линии уровня с многоугольником решений определяет минимум целевой функции.

  4. Последняя точка встречи линии уровня с многоугольником решений определяет максимум целевой функции.

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

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


Пример 1. Экономико-математическая модель задачи о планировании производства.

Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей из (17) в виде

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

Построим вектор набла . Последней точкой встречи линии уровня с многоугольником решений будет точка (см. рис.3) с координатами: , , являющимися решениями системы уравнений

Подставив координаты точки в целевую функцию, найдем



Рис. 3
Пример 2. Экономико-математическая модель задачи о диете.

Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей из (17) в виде
или

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

Построим вектор набла . Первой точкой встречи линии уровня с многоугольником решений будет точка (см. рис. 4) с координатами: , , являющимися решениями системы уравнений:


Подставив координаты точки в целевую функцию, найдем



Рис. 4

1   2   3   4   5   6   7

Похожие:

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconРоссийской Федерации Федеральное государственное бюджетное образовательное...
Учет и анализ: Краткий курс лекций для студентов направления подготовки 080200. 62 Менеджмент / Сост.: Кудряшова Е. В., Павленко...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconИнформация подготовлена по материалам, полученным из сети «Интернет»11. 03. 2012
России по реализации федеральной целевой программы «Социальное развитие села до 2013 года». Как сообщили 6 марта корреспонденту в...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconСписок новых книг, поступивших в библиотеку в ноябре 2012 года
Агафонов В. В. Криминалистика: краткий курс лекций – М.: Юрайт, 2013. – 184с. 10 экз

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconПоложение о Министерстве сельского хозяйства и продовольствия Республики...
Министерство сельского хозяйства и продовольствия Республики Татарстан (далее Министерство) является исполнительным органом государственной...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconПрограмма импортозамещения продукции в пензенской области на 2015-2017 годы
Министерство сельского хозяйства Пензенской области, Министерство строительства и жилищно-коммунального хозяйства Пензенской области,...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций Производственная безопасность. Часть 3
Пламя возникает в результате сложного взаимодействия химических и физических процессов

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций по экономике апк
Федеральное государственное образовательное учреждение высшего профессионального образования Ставропольский государственный аграрный...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconД. А. Медведев [и др.] // Экономика сельского хозяйства России. 2012. № С. 7-13
Агропромышленный комплекс требует повышенного внимания [Текст] / Д. А. Медведев [и др.] // Экономика сельского хозяйства России....

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций по дисциплине
Учебное пособие предназначено для студентов Стгау всех направлений, изучающих курс «История, традиции и обычаи народов Северного...

Краткий курс лекций Саратов 2012 министерство сельского хозяйства iconКраткий курс лекций по статистике автор: ильина г. Г.,к э. н
Статистика-наука,которая изучает приемы и методы сбора и обработки информации о каких –либо явлениях и процессах, происходящих в...






При копировании материала укажите ссылку © 2016
контакты
e.120-bal.ru
..На главную