ЧАСТЬ 1. Федеральное агентство по образованию

Федеральное агентство по образованию

Пермский институт (филиал) ГОУ ВПО

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

Кафедра Высшей и прикладной

математики

УТВЕРЖДЕНО:

Методическим Советом

ПИ (ф) ГОУ ВПО «РГТЭУ»

Протокол №________

от «___» _________ 200 г.

ПРИКЛАДНАЯ МАТЕМАТИКА

ЧАСТЬ 1

МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАНИЯ ДЛЯ КОНТРОЛЬНОЙ РАБОТЫ №1 ДЛЯ СТУДЕНТОВ ЗАОЧНОЙ ФОРМЫ ОБУЧЕНИЯ ВСЕХ СПЕЦИАЛЬНОСТЕЙ И НАПРАВЛЕНИЙ

Пермь 2006

Методические указания составлены в соответствии с государственными образовательными стандартами второго поколения и программой РГТЭУ.

Р А С С М О Т Р Е Н О:

на заседании кафедры:

Высшей и прикладной математики

от «» 200 г. Протокол №

Зав. каф., к.т.н., профессор В.В. Козлов

Составители: доцент Козлов В.В. доцент Овчинникова В.И.

I. Общие методические указания

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

Курс изучается по программе " Прикладная математика", утвержденной в 1992 г.

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

II. Литература

1. Кузнецов Ю.П. Математическое программирование. - М.: Высшая школа, 1980.

2. Вентцель Е.С. Исследование операций. М.: Наука, 1980.

3. Спирин А.А., Фомин Г.П. Экономико-математические методы и модели в торговле М.: Экономика, 1988.

4. Дж. Хедли Нелинейное и динамическое программирование, М.: Мир, 1967.

5. Фомин Г.П., Шарипов ГА. Экономико-математическое моделирование явлений и процессов в торговле: Учеб. пособие /Заоч. ин-т сов. торговли, М., 1982

6. Фомин Г.П., Григорьев С.Б. Модели оптимального планирования в общественном питании: Учеб. Пособие/ Моск. коммерческий ин-тМ., 1990.

7.. Фомин Г.П., Системы и модели массового обслуживания в общественном питании: Учеб. пособие/Заочн. ин-т сов. Торговли М., 1987.

8. Фомин Г.П., Модели выбора решений в коммерческих операциях М.: изд-во МГУК, 1996, 29с.

9. Смирнова В.В. Методические указания и задания по дисциплине «Математическое программирование», М., МУПК, 1998..

10. Смирнова В.В. Методические указания и задания по дисциплине " Математическое программирование", М:, МУПК.1998.

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

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

III. ЗАДАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ №1

Предлагаются к самостоятельному изучению и последующему решению задач по следующим темам:

1. Решение задачи линейного программирования на основе ее геометрической интерпретации (графический метод).

2. Моделирование экономических процессов коммерческого предприятия и решение моделей симплексным методом.

3. Двойственная задача к задаче планирования работы коммер­ческого предприятия.

4. Транспортная задача в матричной постановке. Построение первого опорного плана. Нахождение оптимального плана транспортной задачи методом потенциалов.

5. Номера задач определяются в соответствии с таблицей 1 по первым буквам фамилии, имени, отчества.

Таблица 1

ЗАДАЧИ № 1 - 25

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

1. 5.

2. 6.

3. 7.

4. 8.

9. 10.

11. 12.

13. 14.

16. 17.

18. 19.

20. 21.

22. 23.

24. 25.

Задачи № 26 - 50

Для реализации трех групп товаров коммерческое предпри­ятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве единиц, ресурса второго вида в количестве единиц, ресурса третьего вида в количестве единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарообо­рота расходуется соответственно ресурса первого вида в количест­ве единиц, ресурсов второго вида в количестве единиц, ресурсов третьего вида в количестве единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота состав­ляет соответственно (тыс. руб.).

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

26. а₁₁=3, а₁₂=6, а₁₃=4, a₂₁=2, а₂₂=1, а₂₃=2, а₃₁=2, а₃₂=3, а₃₃=1, b₁=180, Ь₂=50, Ь₃=40, C₁=6, С₂=5, С₃=5.

27. а₁₁=1, а₁₂=2, а₁₃=1, а₂₁=2, а₂₂=1, а₂₃=3, а₃₁=4, а₃₂=2, а₃₃=1, b₁=420, Ь₂=600, Ь₃=900, c₁₌₃, С₂=3, С₃=4.

