ЮЖНО- УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет экономики и права

Кафедра государственно-правовых дисциплин

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ РЕШЕНИЯ

ЭКОНОМИЧЕСКИХ ЗАДАЧ МЕТОДАМИ

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

Преподаватель:

Булгакова Маргарита Владиславовна,

канд. пед. наук

Челябинск, 2006 г.

ОГЛАВЛЕНИЕ

Введение	3
1. Общая задача линейного программирования	4
Задачи для самостоятельного решения	7
2. Графический метод решения задач линейного программирования	10
2.1. Задача с двумя переменными	10
2.2. Графический метод решения задач линейного программирования с п переменными	12
Задачи для самостоятельного решения	14
3. Симплексный метод решения задач линейного программирования	16
3.1. Симплекс-метод	16
3.2. Симплексные таблицы	26
Задачи для самостоятельного решения	30
4. Теория двойственности	32
4.1. Виды математических моделей двойственных задач	32
4.2. Первая теорема двойственности	35
4.3. Вторая теорема двойственности	39
Задачи для самостоятельного решения	43
5. Транспортная задача линейного программирования	44
5.1. Формулировка транспортной задачи	44
5.2. Алгоритм решения транспортной задачи методом потенциалов	45
Задачи для самостоятельного решения	52
Список рекомендуемой литературы	54

Введение

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

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

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

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

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

1. Общая задача линейного программирования

Общая задача математического программирования: найти экстремум целевой функции F(X) =f (х₁, х₂, ..., х_п) → max (min) (1.1)

при системе ограничений

(1.2)

Если целевая функция (1.1) и система ограничений (1.2) линейны, то задача математического программирования называется задачей линейного программирования.

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

F(X) = с₁ х₁ + с₂ х₂ + ... + с_п х_п→max,

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

F(X) = с₁ х₁ + с₂ х₂ + ... + с_п х_п→min,

Рассмотрим варианты составления математической модели для следующих задач.

Задача 1. (Планирование производства.)

Некоторое предприятие выпускает три типа продукции П₁,П₂,П₃ двумя технологическими способами S₁ и S₂. Количество продукции j-гo вида (j = 1,2,3), произведенного i -м способом (i = 1,2) за единицу времени задано табл. 1.3.

Таблица 1.3

П родукции Т.способ	П1	П2	П3	Лимит времени
S1	20	25	30	10
S2	30	20	15	8
Стоимость 1 ед. продукции	5	3	6

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

Математическая модель задачи

Обозначим через х_{i j} — время, затраченное на изготовление продукции Пj (j = 1,2,3) i -м способом. Тогда план производства будет иметь вид:

S1	х11	х12	х13
S2	х21	х22	х23

При этом продукции 1-го вида будет выпущено 20х₁₁+ 30х₂₁ , 2-го вида 25х₁₂+20х₂₂ , 3-го вида 30х₁₃+ 15х₂₃. Стоимость всей продукции (обозначим ее за F) равна 5(20х₁₁+ 30х₂₁)+3(25х₁₂+20х₂₂)+6(30х₁₃+ 15х₂₃) и она должна быть максимальной. Но при этом есть ограничения по времени: х₁₁+ х₁₂ + х₁₃ ≤10, х₂₁+ х₂₂ + х₂₃ ≤8 и очевидно, все х_{i j} ≥ 0.

Окончательно получаем математическую модель задачи

F=5(20х₁₁+ 30х₂₁)+3(25х₁₂+20х₂₂)+6(30х₁₃+ 15х₂₃) → max,

Задача 2. (Задача о смеси.)

Известно, что при правильном питании человек должен получать в день не менее 20 единиц витамина А, не менее 15 единиц витамина В. Содержание этих витаминов в одной единице каждого из продуктов П₁, П₂, П₃ задано табл. 1.4. Составить наиболее дешевый рацион питания. Все данные занесены в табл. 1.4.

Таблица 1.4

В итамины Продукты	А	В	Стоимость одной единицы Пi
П1	4	5	25
П2	5	2	30
П3	2	6	20
	≥20	≥15

Математическая модель задачи

Пусть х_i — количество продукта П_i, потребляемого в день (i=1,2,3), тогда стоимость всех продуктов (обозначим F) будет равна F=25х₁ +30x₂ + +20х₃. При этом количество витамина А равно 4x₁ + 5х₂ + 2х₃ , витамина В — 5x₁ + 2х₂ + 6х₃, получаем математическую модель:

F=25х₁ +30x₂ +20х₃ → min,

Задача 3. (О раскрое материала.)

Для изготовления некоторого изделия требуется 2 планки по 2 м, 3 — по 2,5 м и одна трехметровая. Для этого используют 100 досок по 7 м длиной. Как распилить доски, чтобы получить возможно большее число комплектов?

Математическая модель задачи

Рассмотрим возможные варианты распиливания досок.

Т аблица 1.5

№ варианта Длина планки	1	2	3	4	5	6
2 м	3	2	2	1	0	0
2,5 м	0	1	0	2	1	0
3 м	0	0	1	0	1	2

Обозначим через х_i— количество досок, распиленных i-м способом, тогда заготовок по 2 м получится 3x₁+ 2х₂ + 2х₃ + х₄, по 2,5 м — x₂ + 2x₄ + х₅; по 3 м — х ₃ + x₅ + 2x₆. Обозначим через к — число полученных изделий, тогда

3x₁+ 2х₂ + 2х₃ + х₄ = или 2(3x₁+ 2х₂ + 2х₃ + х₄ )=к,

x₂ + 2x₄ + х₅ = или 3(x₂ + 2x₄ + х₅ )=к,

х ₃ + x₅ + 2x₆=к. Исключим к.

2(3x₁+ 2х₂ + 2х₃ + х₄ )= 3(x₂ + 2x₄ + х₅ ) или 6x₁+ х₂ + 4х₃ -4х₄ -3х₅ =0,

2(3x₁+ 2х₂ + 2х₃ + х₄ )= х ₃ + x₅ + 2x₆ или 6x₁+ 4х₂ + 3х₃ +2х₄ -х₅-2х₆=0.

Окончательно получим математическую модель к=х ₃ + x₅ + 2x₆→ max,

все х_i ≥0.

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