Линейное программирование (Графический метод. Симплексный метод) (стр. 1 )

Министерство образования Российской Федерации

Бузулукский гуманитарно-технологический институт

(филиал) федерального государственного бюджетного

образовательного учреждения

высшего профессионального образования -

«Оренбургский государственный университет»

Кафедра физики, информатики и математики

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

(Графический метод. Симплексный метод)

Методические указания

Рекомендовано к изданию Редакционно-издательским советом БГТИ (филиала) ОГУ в качестве методических указаний по организации самостоятельной работы студентов, обучающихся по программам высшего профессионального образования по специальностям 080105.65 «Финансы и кредит», 080107.65 «Налоги и налогообложение», 080109.65 «Бухгалтерский учет, анализ и аудит»

Бузулук

2011

ББК 22.1

УДК 51

А 95

Рецензент: доцент кафедры физики, информатики и математики, к. п.н, Степунина О. А

Ахматова, Д. Н.

А95	Линейное программирование (Графический метод. Симплексный метод): методические указания / ; Бузулукский гуманитарно-технолог. ин-т (филиал) ОГУ. – Бузулук: БГТИ (филиал) ОГУ, 2011. – 63 с.

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

Методические указания по организации самостоятельной работы студентов предназначено для студентов, обучающихся по программам высшего профессионального образования по специальностям 080105.65 «Финансы и кредит», 080107.65 «Налоги и налогообложение», 080109.65 «Бухгалтерский учет, анализ и аудит» при изучении дисциплины «Математика (экономико-математические методы и модели)»

ББК 22.1

УДК 51

© , 2011

© БГТИ (филиал) ОГУ, 2011

Содержание

Введение. 4

1 Основные понятия математического программирования, основные понятия линейного программирования. 5

1.1 Общая задача математического программирования. Основные разделы математического программирования. 5

1.2 Математические модели экономических задач. 7

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

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

2.1 Свойства основной задачи линейного программирования. 19

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

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

Ответы и решения. 41

Список использованных источников. 47

Введение

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

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

Материал работы содержит теоретическую и практическую часть.

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

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

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

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

1.1 Общая задача математического программирования. Основные разделы математического программирования

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

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

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

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

Общая постановка задачи математического программирования:

вычислить

(1)

при условиях

; (2)

, (3)

где - заданные функции, - действительные числа.

Функция (1) называется целевой функцией или функцией цели; условия (2) – специальными ограничениями задачи математического программирования; условия (3) – общими ограничениями задачи математического программирования.

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

Признаки классификации задач математического программирования:

1)  по типу данных: определенные (детерминированные), случайные;

2)  по характеру изменения переменных: переменные непрерывные, дискретные (целочисленные);

3)  по характеру взаимосвязей между переменными: линейные, нелинейные.

В таблице 1.1 приведем основную классификацию задач математического программирования.

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

Таблица 1.1 – Основная классификация задач математического программирования

Исходные данные	Переменные	Зависимость	Раздел математического программирования
Определенные	Непрерывные	Линейная	Линейное программирование
Целочисленные	Линейная	Целочисленное программирование
Непрерывные/ целочисленные	Нелинейные	Нелинейное программирование
Случайные	Непрерывные	Линейные	Стохастическое программирование

1.2 Математические модели экономических задач

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

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

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

1)  выбор переменных;

2)  изучение информационной базы;

3)  выражение взаимосвязей между переменными, характеризующими объект, в виде уравнений и неравенств;

4)  выбор критерия (от гр. kriterion – мерило, оценка, средство для суждения) оптимальности и выражение его в виде математического соотношения.

Пример

Предприятие располагает двумя видами сырья S1 и S2 в количествах 15 и 13 условных единиц и изготавливает из него изделия двух видов П1 и П2. Изготовление единицы изделия П1 требует расхода сырья S1 в 1 усл. ед., S2 в 3 усл. ед., а для производства единицы изделия П2 необходимо сырья S1 – 3 усл. ед., сырья S2 - 1 усл. ед. Известна прибыль от реализации одной единицы продукции каждого вида. Для вида П1 она составляет 2 ден. ед, для вида П2 – 3 ден. ед. Требуется найти оптимальный план производства продукции, реализация которого обеспечит предприятию максимальную прибыль.

Составим экономико-математическую модель задачи.

Реализуем первый этап построения экономико-математической модели и выберем переменные.

Обозначим искомые переменные следующим образом:

х1 - количество единиц продукции вида П1,

х2 - количество единиц продукции вида П2.

Второй этап построения экономико-математической модели включает изучение информационной базы экономического процесса или объекта. Для наглядности процесса моделирования исходную информацию представим в виде таблицы 1.2.

Таблица 1.2 – Исходная информация

Вид сырья	Расход сырья на 1 ед. продукции	Запас сырья
П1	П2
S1	1	3	15
S2	3	1	13
Прибыль, ден. ед.	2	3

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