28. a₁₁=16, а₁₂=18, а₁₃=9, a₂₁=7, a₂₂=7, a₂₃=2, a₃₁=9, a₃₂=2, a₃₃=3, Ь₁=520, Ь₂=140, Ь₃=810, c₁=8, с₂=6, С₃=4.

29. а₁₁=4, а₁₂=8, а₁₃=2, а₂₁=3, а₂₂=8, а₂₃=4, а₃₁=12, а₃₂=4, а₃₃=6, b₁=116, Ь₂=240, Ь₃=432, C₁=8, с₂=6, С₃=6.

30. а₁₁=8, a₁₂=10, a₁₃=20, a₂₁=4, a₂₂=13, a₂₃=8, a₃₁=2, a₃₂=18, a₃₃=12, b₁=800, Ь₂=520, Ь₃=940, c₁=3, c₂=6, С₃=7.

31. а₁₁=3, а₁₂=3, а₁₃=9, a₂₁=10, a₂₂=9, a₂₃=15, a₃₁=5, a₃₂=5, a₃₃=1, b₁=810, Ь₂=900, Ь₃=250, C₁=7, c₂=7, C₃=6.

32. а₁₁=17, а₁₂=5, а₁₃=5, а₂₁=8, а₂₂=6, а₂₃=6, а₃₁=4, а₃₂=2, а₃₃=4, b₁=850, Ь₂=1120, Ь₃=1060, d=8, С₂=7, с₃=4.

33. а₁₁=2, a₁₂=1, a₁₃⁼6, а₂₁⁼3, а₂₂⁼3, а₂₃=9, a₃₁=2, a₃₂=1, а_зэ=2, Ь₁=240, Ь₂=540, Ь₃=120, c₁=14, С₂=6, С₃=22.

34. а₁₁=2, а₁₂=3, а₁₃=6, а₂₁=6, а₂₂=8, а₂₃=2, a₃₁=3, a₃₂=43, а₃₃=2, Ь₁=450, Ь₂=400, Ь₃=350, с₁=З, С₂=5, С₃=4.

35. a₁₁=1, a₁₂₌1, a₁₃=1, a₂₁=2, а₂₂=1, а₂₃⁼3, а₃₁=3, а_з2=2, а_зз=3, b₁=160, Ь₂=200, Ь₃=240, c₁₌4, С₂=3, С₃=5.

36. а₁₁=2, a₁₂=3, а₁₃=6, а₂₁=4, а₂₂=2, а₂₃=4, а₃₁=4, а₃₂=6, а₃₃=8, b₁=240, Ь₂=200, Ь₃=160, C₁=4, С₂=5, С₃=4.

37. а₁₁=9, а₁₂=9, a₁₃=2, a₂₁=4, a₂₂=3, a₂₃=2, a₃₁=1, a₃₂=2, a₃₃=4, b₁=180, Ь₂=120, Ь₃=220, c₁=7, c₂=8, C₃=6.

38. а₁₁=18, а₁₂=9, а₁₃=6, а₂₁=4, а₂₂=2, а₂₃=4, a₃₁=3, a₃₂=3, а₃₃=1, b₁=540, Ь₂=340, Ь₃=120, с₁=3, С₂=4, с₃=3.

39. а₁₁=3, а₁₂=2, a₁₃=1, a₂₁=4, а₂₂=2, а₂₃=4, а₃₁=3, а₃₂=3, а₃₃=4, b₁=70, b_z=80, Ь₃=120, c₁=7, с₂=8, с₃=7.

40. а₁₁=4, а₁₂=2, a₁₃=5, a₂₁=2, а₂₂=8, а₂₃=4, a₃₁=11, a₃₂=4, a₃₃=2, Ь₁=250, Ь₂=160, Ь₃=440, c₁=7, С₂=6, С₃=8.

41. а₁₁=7, a₁₂=4, a₁₃=5, a₂₁=6, a₂₂=2, a₂₃=4, a₃₁=7, a₃₂=14, а₃₃=7, Ь₁=280, Ь₂=160, Ь₃=420, С₁₌18, С₂=16, С₃=15.

42. а₁₁=5, а₁₂=8, а₁₃=4, а₂₁=5, а₂₂=5, а₂₃=6, a₃₁=10, a₃₂=2, а_зз=5, b₁=400, Ь₂=300, Ь₃=200, c₁=4, C₂=3, С₃=2.

43. a₁₁=5, а₁₂=5, a₁₃=2, а₂₁=4, а₂₂=6, а₂₃=8, a₃₁=5, а₃₂=6, а₃₃=2, b₁=250, Ь₂=500, Ь₃=300, c₁=10, с₂=, с₃=9.

