Юридический техникум

Рассмотрено и одобрено ПЦК г. Кропоткин программирования

Председатель ПЦК

Покалицына О.В.

План чтения лекции по учебной дисциплине

«Математические методы»
Раздел № 2. Линейное программирование.
Тема № 2.2. Основная задача линейного программирования.
Занятие №

Место проведения: аудитория.
Литература:
1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.:
Наука, 1980.
2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001

Учебные вопросы и расчет времени
|№п/п |Учебные вопросы |Время, мин|Методические |
| | | |указания |
|1. |Основная задача ЛП (ОЗЛП). | | |
|2. |Существование решения. | | |

Вводная часть. Организационный момент. План занятия. Основные требования.
Основная часть.
1. Основная задача ЛП (ОЗЛП).

Любую задачу линейного программирования можно свести к стандартной форме, так называемой «основной задаче линейного программирования» (ОЗЛП), которая формируется так: найти неотрицательные значения переменные x1, x2,
…, xn, которые удовлетворяли бы условиям – равенствам: a11 x1 + a12 x2 + … +a1n xn = b1, a21 x1 + a22 x2 + … +a2n xn = b2, (6.1.)

……………………………….. am1 x1 +am2 x2 + … +amn xn = bm. и обращали бы в максимум линейную функцию этих переменных:

[pic] (6.2.)

Случай, когда L надо обратить не в максимум, а в минимум, легко сводится к простому: изменить знак L на обратный (максимизировать не L, а
L`=-L). Кроме того, от любых условий – неравенств можно перейти к условиям
– равенствам ценой введения некоторых новых «дополнительных» переменных.
Пусть требуется найти неотрицательные значения переменных x1,x2,x3, удовлетворяющие ограничениям – неравенствам

[pic] (6.3.)

[pic] и обращающие в максимум линейную функцию от этих переменных:

[pic] (6.4.)

Начнём с того, что приведём условия (6.3.) к стандартной форме, так, чтобы знак неравенства был (, а справа стоял нуль. Получим:

[pic] (6.5.)

[pic]

А теперь обозначим левые части неравенств (6.5.) соответственно через y1 и y2:

[pic] (6.6.)

[pic]

Из условий (6.5.) и (6.6.) видно, что новые переменные y1, y2 также должны быть неотрицательными.

Какая же теперь перед нами стоит задача? Найти неотрицательные значения переменных x1,x2,x3,y1,y2 такие, чтобы они удовлетворяли условиям
– равенствам (6.6.) и обращали в максимум линейную функцию этих переменных
(то, что в L не входит дополнительные переменные y1, y2, неважно: можно считать, что они входят, но с нулевыми коэффициентами). Перед нами – основная задача линейного программирования (ОЗЛП). Переход к ней от первоначальной задачи с ограничениями – неравенствами (6.3.) «куплен» ценой увеличения числа переменных на два (число неравенств).
2. Существование решения ОЗЛП и способы его нахождения.

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям – равенствам: a11 x1+a12 x2+…+a1n xn=b1, a21 x1+a22 x2+…+a2n xn=b2, (7.1.)