Васильев е. П. Экономико математические методы и модели часть I

Скачать 1.03 Mb.

Название	Васильев е. П. Экономико математические методы и модели часть I
страница	4/19
Дата публикации	02.07.2015
Размер	1.03 Mb.
Тип	Учебное пособие

100-bal.ru > Экономика > Учебное пособие

1 2 3 4 5 6 7 8 9 ... 19

1.2. Формы записи задач линейного программирования: общая, каноническая и стандартная

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

Общая форма ЗЛП

- это задача максимизации или минимизации линейной функции с линейными ограничениями в виде как равенств, так и неравенств:

Каноническая форма ЗЛП

- это задача максимизации линейной функции с линейными ограничениями в виде равенств:

Стандартная форма записи ЗЛП

– это задача максимизации (минимизации), если все ограничения – неравенства

Замечания.

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

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

Задача минимизации (максимизации) функции Z эквивалентна задаче максимизации (минимизации) функции (-Z),

так как

min Z= -max(-Z).

Уравнение АX=В эквивалентно двум неравенствам: .
Переход от неравенств к равенствам может быть легко осуществлен путем добавления в неравенства дополнительных переменных, которые затем включаются в оптимизируемую функцию с нулевыми коэффициентами.

Например, от неравенства

a_i₁x₁+a_i₂x₂+...+a_inx_n b_i ,

перейдем к уравнению, добавив новую балансовую переменную х_n₊₁

a_i1x₁+a_i2x₂+...+a_inx_n- b_i+х_n+1=0 ,

где х_n₊₁0.

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

2. Графический метод решения задачи линейного программирования

При решении ЗЛП графическим методом необходимо, чтобы задача была записана в стандартной форме и переменных в задаче было две

.

Запишем математическую модель ЗЛП.

Найти решение

такое, чтобы функция

(1)

достигала экстремума

и выполнялись условия:

, или

, (2)
а также

,

или

(3)
Алгоритм решения ЗЛП графическим методом:

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

удовлетворяющую ограничениям (2) и (3);

Построить вектор – градиент целевой функции

Построить линию уровня – прямую, перпендикулярную вектору-градиенту ( );
Найти:

«точку входа» - minz – первая точка пересечения линии уровня с ОДР,

«точку выхода» - maxz – последняя точка пересечения линии уровня с ОДР.

Пример 3.

Решить графически следующую ЗЛП:

найти

, если

Решение.

Строим ОДР:

построим границы области – прямые:

Далее строим вектор-градиент

, перпендикулярный к линиям уровня

Перемещаем линию уровня - прямую

в направлении вектора

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

;

Итак, точка найдена А(

)

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

.

Перемещая далее линию уровня в направлении вектора

, определим точку «выхода» из области решений.

Наибольшее значение функция принимает в точке В (6; 0) и

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

Рассмотрим следующие задачи.

Пример 4.

Найти наибольшее и наименьшее значения функции.

Z = 2х₁+2х₂

при ограничениях х₁-3х₂

3

-3х₁+х₂ 3

х₁0, х₂0

Решение.

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

Перемещая линию уровня (прямая l) в направлении вектора-градиента (2,2), найдем «точку входа» О (0,0), таким образом,

Z_min= Z(0) = 0;

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

Итак, оптимального решения, при котором целевая функция достигает максимума, не существует, Z_max

Пример 5 (альтернативный оптимум).

Найти наибольшее значение функции Z = 2х₁+2х₂

при ограничениях х₁+х₂

х₁-2х₂

х₁

х₂

Решение.

Построим ОДР

Очевидно, что вектор-градиент

(2,2) ортогонален границе области – отрезку АВ. Линия уровня l

.

Таким образом «точки выхода» - это любые точки отрезка АВ.

Координаты точки А( 0,4);

координаты точки В найдем из системы:
х₁+х₂=4

х₁-2х₂=2

3х₂= 2; х₂=

; х₁= 4 -

, итак, В (

.

Значение целевой функции будет одно и то же в любой точке отрезка АВ, оно равно

Z(А) = Z(В) = 2·0 + 2·4 = 8.

Данная ЗЛП имеет бесконечно много оптимальных решений

х₁ = t

х₂= 4-t

где 0

, причем Z_max = 8.
Пример 6.

Найти Z = х₁ – 2х₂max

при ограничениях х₁+ х₂

2х₁+ 2х₂

х₁

х₂ 0

Решение.

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

1 2 3 4 5 6 7 8 9 ... 19

Похожие:

	Методические рекомендации по изучению дисциплины «экономико-математические... Методические рекомендации по изучению дисциплины «экономико-математические методы и модели»		Фгбоу впо «сгэу» от 09. 11. 2012г. № Решение ученого совета Самарского... «Математическое моделирование», «Математические модели в финансовых операциях», «Методы оптимизации», «Экономико-математические методы...
	Математические методы и модели Габрин К. Э., Математические методы и модели: Семестровое задание и методические рекомендации к решению задач. – Челябинск: Издательство...		Программа дисциплины «Экономико-математические методы и модели в... ...
	Методические указания по выполнению реферата по учебной дисциплине... Государственное образовательное учреждение высшего профессионального образования		Методические указания по выполнению реферата по учебной дисциплине... Государственное образовательное учреждение высшего профессионального образования
	Методические указания по выполнению реферата по учебной дисциплине... Государственное образовательное учреждение высшего профессионального образования		Экономико-математические методы и модели оценки эффективности реализации... И наступил тот месяц, и пришел тот день, и настал тот час, и свершилось событие, в которое многие верили…
	Горюшкин А. А., Хуторецкий А. Б. Математические модели и методы исследования... Горюшкин А. А., Хуторецкий А. Б. Математические модели и методы исследования операций: курс лекций: Учеб пос. Новосиб национ иссл...		Программа дисциплины «Экономико-математические методы и модели в... ...
	План чтения лекции по учебной дисциплине «Математические методы» Раздел №2 Учебные и воспитательные цели: изучить основные виды задач линейного программирования, их математические модели		Тема: «Математические расчеты семейного бюджета» Математическая экономика – теоретическая и прикладная наука, предметом которой являются математические модели экономических объектов...
	Методические рекомендации для студентов по изучению дисциплины «стахование... Знания в области страхования необходимы для успешного прохождения производственной практики и освоения дисциплин Экономико-математические...		Рабочая программа дисциплины «Экономико-математические методы в дорожном строительстве» Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Опыт использования учебно-методического интернет-ресурса в преподавании... Оценочные средства для контроля успеваемости и результатов освоения учебной дисциплины 28		Рабочая программа дисциплины «Экономико-математические методы в стратегическом управлении» Дисциплина является предшествующей для следующих дисциплин: «Корпоративные информационные системы», «Компьютерные технологии в управлении»,...

Школьные материалы