44. а₁₁=7, a₁₂=7, а₁₃=4, a₂₁=2, a₂₂=4, a₂₃=8, a₃₁=16, а_Э2=12, а₃₃=10, Ь₁=280, Ь₂=160, Ь₃=530, с₁=10, с₂=10, c₃=12.

45. а₁₁=7, а₁₂=10, а₁₃=11, а₂₁=8, а₂₂=б, а₂₃=4, a₃₁=12, a₃₂=4, а₃₃=16, b₁=740, Ь₂=820, Ь₃=480, c₁=10, с₂=8, с₃=7.

46. а₁₁=2, а₁₂=2, а₁₃=4, а₂₁=1, а₂₂=5, а₂₃=1, a₃₁=6, a₃₂=2, а₃₃=1, Ь₁=540, Ь₂=360, Ь₃=180, c₁=3, с₂=2, с₃=1.

47. а₁₁=10, а₁₂=6, а₁₃=8, a₂₁=6, а₂₂=6, а₂₃=4, а₃₁=10, а₃₂=12, а₃₃=6, Ь₁=840, Ь₂=296, Ь₃=620, c₁=6, с₂=5, с₃=5.

48. a₁₁=10, а₁₂=5, а₁₃=10, а₂₁=26, а₂₂=13, а₂₃=4, а₃₁=3, а₃₂=4, а₃₃=2, Ь₁=670, Ь₂=520, Ь₃=480, c₁=8, с₂=6, с₃=6.

49. а₁₁=9, а₁₂=9, а₁₃=3, а₂₁=3, а₂₂=6, а₂₃=9, a₃₁=7, a₃₂=4, а₃₃=12, Ь₁₌801, Ь₂=453, Ь₃=280, c₁=3, с₂=2, с₃=2.

50. а₁₁=10, а₁₂=5, а₁₃-5, а₂₁=7, а₂₂=2, а₂₃=4, а₃₁=7, а₃₂=3, а₃₃=3, Ь, =290, Ь₂=140, Ь₃=210, c₁=10, с₂=9, с₃=5.

Задачи №51-75

Используя вариант предыдущего контрольного задания №25-50, необходимо:

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

- установить сопряженные пары переменных прямой и двойственной задач;

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

Задачи №76-100

Поставщики товара - оптовые коммерческие предприятия имеют запасы товаров соответственно в количестве ед. и розничные торговые предприятия - подали заявки на закупку товаров в объемах соответственно: _. Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы

( = ; j = i, n)

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

76.

C =

77.

78.

79.

80.

81.

82.

83.

84.

85.

86.

87.

88.

89.

90.

91.

92.

93.

94.

95.

96.

97.

98.

99.

100.

ПРАВИЛА ОФОРМЛЕНИЯ РАБОТЫ

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

В начале работы или на титульном листе должны быть указаны номера задач, выполненных в контрольном задании.

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

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

Допущенную к защите контрольную работу вместе с рецензией на нее студент должен представить на собеседование.

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

IV.МЕТОДИЧЕСКИЕ УКАЗАНИЯ К РЕШЕНИЮ ЗАДАЧ

1. Графический метод решения задач линейного программирования

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

При условиях-ограничениях

где -заданные постоянные величины и .

Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 1 и 3, где и .

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 2 и 4, где и .

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

План = , при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным.

В случае, когда требуется найти минимум функции можно перейти к нахождению максимума функции , так как min .

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

Допустим ограничения задачи отображают наличие производственных ресурсов, тогда числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объе­му неиспользуемого соответствующего ресурса.

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

Так как векторы являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать m.

Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае - план вырожденный.

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

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

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

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

Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной.

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

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

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

при условиях

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

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

Решение задачи линейного программирования графическим методом включает следующие этапы.

1. На плоскости строят прямые, уравнения которые получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Строят многоугольник решений.

4. Строят вектор , направление которого указывает на возрастание целевой функции.

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

6. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

Минимальное значение линейной функции цели находится путем передвижения начальной прямой , в направлении,

противоположном вектору .

Пример

Найти максимум и минимум линейной функции:

при условиях:

Решение;

Построим на плоскости многоугольник решений рис.1.

Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

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

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

Многоугольником решений задачи является пятиугольник АВ-СДЕ, координаты точек которого удовлетворяют условию неотрицательности и неравенствам системы ограничений задачи.

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

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

Для нахождения минимального значения целевой функции задачи перемещаем начальную прямую в направлении, противоположном вектору . Начальная прямая займет положение опорной прямой в вершине Е. Целевая функция принимает минимальное

