max (Z= 6x1+5x2+4x3+3x4)
2x1+3x2+2x3+x4 < 25
4x1+x2+3x3+2x4 < 30
3x1+5x2+2x3+2x4 < 42
x1, x2, x3, x4 > 0
Математическая модель двойственной задачи
min (Z*= 25y1+30y2+42y3)
2y1+4y2+3y3 > 6
3y1+y2+5y3 > 5
2y1+3y2+2y3 > 4
y1+2y2+2y3 > 3
y1, y2, y3, y4 > 0
Стандартный вид
min (Z= -6x1-5x2-4x3-3x4)
2x1+3x2+2x3+x4+S1=25
4x1+x2+3x3+2x4+S2=30
3x1+5x2+2x3+2x4+S3=42
x1, x2, x3, x4, S1, S2, S3 > 0
Экономический смысл переменных
Xi – количество произведенной продукции
Yj – цена ресурса
Si – количество оставшегося ресурса
| базис | значение |  x1
| x2 | x3 | x4 | S1 | S2 | S3 | отношение |
| Z | -6 | -5 | -4 | -3 | |||||
| S1 | 12,5 | ||||||||
 S2
| 7,5 | ||||||||
| S3 | |||||||||
| Таблица 2 | |||||||||
| базис | значение | x1 |  x2
| x3 | x4 | S1 | S2 | S3 | отношение |
| Z | -3,5 | 0,5 | 1,5 | ||||||
S1
| 2,5 | 0,5 | -0,5 | ||||||
| x1 | 7,5 | 0,25 | 0,75 | 0,5 | 0,25 | ||||
| S3 | 19,5 | 4,25 | -0,3 | 0,5 | -0,8 | 4,59 | |||
| Таблица 3 | |||||||||
| базис | значение | x1 | x2 | x3 | x4 | S1 | S2 | S3 | отношение |
| Z | 1,2 | 1,4 | 0,8 | ||||||
| x2 | 0,2 | 0,4 | -0,2 | ||||||
| x1 | 6,5 | 0,7 | 0,5 | -0,1 | 0,3 | ||||
| S3 | 2,5 | -1,1 | 0,5 | -1,7 | 0,1 |
Анализ решения
Продукции 1 вида производим 6,5 ед., второго вида 4 единицы, третьего и четвертого вообще не производим. Прибыль при этом составит 59 ден. единиц.
Ресурс 1 типа стоит 1,4 ден. ед., 2 типа – 0,8 ден. ед. Третий тип ресурса у нас остался в количестве 2,5 ед., поэтому его покупать не нужно.
Ресурсы 1 и 2 типа дефицитны, 3 типа избыточен.
Эффективность производства
Z = 6*6.5+5*4+4*0+3*0=59 Z*=25*1.4+30*0.8+42*0=59 Производство в целом эффективно
2*1,4+4*0,8+3*0 < 6 6=6 Производство 1 вида продукции эффективно
3*1,4+1*0,8+5*0 < 5 5=5 Производство 2 вида продукции эффективно
2*1,4+3*0,8+2*0 < 4 5,2> 4 Производство 3 вида продукции не эффективно
1*1,4+2*0,8+2*0 < 3 3=3 Т.к. x4 не входит в базис, то оптимальный план не единственен.
Оценить целесообразность покупки 5 ед. второго ресурса по цене 10 ден. ед, т.е. единица ресурса обойдется нам в 2 ден. ед. Мы же готовы покупать только по 0,8 ден. ед. за 1 единицу ресурса.
а1 = 2, а2 = 2, а3 = 4. Цена новой продукции равна 4.
2*1,4+2*0,8+2*0 < 4 4,4> 4 Производство 5 вида продукции не эффективно.
Контрольные вопросы.
1.Определение математической модели экономической задачи.
2.Виды математических моделей ЛП.
3.Составление математической модели.
4.Экономическая формулировка математической модели прямой и двойственной задач.
5.Понятие двойственности в задачах линейного программирования.
6.Правило построения математической модели двойственной задачи.
7. Первая теорема двойственности.
8. Вторая теорема двойственности.
9. Третья теорема двойственности.
10.Алгоритм геометрического метода решения задач ЛП.
11.Симплексный метод решения задач ЛП и его применение.
12.Алгоритмм симплексного метода.
13.Анализ решения задачи по симплекс – таблице, отвечающей критерию оптимальности.
Лекция. Транспортная задача
Постановка задачи. Математическая модель
Транспортной задачи.
Постановка задачи:
Однородный груз сосредоточен у m поставщиков в объемах а1, а2, …, аm.
Данный груз необходимо доставить n потребителям в объемах, b1, b2, …, bn.
Известен Сij (i= 1, 2, …, m; j=1, 2,…, n) – стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю.
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны.
Исходные данные транспортной задачи записываются в таблице вида:
| bj аi | b1 | b2 | … | bn |
| А1 | С11 | С12 | … | С1n |
| А2 | С21 | С22 | … | С2n |
| … | … | … | … | … |
| аm | Cm1 | Cm2 | ... | Cmn |
Переменными (неизвестным) транспортной задачи являются xij(i=1,2,…,m; j=1,2,…,n) – объемы перевозок от каждого i-го поставщика j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок.
