- •Введение
- •1. Общая задача линейного программирования
- •Задачи для самостоятельного решения:
- •2. Графический метод решения задач линейного программирования
- •2.1. Задача с двумя переменными
- •2.2. Графический метод решения задач линейного программирования с п переменными
- •Задачи для самостоятельного решения:
- •3. Симплексный метод решения задач линейного программирования
- •3.1. Симплекс-метод
- •3.2. Симплексные таблицы
- •Задачи для самостоятельного решения:
- •4. Теория двойственности
- •4.1. Виды математических моделей двойственных задач
- •4.2. Первая теорема двойственности
- •4.3. Вторая теорема двойственности
- •Задачи для самостоятельного решения
- •5. Транспортная задача линейного программирования
- •5.1. Формулировка транспортной задачи
- •5.2. Алгоритм решения транспортной задачи методом потенциалов
- •Задачи для самостоятельного решения
- •Список рекомендуемой литературы:
ЮЖНО- УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Факультет экономики и права
Кафедра государственно-правовых дисциплин
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ РЕШЕНИЯ
ЭКОНОМИЧЕСКИХ ЗАДАЧ МЕТОДАМИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Преподаватель:
Булгакова Маргарита Владиславовна,
канд. пед. наук
Челябинск, 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 (х1, х2, ..., хп) → max (min) (1.1)
при системе ограничений
(1.2)
Если целевая функция (1.1) и система ограничений (1.2) линейны, то задача математического программирования называется задачей линейного программирования.
Математическая модель задачи на нахождения максимального значения целевой функции записывается в виде
F(X) = с1 х1 + с2 х2 + ... + сп хп→max,
В задаче на нахождение минимального значения целевой функции математическая модель её запишется в виде
F(X) = с1 х1 + с2 х2 + ... + сп хп→min,
Рассмотрим варианты составления математической модели для следующих задач.
Задача 1. (Планирование производства.)
Некоторое предприятие выпускает три типа продукции П1,П2,П3 двумя технологическими способами S1 и S2. Количество продукции 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х11+ 30х21 , 2-го вида 25х12+20х22 , 3-го вида 30х13+ 15х23. Стоимость всей продукции (обозначим ее за F) равна 5(20х11+ 30х21)+3(25х12+20х22)+6(30х13+ 15х23) и она должна быть максимальной. Но при этом есть ограничения по времени: х11+ х12 + х13 ≤10, х21+ х22 + х23 ≤8 и очевидно, все хi j ≥ 0.
Окончательно получаем математическую модель задачи
F=5(20х11+ 30х21)+3(25х12+20х22)+6(30х13+ 15х23) → max,
Задача 2. (Задача о смеси.)
Известно, что при правильном питании человек должен получать в день не менее 20 единиц витамина А, не менее 15 единиц витамина В. Содержание этих витаминов в одной единице каждого из продуктов П1, П2, П3 задано табл. 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х1 +30x2 + +20х3. При этом количество витамина А равно 4x1 + 5х2 + 2х3 , витамина В — 5x1 + 2х2 + 6х3, получаем математическую модель:
F=25х1 +30x2 +20х3 → 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 м получится 3x1+ 2х2 + 2х3 + х4, по 2,5 м — x2 + 2x4 + х5; по 3 м — х 3 + x5 + 2x6. Обозначим через к — число полученных изделий, тогда
3x1+ 2х2 + 2х3 + х4 = или 2(3x1+ 2х2 + 2х3 + х4 )=к,
x2 + 2x4 + х5 = или 3(x2 + 2x4 + х5 )=к,
х 3 + x5 + 2x6=к. Исключим к.
2(3x1+ 2х2 + 2х3 + х4 )= 3(x2 + 2x4 + х5 ) или 6x1+ х2 + 4х3 -4х4 -3х5 =0,
2(3x1+ 2х2 + 2х3 + х4 )= х 3 + x5 + 2x6 или 6x1+ 4х2 + 3х3 +2х4 -х5-2х6=0.
Окончательно получим математическую модель к=х 3 + x5 + 2x6→ max,
все хi ≥0.
Мы видим, что различные экономические задачи приводят к одному и тому же типу математических задач. Задачи такого типа решаются методами линейного программирования.