значение в угловой точке Е, где

Найдем координаты угловых точек В, Д и А. Для этого решим следующие системы уравнений:

В результате получим координаты точек В (0; 2, 5), Д (2, 0) и А (0, 1).

Вычислим значения целевой функции во всех угловых точках многоугольника решений АВСДЕ:

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Сформулируйте общую задачу линейного программирования.

2. Дайте определение невырожденного и вырожденного опорного плана, оптимального плана.

3. Какое множество называется выпуклым?

4. Какая точка выпуклого множества называется угловой?

5. Дайте геометрическую интерпретацию задачи линейного программирования.

6. В какой точке многогранника решений целевая функция задачи линейного программирования достигает оптимального значения?

7. Какие задачи линейного программирования можно решить графическим методом?

8. Назовите особые случаи при решении задачи линейного программирования графическим методом.

2. Симплексный метод решения задачи линейного программирования.

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

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

1. Математическую модель задачи запишем следующим образом:

Определить , который удовлетворяет ограничениям вида:

и обеспечивает максимальное значение целевой функции

Алгоритм симплексного метода включает следующие этапы.

2. Составление первого опорного плана.

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

где базисные переменные.

свободные переменные.

Решим эту систему относительно базисных переменных:

а функцию цели перепишем в таком виде:

Полагая, что основные переменные

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

3. Проверка плана на оптимальность.

Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны ( 0), то

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

4. Определение ведущих столбца и строки.

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

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

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

5. Построение нового опорного плана

Переход к новому плану проводится пересчетом симплексной таблицы по методу Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо в базис войдет переменная , соответствующая направляющему столбцу.

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

нового плана находятся по правилу прямоугольника: - ,

где элемент старого плана, разрешающий элемент,

А и В - элементы старого плана, образующие прямоугольник с элементами и .

6. Полученный новый опорный план опять проверяется на оптимальность в соответствии с этапом 3 алгоритма.

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

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

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

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

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

ПРИМЕР РЕШЕНИЯ ЗАДАЧИ СИМПЛЕКСНЫМ ДЕТОДОМ.

Торговое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В и С. Плановые нормативы затрат ресурсов на тыс. руб. товарооборота, прибыль от продажи товаров на тыс. руб. товарооборота, а также объем ресурсов заданы в таблице 2.

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

Таблица 2

Виды материально-денежных ресурсов	Норма затрат материально-денежных ресурсов на ед. товарооборота, тыс. руб.	Объём ресурсов
А _ группа _	В группа	С группа
Рабочее время продавцов, чел./ч	0, 1	0, 2	0, 4
Площадь торговых залов, м2	0, 05	0, 02	0, 02
Площадь складских помещений, м2
Прибыль, т.руб.				max

1.Запишем математическую модель задачи.

Определить , который удовлетворяет условиям

и обеспечивают максимальное значение целевой функции

Для построения первого опорного плана систему неравенств, приведем к системе уравнений.

В матрице этой системы уравнений имеет:

Векторы - линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля:

Соответствующие этим векторам переменные будут базисными.

Решим систему уравнений относительно базисных переменных.

Функцию цели запишем в виде:

2.Полагая, что свободные переменные =0, =0, =0, получим первый опорный план

=(0, 0, 01100, 120, 8000), F = 0, в котором базисные переменные =1100, =120, =8000,

следовательно товары не продаются и прибыль равна нулю, а ресурсы не используются.

Заносим первый опорный план 1 в симплексную таблицу 3.

План	Базисные переменные	Ресурсы плана	Значения коэффициентов при переменных
I план		1100 120 8000	0, 1 0, 05 3	0, 2 0, 02 1	0, 4 0, 02 2		0 1 0
Инд. Строка			-3	-5	-4
II план		5500 10 2500	0, 5 0, 04 2, 5		-0, 02 0	-0, 1 -5
Инд. Строка			-0, 5
III план		5375 250 1 875			2, 25 -0, 5 1, 25	6, 25 -2, 5 1, 25	-12, 5 25 -62, 5	0 0
Инд. строка					5, 75	23, 75	12, 5

Симплексная таблица 3

Первый опорный план 1 не оптимальный, так как в индексной строке находятся отрицательные коэффициенты - -3, -5, -4.

За ведущий столбец выберем столбец, соответствующий переменной , так как сравнивая по модулю имеем:

|- 5| > |- 3I, |- 4I} Рассчитываем значения 9 по строкам, как частное от деления и выбираем наименьшее: