Симплексный и распределительный методы

Министерство сельского  хозяйства РФ

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

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

«Пермская государственная  сельскохозяйственная академия

имени академика Д. Н. Прянишникова»

 

 

Кафедра земельного кадастра

ЭММ и модели

 

 

Контрольная работа по дисциплине

"Экономико-Математические  методы и модели"

 

 

 

Выполнила: студентка группы заочного обучения по специальности  «Экономика и управление на предприятии (в оценке недвижимости)» 

Старцева Екатерина Михайловна

Шифр: Экр (ОН)-11-4388

Работу проверила: Осокина  Н.В.

 

 

 

 

 

Пермь 2013

 

 

Содержание

Решение задач линейного программирования:

Часть 1. Симплексный метод……………………………………………….………3

Часть 2. Распределительный  метод………………………………………………...7

Список используемых источников………………………………………………10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Целевая функция:

X1 + 15X2 + 10X3 → max

Необходимо получить максимальный размер прибыли.

Неравенства:

2X1 + 4X2 + 3X3 ≤ 130

52X1 + 2,6X2 + 7X3 ≤150

3,5X1 + 5X2 – 2,4X3 ≤140

2X1 – 1,3X2 + 1,5X3 ≤ 120

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

2X1 + 4X2 + 3X3 + S₁= 130

52X1 + 2,6X2 + 7X3 +S₂=150

3,5X1 + 5X2 – 2,4X3 +S₃ =140

2X1 – 1,3X2 + 1,5X3 +S₄ =120

S1, S2, S3, S4 – дополнительные переменные и обозначают величины недоиспользованных в плане ресурсов.

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

X1 = 0        →     S1 =130     →    Z = 0

X2 = 0                 S2 = 150             

X3 = 0                 S3 = 140    S4 = 120  

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

Таблица 1 – Первая симплексная  таблица

Оценка	Баз. Перем.	Значение БП	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
0	S1	130	2	4	3	1	0	0	0
0	S2	150	5	2.6	7	0	1	0	0
0	S3	140	3.5	5	2.4	0	0	1	0
0	S4	120	2	1.3	1.5	0	0	0	1
	Z	0	-1	-15	-10	0	0	0	0

 

Решение не оптимально, необходимо улучшить план (признак оптимальности  – отсутствие в индексной строке отрицательных значений).

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

 Х2 – главный столбец первой симплексной таблицы ↑

Главная строка определяется по минимальному значению частного определения  значения базисных переменных на коэффициенты главного столбца, т.е. 130:4 = 32.5; 150:2.6 = 57.7; 140:5=28; 120:1.3=92.3

S3 – главная строка первой симплексной таблицы.

На пересечении главной  строки и главного столбца находится  главный элемент = 5.

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

Коэффициенты  главной  строки новой симплексной таблицы  рассчитываем путем деления  всех коэффициентов в строке на главный  элемент. (140:5=28; 3.5:5= 0.7; 2.4:5=0,48 и т.д.)

Таблица 2 – Вторая симплексная таблица

Оценка	Баз. Перем.	Значение БП	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
0	S1	18	-0.8	0	1.08	1	0	-0.8	0
0	S2	77.2	3.18	0	5.75	0	1	-0.52	0
15	X2	28	0.7	1	0.48	0	0	0.2	0
0	S4	83.6	1.09	0	0.88	0	0	-0.26	1
	Z	420	9.6	0	-2.8	0	0	3	0

Оценка Х2 = 3, S1, S3, S4 так и оставляем из первой таблицы. Главный столбец новой симплексной таблицы превращается в нулевой вектор столбец. Все остальные коэффициенты таблицы рассчитываются по правилу прямоугольника.

S₁Х1 = =- 0,8;

S₂Х1 = = 3,8;

S₄Х1 = = 1,9 и т.д.

Выбираем главный столбец (отрицательное).

Главный столбец новой  симплексной таблицы Х3.

Выбираем главную строку – 18:1,08 = 16,7; 77,2:5,75=13,4; 28:0,48=58,3; 83,6:88=95.

S2 – главная строка новой симплексной таблицы.

Главный элемент – 5,75

Строим третью симплексную  таблицу (рассчитывается как предыдущая таблица).

 

 

Таблица 3 – Третья симплексная  таблица

Оценка	Баз. Перем.	Значение БП	Не базисные переменные
			Х1	Х2	Х3	S1	S2	S3	S4
0	S1	3,5	-1,4	0	0	1	-0,2	-0,7	0
2,8	Х3	13,4	0,5	0	1	0	0,2	-0,1	0
15	X2	21,5	0,4	1	0	0	-0,1	0,24	0
0	S4	71,8	0,61	0	0	0	-0,15	-0,18	1
	Z	457,58	11,5	0	0	0	0,5	2,75	0

Оптимальный план можно записать так:

S₁ = 3.5

x₃ = 13.42

x₂ = 21.56

S₄ = 71.84

Проверка:

F(X) = 15*21.56 + 10*13.42 = 457.58

 

 

 

 

 

 

 

 

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

1. Проверить задачу на сбалансированность.
2. Составить базисный план способом северо-западного угла. Рассчитать значение функции цели.
3. Составить базисный план методом наилучшего элемента на максимальном значении функции цели. Рассчитать значение функции цели.
4. Сравнить результаты решения двух базисных планов.
5. Проверить базисный план, составленный методом наилучшего элемента на оптимальность методом потенциала и провести улучшение плана до оптимального результата (делать проверку значения функции цели)

Задача.

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

Таблица 5

участки севооборота	Урожайность культур при  размещении на данном участке, тонн с 1 га				Проектные площади участков, га
	Озимая пшеница	ячмень	Однолетние травы	рожь
1	15	2	4	19	350
2	3	4	14	19	460
3	22	13	5	15	1630
4	2	6	15	3	660
5	8	25	11	29	1260
Площадь посевов культур, га	1200	1350	1500	600	4360   4650

 

1. Проверка задачи на сбалансированность. Сравниваем проектные площади участков и площадь посевов культур.

350+460+1630+660+1260=4630

1200+1350+1500+600=4650

Площади не совпадают, следовательно, задача является открытой, т.е. не сбалансированной.

Добавляем фиксированную  строку, приравниваем 4650=4650

Аф = 4650-4360 = 290

 

 

Таблица 6 – Сбалансированная задача.

участки севооборота	Урожайность культур при  размещении на данном участке, тонн с 1 га				Проектные площади участков, га
	В1	В2	В3	В4
А1	15	2	4	19	350
А2	3	4	14	19	460
А3	22	13	5	15	1630
А4	2	6	15	3	660
А5	8	25	11	29	1260
Аф	1	1	1	1	290
Площадь посевов культур, га	1200	1350	1500	600	4650

В фиксированном столбце  оценка равна 0.

2. Построим базисный план методом северо-западного угла

Таблица 7 – Метод северо-западного  угла

участки севооборота	Урожайность культур при  размещении на данном участке, тонн с 1 га				Проектные площади участков, га
	В1	В2	В3	В4
А1	350   15	-        2	-         4	-       19	350
А2	460   3	-        4	-       14	-       19	460
А3	390   22	1240    13	-        5	-       15	1630
А4	-      2	110       6	550     15	-         3	660
А5	-      8	-       25	950     11	310     29	1260
Аф	-     1	-         1	-        1	290      1	290
Площадь посевов культур, га	1200	1350	1500	600	4650