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

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

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

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

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

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

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

ЭММ и модели

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

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

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

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

Шифр: Экр (ОН)-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 – Первая симплексная  таблица

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

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

 Х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 – Вторая симплексная таблица

Оценка Х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 – Третья симплексная  таблица

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

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. Проверка задачи на сбалансированность. Сравниваем проектные площади участков и площадь посевов культур.

350+460+1630+660+1260=4630

1200+1350+1500+600=4650

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

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

Аф = 4650-4360 = 290

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

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

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

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

Распределение площадей начинается с северо-западного угла.

Начинаем с первого  угла Х11 выбираем наименьшее 350 или 1200.

Х21 выбираем  наименьшее 460 или (1200-350)=850

Х32 выбираем наименьшее (1200-350-460)=390 или 1630 и т.д.

Количество занятых клеток в базисном плане должно быть равно  m+n – 1

m = 4, n = 6 → 4+6 – 1 = 9. Количество занятых клеток = 9.

Рассчитаем значение функции  цели:

F=350*15+460*3+390*22+1240*13+110*6+550*15+950*11+310*29+290*1=59970

3. Составляем базисный план методом наилучшего элемента на максимальном значении функции цели.

Выбираем из всей таблицы  самую большую оценку = 29, записываем в клетку 600 (распределяем), следующая  максимальная оценка 25, из 1260 – 600 = 660, следующая  максимальная оценка 22, записываем 1200 и т.д.

Таблица 8 – Метод наилучшего элемента

F = 350*4+460*14+1200*22+430*13+660*15+660*25+600*29+290*1+30*1=83880

6+4-1=9 – условие выполняется,  план не вырождается.

Ответ: оптимальный состав культур в севообороте.

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

1. Шапкин А.С., Мазаева Н.П. Математические методы и модели исследования операций: Учебник. – 2-е изд., перераб. и доп. – М.: Дашков и К, 2005. – 400 с.
2. Экономико-математические модели и прогнозирование рынка труда: Учеб. пособие. – М.: Вузовский учебник, 2005. – 144 с.
3. С.И. Шелобаев. Математические методы и модели в экономике, финансах, бизнесе: Учеб. пособие для вузов. – 2-е изд., перераб. и доп. – М.: ЮНИТИ, 2005. – 400 с.
4. Математическая экономика: Учебник для вузов / В.А. Колемаев. – 3-е зд., перераб. и доп. – М.: ЮНИТИ-ДАНА, 2005. – 399 с.
5. М.С.Красс, Б.П.Чупрынов. Математика для экономистов. – М.: Питер, 2004. - 464 с.
6. Солодовников А.С. Математика в экономике: Учебник: в 2-х частях / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2003. – 560 с.
7. Введение в экономико-математические модели налогообложения: Учеб. пособие / Под ред. Д.Г. Черника. – М.: Финансы и статистика, 2002. – 256 с.
8. Ляшенко И.Н., Карагодова Е.А. Линейное и нелинейное программирование. «Вища школа», 1975. - 369 с.
9. Заславский Ю.Л. Сборник задач по линейному программированию. М. 1969-256 с.
10. П.Е.Данко, А.Г. Попов высшая математика в упражнениях и задачах. Ч. 3. М., «Высшая школа», 1971-288 с.
11. В.А.Абчук Экономико-математические методы «Союз» Санкт-Петербург 1999-318 с.