Линейное программирование



страница1/10
Дата02.01.2013
Размер0.83 Mb.
ТипМетодические указания
  1   2   3   4   5   6   7   8   9   10


Министерство общего и профессионального образования РФ

Алтайский государственный технический университет

им. И.И. Ползунова

Бийский технологический институт

Л.И. Царегородцев, Ю.Н. Каргин, В.В. Царегородцева


ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Методические указания и контрольные задания для

студентов-заочников специальности 060800 - экономика и управление на предприятиях машиностроения; 071900 - информационные системы в экономике.

Бийск, 1999

УДК 519
Царегородцев Л.И., Каргин Ю.Н., Царегородцева В.В. Линейное программирование: Методические указания и контрольные задания для студентов - заочников.
Алт. гос. ун-т им. И.И.Ползунова, БТИ. -Бийск.

Изд-во Алт. гос. ун-та, 1999.-54с.

Настоящее пособие предназначено для студентов Бийского технологического института заочной формы обучения специальности 060800–экономика и управление на предприятиях машиностроения.

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

на заседании кафедры математики

Протокол №14 от 6.12.1998 г.
Рецензент: Фарукшин В.Х. к.ф.-м. н., доцент БИГПИ

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ И ОФОРМЛЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

Раздел "Линейное программирование" разбит на шесть тем. Перед выполнением контрольного задания студент должен изучить соответствующую тему по пособиям, рекомендуемым в "Методических указаниях". Пособия обозначаются номерами в квадратных скобках; например, [3] означает ссылку на учебник А.В. Кузнецова, В.А. Саковича и Н. И. Холода. В "Методических указаниях" приводится перечень знаний и умений, которыми должен обладать студент, изучивший тему. В них даются также некоторые начальные теоретические сведения и приводятся решения типовых примеров. Если студент испытывает затруднения в освоении теоретического или практического материала, то он может получить консультацию на кафедре математики БТИ. График консультаций можно узнать в деканате заочного отделения.

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

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

В прорецензированной работе студент должен исправить отмеченные рецензентом ошибки и учесть его рекомендации, сделав "Работу над ошибками".
Если работа не зачтена, то после исправления ошибок ее отправляют на повторную рецензию. Зачтенная контрольная работа предъявляется студентом при сдаче зачета или экзамена.

На зачете (экзамене) выясняется степень усвоения студентом теоретических вопросов программы и умения применять полученные знания к решению практических задач.

ЛИТЕРАТУРА

  1. Беклемишев Д.В. Курс аналитической геометрии и линейной

алгебры.-М.: Наука, 1980

  1. Высшая математика для экономистов /Под ред. проф.

Н.Ш.Кремера.- М.: Банки и биржи, 1997.

  1. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика:

математическое программирование.-Мн.: Высшая школа, 1994.

  1. Акулич И.Л. Математическое программирование в примерах и

задачах–М.: Высшая школа, 1986.

  1. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в

упражнениях и задачах. В 2-х ч.Ч.1–М.: Высшая школа, 1986.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КОНТРОЛЬНОЙ РАБОТЕ

1 Математический аппарат линейного программирования

Литература: [1], гл. V, § 1-5; [2], гл. II

Студент должен

знать:

  • определение n-мерного арифметического пространства и линейных операций над векторами из ;

  • определение линейно независимой системы векторов и базиса в;

  • определение скалярного произведения векторов в и понятие ортонормированной системы векторов в;

  • понятия определителя, матрицы, базисного минора и ранга матрицы, определение элементарных преобразований матрицы, теорему о базисном миноре;

  • понятие системы линейных уравнений, виды систем, задачи теории систем линейных уравнений;

  • метод Гаусса решения систем линейных уравнений;

  • определения общего, частного, базисного и опорного решений системы линейных уравнений;

уметь:

  • выполнять линейные операции над векторами из и вычислять скалярное произведение векторов из ;

  • выполнять элементарные преобразования матрицы и находить ее ранг;

  • находить максимальную линейно независимую подсистему в заданной системе векторов из ;

  • находить координаты произвольного вектора из в заданном базисе;

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

Основные теоретические сведения

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

. (1.1)

Элементы множества называют векторами. Вектор может быть записан как в виде строки (1.1), так и в виде столбца:

. (1.2)

Числа , называются компонентами вектора.

Пусть даны два вектора и

. Векторы и называют равными в том и только в том случае, когда

Суммой векторов и называется вектор , компоненты которого равны сумме соответствующих компонент слагаемых векторов, т.е.

. (1.3)

Произведением вектора на вещественное число называется вектор , компоненты которого равны произведению на соответствующие компоненты вектора , т.е.

. (1.4)

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

. (1.5)

Множество всех векторов вида (1.1)-(1.2), в котором определены операции сложения векторов (1.3), умножения вектора на число (1.4) (такие операции называются линейными) и операция скалярного произведения (1.5) называется n-мерным вещественным арифметическим пространством.

Определение 1.2. Система векторов из называется линейно зависимой, если существуют такие вещественные числа , не все равные нулю, что имеет место равенство:

. (1.6)

Если же равенство (1.6) возможно в единственном случае, когда , система векторов называется линейно независимой.

Из определения следует, что система, содержащая более одного вектора, линейно зависима в том и только в том случае, когда среди векторов системы имеется вектор, который линейно выражается через остальные.

Определение 1.3. Система векторов из называется базисом пространства , если:

1) эти вектора линейно независимы;

2) любой вектор из является линейной комбинацией векторов данной системы.

