Переход от одной формы модели ЗЛП к другой

Цель:

· изучение основных понятий о ЗЛП,

· изучение моделей ЗЛП,

· алгоритм перехода от одной формы ЗЛП к другой;

· изучение алгоритма графического метода решения ЗЛП;

· формирование навыков самостоятельной работы по заданному алгоритму;

· формирование умений самостоятельно пополнять знания, пользоваться учебной литературой и др. источниками.

 

 

В результате изучения темы студент должен знать:

ü Постановку ЗЛП, модели ЗЛП,

ü алгоритм перехода от одной формы ЗЛП к другой,

ü алгоритм графического метода решения ЗЛП.

В результате изучения темы студент должен уметь:

ü По заданному алгоритму осуществлять переход от одной формы ЗЛП к другой,

ü используя алгоритм графического метода решения ЗЛП, по заданному образцу решать ЗЛП графическим методом.

 

Литературные источники:

 

1. Богомолов Н.В. Практические занятия по математике. - М.: Дрофа - 2010.- 400 с.

2. Богомолов Н.В., Сергиенко Л.Ю. Сборник дидактических заданий по математике. - М.-Дрофа-2009.

3. Григорьев С.Г. Математика: учебник для студентов сред. проф. учреждений / С.Г. Григорьев, С.В. Задулина; под ред. В.А. Гусева. - 2-е изд., стер. - М.: Издательский центр «Академия», 2007. - 384 с.

4. Кремер Н.Ш. Теория вероятностей и математическая статистика: Учебник для вузов. - 4-е изд., перераб. и доп. - М.: ЮНИТИ-ДАНА, 2010. - 573 с.

5. Спирина М.С. Теория вероятностей и математическая статистика: учебник для студ. учреждений сред. проф. образования / М.С. Спирина, П.А. Спирин. - М.: Издательский центр «Академия», 2007. - 352 с.

6. Спирина М.С. Дискретная математика: учебник для студ. учреждений сред. проф. образования / М.С. Спирина, П.А. Спирин. - М.: Издательский центр «Академия», 2010. - 368 с.

7. П.Е. Данко, А.Г. Попов, Т.Я. Кожевникова Высшая математика в упражнениях и задачах. Часть 1 и 2. - М.: Высшая школа, 2008.

8. Н.В. Богомолов Задачи по математике с решениями. - М.: Высшая школа, 2006

9. Н.В. Богомолов, П.И. Самойленко Математика. - М.: Дрофа, 2004

10. З.И. Гурова, С.Н. Каролинская, А.П. Осипова Математический анализ. Начальный курс с примерами и задачами- М.: ФИЗМАТЛИТ, 2002

11. И.Д. Пехлецкий Математика. - М.: Мастерство, 2001

12. В.Ф. Бутузов, Н.И. Крутицкая. Математичесий анализ в вопросах и задачах. - М.: Физматлит, 2000

1. Изучение нового материала.

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

 

1.1 Модели ЗЛП могут находиться в трех формах:

- общая;

- стандартная (графический метод решения ЗЛП);

- каноническая (симплекс-метод).

1. Общая форма модели ЗЛП:

z = c₁x₁ + c₂x₂ + ... + c_nx_n → max (min)

 

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n      R₁   a₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n      R₂     a₂

  ……     ……       …..

a_m1x₁ + a_m2x₂ + ... + a_mnx_n   R_m     a_m

R₁ , R₂ , … R_m – знаки (=,≤ , ≥ )

 

x_j ≥ 0, j = , k ≤ n

 

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

 

2. Стандартная форма модели ЗЛП:

z = c ₁ x ₁ + c ₂ x ₂ + ... + c_nx_n → max (min)

 

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤  a₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n    ≤ a₂

  ……     ……       …..

a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ a_m

x_j ≥ 0, j =

Особенности	1) условие неотрицательности накладывается на все переменные
	2) целевая функция исследуется на максимум/ минимум
	3) система ограничений представлена в виде неравенств (нежесткие условия)

 

3. Каноническая форма модели ЗЛП:

z = c ₁ x ₁ + c ₂ x ₂ + ... + c_nx_n → min

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n =  a₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n    = a₂

  ……     ……       …..

a_m1x₁ + a_m2x₂ + ... + a_mnx_n = a_m

x_j ≥ 0, j =

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

 

Переход от одной формы модели ЗЛП к другой

1) Преобразование переменных

Если х _k ≤ 0, введем х _k ′ = – х _k , тогда х _k ′ ≥ 0

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

Если какая-либо переменная х _t может принимать любые значения, то ее заменяют разностью двух неотрицательных переменных х _t ′ и х _t ′′ т.е. х _t = х _t ′ – х _t ′′ , где х _t ′ ≥0, х _t ′′ ≥ 0.

 

2) Преобразование ограничений

Если какое-либо из ограничений в модели имеет вид неравенства, то оно преобразуется в уравнение так:

Если неравенство имеет смысл ≤ 0, то к левой части неравенства прибавляют некоторую неотрицательную переменную.

Если неравенство имеет смысл ≥ 0, то из левой части неравенства вычитают неотрицательную переменную.

 

Эти переменные называют балансовыми.

Балансовая переменная входит в целевую функцию с коэффициентом нуль. Балансовая переменная принимает значение индекса последовательно после уже имеющихся.

 

3) Преобразование целевой функции

Если в модели задана целевая функция на нахождение максимального значения, то вместо задачи z → max будем решать задачу z ′ = – z → min.

В окончательном ответе необходимо опять поменять знак на противоположный, т.е. min z = – max z ′.

 

 

---

Дата добавления: 2020-11-23; просмотров: 376; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!