Сборник задач по линейному программированию (стр. 1 )

  МИНОБРНАУКИ РОССИИ

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Южно-российский государственный университет экономики и сервиса»

(ФГБОУ ВПО «ЮРГУЭС»)

Кавминводский институт сервиса (филиал)

  (КМВИС ФГБОУ ВПО «ЮРГУЭС»)

Сборник задач по линейному
программированию

Часть 1

Учебно-методическое  пособие по высшей математике

Пятигорск

2011г.

УДК 51

ББК 22.1

П 77

Кафедра «Информационные системы технологии и связь»

Составитель:

к. т.н., доцент

Рецензент:

к. б.н., доцент 

 

       Сборник задач по линейному программированию. Часть 1. Учебно-методическое пособие по высшей математике. -  Пятигрск: КМВИС, 2011г. - 35с.

       

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

       Часть 1 включает задачи на нахождение решения систем линейных уравнений методом Жордана-Гаусса, построение линейных математических моделей и решение соответствующих задач графическим и симплексным методами.

Пособие печатается по решению Методического совета КМВИС для внутривузовского пользования (протокол № 2  от 01.01.2001 г.)

© КМВИС ФГБОУ ВПО «ЮРГУЭС»

©

Содержание:

Получение неотрицательных базисных решений  системы линейных уравнений (СЛУ)методом Жордана-Гаусса.  Построение математических моделей для задач линейного программирования. Графический метод решения системы неравенств Графический метод решения задач линейного
программирования. Симплексный метод решения задач линейного
программирования.

Получение неотрицательных базисных решений системы линейных уравнений (СЛУ) методом Жордана-Гаусса

Среди методов решения СЛУ (метод Крамера, матричный метод, метод Гаусса) наиболее распространен метод Гаусса – метод последовательного исключения переменных. Модифицированный метод Гаусса называется методом Жордана-Гаусса или методом полного исключения переменных.        

Рассмотрим систему линейных уравнений с - неизвестными.

               

       Нашу СЛУ удобно записать в виде следующей таблицы – матрицы:

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

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

       При преобразованиях возможны три случая:

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

Допустим, исходная система состояла из пяти уравнений с пятью неизвестными, т. е. исходная матрица имела вид:

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

       Заметим, что конкретный вид матрицы может получиться и не такой, важно, что от пяти уравнений (строчек) осталось три.

Если все уравнения сохраняются, то процедура Жордана-Гаусса приводит к треугольной матрице СЛУ. В нашем случае:

       Ранг полученной системы равен 5, решение системы единственное и равно:

  или

       Вид треугольной единичной матрицы может быть не такой, как (5), например:

       Это тоже треугольная матрица.

       В этом случае решение получается в виде:

или

       Если ранг системы равен , т. е. окончательное число уравнений, меньше числа переменных , то матрица СЛУ имеет трапецеидальную форму и переменных можно выразить через остальные переменных. Допустим, мы получили матрицу (4). В этом случае =3, =5.

       Тогда можно найти:

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