Примером базиса в может служить ортонормированная система векторов

. (1.7)

Векторы (1.7) обладают следующим свойством:

. (1.8)

Отметим, что компоненты вектора являются его координатами относительно ортонормированного базиса (1.7).

Решение задач линейного программирования и их анализ напрямую связаны с решением систем линейных уравнений методом исключения неизвестных (метод Гаусса).

Определение 1.4. Системой m линейных уравнений с n неизвестными называется система вида

, (1.9)

.

Систему уравнений (1.9) можно записать в матричном виде:

, (1.10)

где - основная матрица системы (1.9), -вектор-столбец неизвестных, -вектор-столбец свободных членов:

, , . (1.11)

Систему (1.9) можно представить также в векторном виде:

, (1.12)

где - вектор-столбец, составленный из коэффициентов при j-ой неизвестной .

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

Система линейных уравнений (1.9) называется совместной, если она имеет хотя бы одно решение, и несовместной, если она не имеет ни одного решения.

Если совместная система имеет только одно решение, она называется определенной. Если же система имеет более одного решения, она называется неопределенной.

Решить систему линейных уравнений - это значит:

1) выяснить, совместна система или нет;

2) если система совместна, то найти все ее решения.

На практике решение системы линейных уравнений удобно проводить, используя метод Гаусса. Метод Гаусса, или метод последовательного исключения неизвестных, заключается в том, что с помощью элементарных преобразований система уравнений (1.9) приводится к равносильной системе ступенчатого (или треугольного) вида. Ступенчатый вид системы позволяет без труда найти базисные миноры в основной и расширенной матрице системы и тем самым решить вопрос о ее совместности. Выбор базисного минора в основной матрице совместной системы позволяет также разделить все неизвестные на два типа - свободные и базисные. Число базисных неизвестных равно рангу системы r, следовательно, число свободных неизвестных равно . Выбор базисных переменных можно осуществить, вообще говоря, многими способами. Однако, число таких способов конечно и не превосходит числа сочетаний .

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

Рассмотрим пример. Решить систему уравнений:

. (1.13)

Составим расширенную матрицу системы (вертикальной чертой отделен столбец свободных членов) и с помощью элементарных преобразований приведем ее к ступенчатому виду.

. (1.14)

Шаг 1. Вычитая первую строку матрицы из третьей и четвертой строк, обратим в нуль все элементы первого столбца кроме первого. Мы получим

. (1.15)

Шаг 2. Умножая элементы второй строки на числа (-2), 5 и 3 и вычитая затем вторую строку соответственно из первой, третьей и четвертой, обратим в нуль все элементы второго столбца кроме второго. Результат имеет вид:

. (1.16)

Шаг 3. Разделим теперь элементы третьей строки на 2, вычтем результат соответственно из первой и четвертой строки и прибавим его ко второй строке. В итоге все элементы третьего столбца, кроме , обратятся в нуль. Четвертая строка будет целиком состоять из нулей и ее можно отбросить. Мы получим

. (1.17)

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

Матрице (1.17) соответствует система линейных уравнений вида:

. (1.18)

Эта система равносильна исходной системе (1.13). В соответствии с выбором базисного минора переменные и являются базисными, а переменные -свободными. Придавая свободным переменным произвольные значения , , найдем общее решение системы (1.13) в виде:

, (1.19)

, .

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

Найдем базисное решение системы (1.13). Полагая в (1.19) свободные переменные , мы получим базисное решение в виде

=(-8, 3, 6, 0, 0), (1.20)

выраженное через базисные векторы .

Найдем теперь другое базисное решение системы (1.13) или равносильной системы (1.18). С этой целью выберем в матрице (1.17) другой базисный минор. В качестве нового базисного минора можно взять любой минор третьего порядка не равный нулю, например, минор, расположенный в первом, втором и четвертом столбцах. Тогда в системе (1.18) базисными переменными будут , и , а свободными - и . Приравняв новые свободные переменные к нулю,

, мы получим систему (1.18) в виде

, (1.21)

откуда , , . Таким образом, новое базисное решение имеет вид

=(-8, 0, 0,-3, 0). (1.22)

Оно выражено через базисные векторы .

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

В качестве самостоятельного упражнения найдите базисное решение, выраженное через векторы , и выясните, является ли оно опорным.
  1   2   3   4   5   6   7   8   9   10

Похожие:

Линейное программирование iconЛинейное программирование
Линейное программирование (ЛП) это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на...
Линейное программирование iconПеречень вопросов для вступительного экзамена в аспирантуру по специальности 05. 13. 18 «Математическое моделирование, численные методы и комплексы программ» Математические основы
Математическое программирование, линейное программирование, выпуклое программирование
Линейное программирование iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Линейное программирование iconМатематическое программирование
В математическом программировании выделяют линейное программирование – когда функции и линейны, квадратичное программирование, когда...
Линейное программирование iconЛинейное программирование задачи математического и линейного программирования
Соответствующие методы, позволяющие решать указанные задачи, объединяются под общим названием «математическое программирование»
Линейное программирование iconПараметрическое линейное программирование
Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых...
Линейное программирование icon«Линейное программирование и симплекс метод»

Линейное программирование iconВопросы экзамена Методы оптимизации Раздел Линейное программирование
Алгоритм симплекс-метода без корректного вида базиса с искусственными переменными
Линейное программирование iconЛинейное программирование и симплекс метод
...
Линейное программирование iconТранспортная задача
Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org