8

МИНИСТЕРСТВО ОБРАЗОВАНИЯ и науки УКРАИНЫ

Запорожский институт экономики и

информационных технологий

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

"математическое программирование"

Кривой Рог

2012

Содержание

Введение 3

Тема 1. Задача линейного программирования (ЗЛП) 5

І. Постановка задачи 5

ІІ. Основные определения 5

ІІІ. Геометрическая интерпретация ЗЛП 7

Задачи для самостоятельного решения 12

IV Основные свойства ЗЛП 14

V Симплекс-метод решения ЗЛП 15

Варианты контрольных заданий 25

Тема 2. Двойственная задача линейного программирования 27

2.1. Постановка задачи 27

2.2.Связь между решениями прямой и двойственной задач 29

2.3.Контрольные задания 31

Тема 3. Двойственный симплекс-метод 35

ТЕМА 4. Линейное целочисленное программирование 39

4.1. Постановка задачи 39

4.2. Геометрическая интерпретация задачи целочисленного программирования 39

4.3. Метод Гомори (метод отсекающих плоскостей, метод отсечения) 41

4.4. Варианты заданий 45

Тема 5. Транспортная задача 48

Таблица 5.5 53

Варианты контрольных заданий 54

Тема 6. Задача о назначениях 57

Список рекомендуемой литературы 63

Введение

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

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

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

«Математическое программирование» представляет собой математическую дисциплину, занимающуюся изучение экстремальных задач и разработкой методов их решения.

В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции f(x₁, x₂, …, x_n) при условиях.

В качестве примера рассмотрим следующую задачу:

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

Тип оборудования	Затраты времени (станко-часы) на обработку одного изделия вида			Общий фонд рабочего времени оборудования (ч)
	А	В	С
Фрезерное	2	4	5	120
Токарное	1	8	6	280
Сварочное	7	4	5	240
Шлифовальное	4	6	7	360
Прибыль (д.е.)	10	14	12

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

Составим математическую модель задачи: обозначим через x₁ количество единиц изделий вида А,x₂ – количество единиц изделий вида В,x₃ – количество единиц вида С. Тогда для производства такого количества изделий потребуется затратить:

2x₁+4x₂+5x₃станко-часов фрезерного оборудования,

x₁+8x₂+6x₃ – токарного,

7x₁+4x₂+5x₃ – сварочного,

4x₁+6x₂+7x₃– шлифовального.

При этом прибыль будет составлять 10x₁+14x₂+12x₃д.е. Учитывая ограниченность фонда рабочего времени оборудования и, что количество изготавливаемых изделий не может быть отрицательным, придем к следующей математической задаче (математической модели исходной задачи):

Определить x₁, x₂, x₃, чтобы функцияF=10x₁+14x₂+12x₃

достигла максимального значения при условиях