Конспект лекций по курсу «Математическое программирование»

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

 

ОДЕССКАЯ НАЦИОНАЛЬНАЯ АКАДЕМИЯ ПИЩЕВЫХ ТЕХНОЛОГИЙ

 

 

 

 

 

 

 

 

 

 

Кафедра КС и  УБП

 

 

 

 

КОНСПЕКТ ЛЕКЦИЙ

 

ПО КУРСУ  «МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ»

 

для студентов  профессиональных направлений

6.030509, 6.030504, 6.030601дневной и заочной форм обучения

 

 

 

 

 

 

 

 

 

 

Утверждено

советами специальностей

1. 7.030509, 7.030504 протоколом №  
2. 7.030601 протоколом №

 

 

 

 

 

 

Одесса ОНАПТ 2007

 

     Конспект  лекций  по курсу "Математическое программирование" для студентов профессионального направления 6.030509 (504, 601) дневной и заочной форм обучения  / Составители: В.Г.Визинг, Н.А. Макоед -Одесса: ОНАПТ, 2007.- 60 с.

 

 

 

 

 

 

 

 

 

Составители :  В.Г. Визинг, канд. ф.-м. наук, доцент,

                          Н.А. Макоед, канд. пед. наук, доцент.

                         

                        

                      

 

           

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ответственный за выпуск

заведующий  кафедрой КС и УБП канд. ф-м. наук, доцент  Волков В.Э.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

  

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

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

Нами будет  рассмотрен только один класс задач, называемых оптимизационными. Термин "оптимум" происходит от латинского слова optimus – наилучший и используется для обозначения решения, наилучшего с какой-либо фиксированной точки зрения. Термин "оптимальное решение" следует понимать не как абсолютно лучшее, а лучшее в каком-то смысле, то есть по какому-то критерию. Например, при выборе вариантов переезда из одного города в другой можно воспользоваться самолетом или поездом. Легко показать, что каждое решение является оптимальным по соответствующему критерию. Так, если цель – затратить на проезд как можно меньше времени, то из данных вариантов наилучшим, безусловно, является первый. Если же цель – минимум денежных затрат, оптимальным окажется второй вариант.

Понятие оптимальности  и критерия связаны между собой. Применение термина "оптимальный" корректно лишь при указании критерия.

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

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

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

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

Основополагающая  работа по математическому программированию была написана в 1939 году советским математиком Л.В. Канторовичем. Появление ЭВМ дало мощный толчок развитию математического программирования. В настоящее время эта область находится на стадии развития.

 

1.РЕШЕНИЕ  СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ГАУССА – ЖОРДАНА

1.1. Основные  понятия

Система m линейных уравнений с n неизвестными имеет следующий вид:

 

 

Здесь х_j ( j=1, n ) – переменные ( или неизвестные) системы, а_ij ( i =1,m; j = 1,n ) – коэффициенты при переменных,   в_i ( i =1,m  ) – свободные члены.

Решением системы ( І.І)  называется всякий набор значений   переменных х₁, х₂, …, х_n, при котором все уравнения превращаются в тождества. Система называется совместной, если она имеет хотя бы одно решение, и несовместной – в противном случае.

Например, система

совместна, так  как она имеет, в частности, такое  решение:

х₁ = 1;  х₂ = 2;  х₃ = 0 . Система же   

несовместна.

Две системы  линейных уравнений называются равносильными, если каждое решение одной из них является решением другой, и наоборот. Если какое-либо уравнение системы умножить на постоянный множитель λ ≠ 0 , то получится система уравнений, равносильная исходной. Аналогично, если к какому-либо уравнению системы прибавить другое уравнение системы, то получится система, равносильная исходной.

Наконец если, в системе есть уравнение вида

0∙х₁ + 0∙х₂ + ... + 0∙ х_n = 0, то такое уравнение можно убрать, получив систему, равносильную исходной.

 

1.2. Приведение  системы линейных уравнений к  жордановой форме

 

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

Определение. Жордановой формой системы (I.I) называется система линейных уравнений, обладающая следующими свойствами:

а) она равносильна системе (I.I)

б) в каждом уравнении  жордановой формы есть такая переменная, которая входит в это уравнение  с коэффициентом 1,  а в остальные  уравнения - с коэффициентом 0.

Так, если системе (I.I) равносильна следующая система линейных уравнений:

 

                                     (1.2)

то (І.2) есть жорданова  форма для (I.I). При этом переменные х_1, х₂,... ,х_к называются базисными, остальные переменные х_к+1,..., х_n   называются свободными. Жорданова форма всегда является совместной системой линейных уравнений. Действительно, система (І.2) имеет следующее решение:

                 (І.3)

