Зад лин прогр и мет их решения 16 12 08

Сыктывкарский государственный университет

Никитенков В.Л. Холопов А.А.

ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

И

МЕТОДЫ ИХ РЕШЕНИЯ

Учебное пособие и практикум

версия 16.12.08

Рекомендовано УМО по классическому университетскому образованию в качестве учебного пособия по методам решения задач математического программирования для студентов высших учебных заведений, обучающихся по специальности 010200 «Прикладная математика и информатика» и по направлению подготовки 511800 «Математика. Компьютерные науки»

Сыктывкар 2008

УДК 519.85 (075) ББК 22.1 Н 62

Никитенков В.Л., Холопов А.А.

Н 62 Задачи линейного программирования и методы их решения. Сыктывкар: Изд-во СыктГУ, 2008. 277 с. ISBN 978-5-87237-648-4

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

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

Рецензенты:

Громов Н.А. – д.ф.-м.н., профессор, зав. отделом математики (Коми Научный Центр УрО РАН);

Полещиков С.М. – д.ф.-м.н., профессор, зав.кафедрой высшей математики (Сыктывкарский лесной институт С-Петербургской лесотехнической академии).

3

СОДЕРЖАНИЕ

Стр.

ВВЕДЕНИЕ……………………………………………………………………………..5 1.ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ДЛЯ ЭКОНОМИЧЕСКИХ ЗАДАЧ…………………………………………………………………………………5

1.1Задача планирования производства продукции (ЗЛП на максимизацию)…….5

1.2Задача о составлении оптимального рациона (ЗЛП на минимизацию)……….7

2.ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП. ГРАФИЧЕСКИЙ СПОСОБ РЕШЕНИЯ ЗЛП ОТ ДВУХ ПЕРЕМЕННЫХ С ОГРАНИЧЕНИЯМИ-

НЕРАВЕНСТВАМИ…………………………………………………………………7

3.СИМПЛЕКС-МЕТОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ………………………………………………………….15

3.1Предварительные сведения……………………………………………………..15

3.2Геометрическая идея симплекс-метода………………………………………..18

3.3Алгоритм прямого симплекс-метода…………………………………………...20

3.4Метод искусственных переменных. Вспомогательная задача ЛП…………...31

4.ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ……….38

4.1Постановка транспортной задачи………………………………………………38

4.2Метод потенциалов для решения ТЗ…………………………………………...41

4.3Пример решения классической транспортной задачи...……………………...56

5.ЗАДАЧА ОБ АРЕНДЕ ОБОРУДОВАНИЯ…………………...…………………..66

5.1Предварительные сведения. Бесконтурные сети…...........................................66

7.1Векторы и матрицы……………………………………………………………...94

7.2Постановка задачи ЛП…………………………………………………………..97

7.3Выпуклость множества допустимых решений ЗЛП…………………………..98

7.4Характеристика угловых точек…………………………………………………99

7.5Достижимость оптимального решения ЗЛП в угловой точке множества допустимых решений………………………………………………………….. 100

УПРАЖНЕНИЯ И ЗАДАЧИ………………………………………………………..213

РЕКОМЕНДУЕМЫЙ БИБЛИОГРАФИЧЕСКИЙ СПИСОК……………………..275

5

ВВЕДЕНИЕ

Задачей линейного программирования (ЗЛП) называется задача отыскания экстремума (максимума или минимума) линейной функции от нескольких переменных при линейных ограничениях на эти переменные.

Пример: Найти максимальное значение функции f (x1 ,x2 ) = 2x1 + 5x2

при следующих ограничениях на переменные x1 и x2 .

x1 + x2 ≤ 1277x1 − x2 ≤ 83

x1 ≥ 0,x2 ≥ 0

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

x1 ≥ 0,x2 ≥ 0

называются ограничениями неотрицательности (или условиями неотрицательности), а система линейных неравенств и (или) уравнений называется системой ограничений ЗЛП. Запись ЗЛП с ограничениями-неравенствами выглядит следующим образом

f (x1 , x2 ) = 2x1 + 5x2 → max

x1 + x2 ≤127

7x1 − x2 ≤ 83 }

x1 ≥ 0, x2 ≥ 0 }

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

1. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ДЛЯ ЭКОНОМИЧЕСКИХ ЗАДАЧ

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

1.1. Задача планирования производства продукции (ЗЛП на максимизацию).

Некоторое предприятие в течение планового периода выпускает 2 вида продукции, например, табуретки и стулья. При их производстве используются три вида ресурсов. Дан-

6

быль была максимальна. Итак, цель задачи - получение максимальной прибыли. Выберем в качестве параметров, характеризующих процесс планирования производства продукции, число выпускаемых табуреток (переменная x1) и выпускаемых стульев (переменная x2). Выразим через выбранные неизвестные суммарную прибыль от реализации всей продукции

f (x1 , x2 ) = 4x1 + 5x2

Она включает в себя прибыль от реализации всех табуреток ( 4x1) и выпускаемых стульев (5x2 ). Цель задачи (максимизация прибыли) запишется в виде

f (x1 , x2 ) = 4x1 + 5x2 → max

Перейдем к формулировке ограничений. Структура всех трех ограничений одинакова

РАСХОД РЕСУРСА ≤ ЗАПАС РЕСУРСА

Теперь остается выразить полный расход ресурса через выбранные неизвестные x1 и x2 . Так, расход ресурса первого вида на выпуск всех табуреток составит 4x1 единиц, а на выпуск всех стульев 6x2 соответственно (см. первую строку таблицы). В сумме это даст полный расход ресурса первого вида и ограничение примет вид линейного неравенства

4x1 + 6x2 ≤ 24

Аналогично запишутся ограничения по второму и третьему видам ресурсов 3x1 + 2x2 ≤ 12

x1 + x2 ≤ 8

Объединяя их в систему получим

4x1 + 6x2 ≤ 24

3x1 + 2x2 ≤ 12

x1 + x2 ≤ 8

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

x1 ≥ 0, x2 ≥ 0

Окончательно выпишем математическую модель задачи в форме ЗЛП. f (x1, x2 ) = 4x1 + 5x2 → max

4x1 + 6x2 ≤ 24

3x1 + 2x2 ≤ 12

x1 + x2 ≤ 8 x1 ≥ 0, x2 ≥ 0

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

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