Тема 1. 1 общая и основная задачи линейного программирования

Ульяновск

Конспект лекций

для специальности базового уровня

· 230105 (2203) Программное обеспечение вычислительной техники и автоматизированных систем

МАТЕМАТИЧЕСКИЕ МЕТОДЫ. КОНСПЕКТ ЛЕКЦИЙ: учеб. пособие для студентов специальностей 230105 (2203) базового уровня / Авт.-сост. А.А. Мардамшина - Ульяновск: УАвиаК, 2011 – стр.

Учебное пособие по дисциплине «Математические методы» предназначено для студентов Ульяновского Авиационного колледжа, обучающихся на специальностях 230105 (2203).

Содержит учебный материал по 5 разделам. Может служить пособием при подготовке к уроку, к экзамену.

Рецензенты:

Камышова Г.А.	Преподаватель высшей категории Ульяновского авиационного колледжа
Кондратьев А.Е.	кандидат физико-математических наук, доцент кафедры Информационных Технологий факультета Математики и Информационных Технологий Ульяновского Государственного Университета

СОДЕРЖАНИЕ

РАЗДЕЛ 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1.1 Общая и основная задачи линейного программирования.................................... 10

1.2 Симплексный метод решения ЗЛП......................................................................... 15

1.3 Прямая и двойственная ЗЛП. Двойственный симплекс-метод............................ 15

1.4 Транспортная задача.................................................................................................. 20

РАЗДЕЛ 2. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

2.1 Нелинейное программирование.............................................................................. 24

2.2 Градиентные методы................................................................................................ 30

РАЗДЕЛ 3. СЕТЕВОЕ ПРОГРАММИРОВАНИЕ.

3.1 Алгоритмы на сетях.................................................................................................. 39

3.2 Сетевое моделирование............................................................................................ 46

РАЗДЕЛ 4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

3.1 Модели динамического программирования.......................................................... 39

РАЗДЕЛ 5. ТЕОРИЯ ИГР.

3.1 Основные понятия теории игр................................................................................ 39

Литература....................................................................................................................... 63

РАЗДЕЛ 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

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

(1)

при условиях

(2)

(3)

(4)

где - заданные постоянные величины и.

Определение 1.2 Функция (1) называется целевой функцией (или линейной формой) задачи (1) – (4), а условия (2) – (4) – ограничениями данной задачи.

Определение 1.3 Стандартной (или симметричной} задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (2) и (4), где k = m и l = n.

Определение 1.4 Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где k = 0 и l = п.

Определение 1.5 Совокупность чисел,удовлетворяющих ограничениям задачи (2) – (4), называется допустимым решением (или планом).

Определение 1.6 План, при котором целевая функция задачи (1) принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции (1) при плане Х будем обозначать через. Следовательно, X^*– оптимальный план задачи, если для любого Х выполняется неравенство [соответственно ].

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

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

В том случае, когда требуется найти минимум функции, можно перейти к нахождению максимума функции, поскольку.

Ограничение-неравенство исходной задачи линейного программирования, имеющее вид “ ”, можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида “ ” – в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство

преобразуется в ограничение-равенство

(5)

а ограничение-неравенство

– в ограничение-равенство

(6)

В то же время каждое уравнение системы ограничений

можно записать в виде неравенств:

(7)

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

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

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

Дата добавления: 2014-01-15