Так как система (І.2) равносильна системе ( І.І ) , то (І.3) является решением системы (І.І).

Таким образом, если для системы линейных уравнений  ( І.І ) существует жорданова форма, то ( І.І ) – совместная система. Несовместная система  жордановой формы не имеет.

Покажем, что любую совместную систему можно привести к жордановой форме. Это достигается методом Гаусса-Жордана, который состоит в следующем.

Рассмотрим  первое уравнение системы (І.І). Выберем в нем переменную, коэффициент при которой отличен от нуля. Предположим, что а₁₁ ≠ 0. Поделим уравнение на а₁₁.

 Получим  уравнение

                                                х₁+ а₁₂х₂ + … + а_1nх_n = в₁                        (І.4)

 

Будем переменную х₁ делать базисной в жордановой форме. Для этого ее нужно исключить из остальных уравнений системы. Чтобы исключить х₁ из второго уравнения, умножим уравнение (І.4) на  -а₂₁ и сложим со вторым уравнением. Затем исключим х₁ из третьего уравнения, для чего уравнение (І.4) умножим на –а₃₁ и сложим с третьим уравнением. Аналогично переменная х₁ исключается из остальных уравнений. Таким образом, взяв в качестве "ведущего" первое уравнение и проведя серию "жордановых исключений", мы получим равносильную (I.I) систему уравнений, в которой x₁ входит в первое уравнение с коэффициентом 1 , а в остальные уравнения - с коэффициентом 0.

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

Если на некотором  шаге возникнет уравнение вида

           0∙х₁ + 0∙х₂ + ... + 0∙ х_n =  0                                                 (І.5)

то удаляем  его из системы. Если же возникнет уравнение вида

0∙х₁ + 0∙х₂ + ... + 0∙ х_n = b ≠ 0, то это свидетельствует о несовместности исходной системы ( І.І), а несовместная система к жордановой форме не приводится.

Таким образом, метод Гаусса-Жордана совместную систему линейных уравнений приводит к жордановой форме, а в случае несовместности системы обнаруживает несовместность.

Ясно, что в жордановой форме число уравнений не может быть больше числа уравнений в исходной системе. Так, если система (1.2) является жордановой формой для системы (I.I), то , причем строгое неравенство имеет место тогда, когда на некоторых шагах жордановой процедуры удалялись уравнения вида (1.5).

Очевидно, одна и та же система  может иметь много различных  жордановых форм.

 

Пример. Привести к жордановой форме

Выберем в качестве ведущего первое уравнение, а в качестве базисной переменной - переменную х_1. Поделим первое уравнение на (-1) (коэффициент при х₁), получим:

Умножим это уравнение на (+5) и  прибавим ко второму уравнению, затем  умножим его на (-3) и прибавим к  третьему уравнению.

Получим систему:

 

Теперь сделаем  ведущим второе уравнение, а базисной переменной - переменную . Поделив второе уравнение на (-8) и исключив из первого и третьего уравнений, получим систему:

Наконец, в третьем  уравнении выбираем в качестве базисной переменную . Поделим это уравнение на (-1) и исключим из остальных уравнений. Получим жорданову форму:

Переменные  являются базисными, переменная - свободной.

 

1.3. Понятие  общего, частного и базисного решений.

.

Пусть система (І.І) представлена в жордановой форме (1.2). Выразим базисные переменные через  свободные.

 

                                     (1.6)

(1.6) называется общим решением системы (I.I).

Если свободным переменным придать любые числовые значения и вычислить значения базисных переменных из системы (1.6), то получится решение исходной системы, называемое частным. Частное решение называется базисным, если свободные переменные принимают нулевые значения. Решение (1.3) является базисным.

 В примере  общее решение таково:

 

 

а базисное решение . Если в жордановой форме число уравнений равно числу переменных n, т.е. жорданова форма имеет вид:

то система  имеет единственное решение; оно  является и общим, и частным, и  базисным. Если же k‹n , т.е. жорданова  форма содержит свободные переменные, то система имеет бесконечно много  решений.

 

2. ОБЩИЕ  СВОЙСТВА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

2.І. Пример задачи линейного программирования -

задача  об использовании оборудования.

 

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

Изделия станки	А	В	Резервы времени (в часах)
I	Затраты времени на пр-во ед. изделия (в часах)
	2	3	30
II	4	2	40
III	3	4	60
Прибыль от реализации ед. изделия	6	7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Это пример оптимизационной экономической задачи. Решение таких задач включает в себя следующие этапы:

построение  экономико-математической модели;

решение полученной математической задачи каким-либо математическим методом;