bannerka.ua

Графический метод и симплекс метод решения задач

Графический метод и симплекс метод решения задач линейного программирования

1. Обзор темы

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

Известны затраты труда, затраты удобрений и прибыль в расчете на 1 га.

Культура

Затраты труда на 1га, человеко-часов

Затраты удобрений на 1 га, ц. д. р.

Прибыль с 1 га, грн.

Ячмень

26

2,5

200

Подсолнечник

31,5

4,8

250

Определить, какие площади следует отвести под каждую культуру, чтобы получить максимальную прибыль.

Решения.

Разработаем экономико-математическую модель задачи:

X1 — площадь ячменя;

X2 — площадь подсолнечника.

Целевая функция (максимальная прибыль) имеет вид:

F = 200Х1 + 250Х2  max

Ограничения задачи:

1-е ограничение характеризует использование площади пашни

Х1 + Х2 <= 60

2-е ограничение касается использования затрат труда

26Х1 + 31,5Х2 <= 1890

3-е ограничение описывает использование удобрений

2,5Х1 + 4,8Х2 <= 240

В задачи следует учесть условие неотрицательности переменных: Х1 и Х2> = 0

Ограничения задачи запишем в виде системы уравнений:

Графический метод и симплекс метод решения задач

В системе координат нарисуем соответствующие прямые:

I. Х1= 0, Х2= 60; Х2= 0, Х1= 60

II. Х1= 0, Х2= 1890/31, 5 = 60; Х2= 0, Х1= 1890/26 = 72,7

III. Х1= 0, Х2= 240/4, 8 = 50; Х2= 0, Х1= 240/2, 5 = 96

Графический метод и симплекс метод решения задач

Рис. 1.

Каждая прямая разделила плоскость на две полуплоскости. Координаты точек одной из полуплоскостей удовлетворяет условию соответствующей неравенства (все точки этой полуплоскости, подставленные в неравенство не отрицают знака), второй — нет. Чтобы определить полуплоскость решений, необходимо взять любую точку, которая принадлежит к одной из напивплощ, и проверить, удовлетворяют ее координаты данной неравенства. Если координаты взятой точки удовлетворяют условию соответствующей неровности, то полуплоскость, которой принадлежит точка, является полуплоскость решений; иначе — вторая полуплоскость.

Найдем, например, полуплоскость решений, определяется неравенством

Х12 £ 60. Для этого, построив прямую Х1 Х2 = 60 (на рис.1 она I), возьмем любую точку, принадлежащую одной из напивплощ, например точку О (0; 0). Координаты этой точки удовлетворяют неравенству 0 +0 £ 60; Значит, полуплоскость, которой принадлежит точка О (0; 0), определяется неравенством Х1 +Х2 £ 60, Что показано стрелками на рис.1.

Пересечение всех полученных напивплощ решений определяет многоугольник решений задачи (область возможных значений). Точки этой области удовлетворяют всем ограничениям задачи.

0АВС — многоугольник решений.

Необходимо найти точку, которая принадлежит четырехугольнике 0АВС, в которой целевая функция F Принимает максимальное значение. Для этого строится векторГрафический метод и симплекс метод решения задач (200; 250), координатами которого являются коэффициенты в целевой функции при соответствующих переменных, и к нему проводится перпендикуляр.

Перемещаем перпендикуляр по направлению, указывающий вектор:

- в первой точке соприкосновения перпендикуляра с многоугольником решений будет точка Min;

- в последней точке соприкосновения с многоугольником решений будет точка max.

Так что в точке В целевая функция имеет максимальное значение.

Чтобы определить точные координаты точки В, необходимо решить систему из двух уравнений, линии которых образовали эту точку. Точка В лежит на пересечении первой и третьей линий, поэтому берутся именно первое и третье уравнения.

Графический метод и симплекс метод решения задач

Из первого уравнения выражение Х2 = 60 -Х1 и подставим во второе уравнение:

2,5Х1+4,8 (60 -Х1) = 240

2,5Х1 +288-4,8Х1 = 240

2,3Х1 = 48

Х1 = 20,87

Х2 = 60-20,87 = 39,13

Таким образом точка В(20.87; 39.13) — точка max, в которой значение целевой функции равно:

Графический метод и симплекс метод решения задач

Чтобы хозяйству получить максимальную прибыль в размере 13956,5 грн., Необходимо посеять 20,87 га ячменя и 39,13 га подсолнечника.

2. Фермер может выращивать 4 культуры на площади 80га. Он уже вложил соглашения на продажу определенной продукции (объем продаж) и может приобрести 250ц минеральных удобрений.

Площадь пропашных культур (подсолнечник, сахарная свекла, картофель, Кукуруза) Должна быть 20 га.

Затраты труда и удобрений, прибыль с 1 га приведены в таблице.

Культуры

Урожайность,

Ц / га

Объем продаж,

Ц

Расхода удобрений на 1га, ц

Прибыль,

Грн. / Га

Пшеница

30

-

3,5

160

Ячмень

25

-

3

120

Просо

20

200

3

100

Картофель

330

-

5

260

Определить, какие площади следует отвести под каждую культуру, чтобы получить максимальную прибыль. Разработать экономико-математическую модель и решить задачу.

Решение

Разработаем экономико-математическую модель задачи.

Переменные:

Х1 — площадь пшеницы;

Х2 — площадь ячменя;

Х3 — площадь проса;

Х4 — площадь картофеля.

Целевая функция (максимальная прибыль) будет иметь вид:

F= 160X1 +120X2 +100X3 +260X4 à max

На переменные задачи наложены ограничения:

1-е ограничение характеризует использование площади пашни

Х1 + Х2 + Х3 + Х4 <= 80

2-е ограничение касается соглашения на продажу проса (200 ц):

20 Х 3> = 200

3-е ограничение описывает использование удобрений

3,5Х1 + 3Х2 + 3Х3 + 5Х4 <= 250

4-е ограничение описывает условие, что площадь картофеля должна быть 20 га:

Х4 = 20

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

Графический метод и симплекс метод решения задач

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

F= 160 ×X1 +120 ×X2 +100 ×X3 +260 ×X4 +0 ×S5 +0 ×S6 +0 ×S7à max

Ограничения задачи запишем в векторном виде:

Графический метод и симплекс метод решения задач; Графический метод и симплекс метод решения задач; Графический метод и симплекс метод решения задач; Графический метод и симплекс метод решения задач; Графический метод и симплекс метод решения задач; Графический метод и симплекс метод решения задач; Графический метод и симплекс метод решения задач; Графический метод и симплекс метод решения задач

Среди всех векторов лишь два единичных (А5 и А7). Во второе и четвертое ограничения необходимо ввести искусственные переменные. Запишем ограничения задачи и целевую функцию с искусственными переменными:

Графический метод и симплекс метод решения задач

F= 160 ×X1 +120 ×X2 +100 ×X3 +260×X4+0 ×S5 +0 ×S6 +0 × S7-M ×Y1-M ×Y2 à max

X — Основные переменные, S — Дополнительные переменные, Y — Искусственные переменные

Решение задач симплексным методом осуществляется в таблицах, заполним первую таблицу.

Итерация 1

Базис

C (j)

X1

X2

X3

X4

S1

S2

Y1

S3

Y2

B (i)

Графический метод и симплекс метод решения задач

160

120

100

260

0

0

-M

0

-M

S1

0

1

1

1

1

1

0

0

0

0

80

80

Y1

-M

0

0

20

0

0

-1

1

0

0

200

10

S3

0

3,5

3

3

5

0

0

0

1

0

250

83,33

Y2

-M

0

0

0

1

0

0

0

0

1

20

Inf

Графический метод и симплекс метод решения задач

* Big M

-160

0

-120

0

-100

-20

-260

-1

0

0

0

1

0

0

0

0

0

0

0

-220

Текущее значение целевой функции (Max) = 0 + (-220 Big M)

(В базис вводим переменную Х3; выводим переменную Y1),

Inf — действие не выполняется, потому что делить на 0 невозможно

Система ограничений задачи записывается в табличном виде (Итерация 1): в Базис записываются переменные, которые образовали систему одиничничних векторов (для первой таблицы), в столбик С (J) — Коэффициенты в целевой функции при переменных, которые вошли в Базис, в столбцы Х1, Х2, Х3, Х4, S1, S2, Y1, Y2 — соответствующие коэффициенты при этих переменных в каждом ограничении; столбик B (i) — Правые части уравнений.

Индексный строку Графический метод и симплекс метод решения задач рассчитывается по правилу — каждое значение столбца С (j) умножается на соответствующий элемент расчетного столба, что получено в результате умножения добавляется и из этой суммы вычитается коэффициент при переменной в целевой функции, получено: число без М записывается в строку Графический метод и симплекс метод решения задач, число с М записывается в строку *Big M.

Например:

Рассчитаем индексный строку для столбца Х1:

Графический метод и симплекс метод решения задач

Рассчитаем индексный строку для столбца Х3:

Графический метод и симплекс метод решения задач

Задача имеет оптимальное решение, когда в индексной строке не существует отрицательных элементов при решении задач на max.

Если условие оптимальности не выполняется, необходимо определить генеральный (направляющий) элемент, лежащий на пересечении генерального столбца и генерального строки и перейти к новой таблице. Определяется направляющий столбец, на который указывает наибольшее по абсолютной величине отрицательное значение в индексной строке. Затем определяется направляющий строка: необходимо разделить каждое значение столбца B(I) На соответствующее значение генерального столбца и наименьшее значение, которое будет получено, указывать на направляющий строку. При определении генерального строки невозможно делить на ноль и отрицательный элемент.

Итак: Х3 — генеральный столбец;

Строка 2 — генеральный строку;

20 — генеральный элемент.

Правила перехода к новой таблице:

1. Вместо генерального элемента записывается 1, вместо всех других элементов генерального столбца 0;

2. Все элементы генерального строки делятся на генеральный элемент;

3. Все остальные элементы таблицы рассчитываются по правилу прямоугольника:

Графический метод и симплекс метод решения задач

Если из базиса получается некоторая искусственная переменная, то с этого момента соответствующий столбец не рассчитывается.

Рассчитаем вторую таблицу (итерация 2)

Рассмотрим как по правилу прямоугольника определяется несколько значений:

1) Графический метод и симплекс метод решения задач 2) Графический метод и симплекс метод решения задач

3) Графический метод и симплекс метод решения задач 4) Графический метод и симплекс метод решения задач

Итерация 2

Базис

C (j)

X1

X2

X3

X4

S1

S2

Y1

S3

Y2

B (i)

Графический метод и симплекс метод решения задач

160

120

100

260

0

0

-M

0

-M

S1

0

1

1

0

1

1

0,05

0

0

70

70

X3

100

0

0

1

0

0

-0,05

0

0

10

Inf

S3

0

3,5

3

0

5

0

0,15

1

0

220

44

Y2

-M

0

0

0

1

0

0

0

1

20

20

Графический метод и симплекс метод решения задач

* Big M

-160

0

-120

0

0

0

-260

-1

0

0

5

0

0

0

0

0

1000

-20

Текущее значение целевой функции (Max) = 1000 + (-20 Big M)

(В базис вводим переменную Х4; выводим переменную Y2)

Задача еще не имеет оптимального решения, следует перейти к новой таблицы (итерация 3).

Итерация 3

Базис

C (j)

X1

X2

X3

X4

S1

S2

Y2

S3

Y4

B (i)

Графический метод и симплекс метод решения задач

160

120

100

260

0

0

-M

0

-M

S1

0

1

1

0

0

1

0,05

0

50

50

X3

100

0

0

1

0

0

-0,05

0

10

Inf

S3

0

3,5

3

0

0

0

0,15

1

120

34,29

X4

260

0

0

0

1

0

0

0

20

Inf

Графический метод и симплекс метод решения задач

-160

-120

0

0

0

-5

0

6200

Текущее значение целевой функции (Max) = 6200

(В базис вводим переменную Х1; выводим переменную S3)

Итерация 4

Базис

C (j)

X1

X2

X3

X4

S1

S2

Y2

S3

Y4

B (i)

Графический метод и симплекс метод решения задач

160

120

100

260

0

0

-M

0

-M

S1

0

0

0,143

0

0

1

0,007

-0,286

15,71

0

X3

100

0

0

1

0

0

-0,05

0

10

0

X1

160

1

0,857

0

0

0

0,043

0,286

34,29

0

X4

260

0

0

0

1

0

0

0

20

0

Графический метод и симплекс метод решения задач

0

17,1

0

0

0

1,86

45,7

11685,7

(Max) Оптимальная величина ЦФ = 11685,7

Задача имеет оптимальное решение, так как в индексной строке не существует отрицательных элементов (выполняется условие оптимальности).

Чтобы фермеру получить максимальную прибыль в размере 11685,7 грн., Необходимо посеять 34,29 га пшеницы (Х1), 10 га проса (Х3), 20 га картофеля (Х4).

При таком плане производства остается незасеянными пашня в количестве 15,71 га (S1) удобрения и трудовые ресурсы будут использованы полностью (в столбце Базис нет переменных S2 и S3).

3. Рекомендуемая литература

Курносов А. П., Сысоев И. А. Вычислительная техника т экономико-математические методы в сельском хозяйстве. — М., 1989. Кузнецов Ю. Н., Кузобов В. И., Ермольев Ю. М. Математическое программирование. — М.: Высш. шк., 1976. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. Исследование операций в экономике: Учебн. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин. М. Н. Фридман; Под ред. проф. Н. Ш. Кремера. — М.: Банки и биржи, ЮНИТИ, 1997. Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высш. Шк. », 1986, — 319 с. Ляшенко И. Н. Линейное и нелинейное Программирование. — и К. Вищашк., 1975, -371 с.

· Дополнительная

1. Математическое моделирование экономических процессов в сельском хозяйстве / Гатаулин А. М. и др.; Под ред. А. М. Гатаулина. — М.: Агропромиздат, 1990. — 432с.: Ил.

2. Эддоус М., Стэнфилд Р. Методы принятия решений / Пер. с англ. под ред. член-корр. РАН И. И. Елисеевой. — М.: Аудит, ЮНИТИ, 1997. — 590С.

Крушевский А. В., Шевцов К. И. Математическое программирование и моделирование в экономике.: Учеб. пособие для вузов. — М.: Высшая школа. Головное изд-во, 1979. — 456с. Курицкий Б. Я. Поиск оптимальных решений средствами Excel 7.0. — СПб.: ВНV — Санкт-Петербург, 1997. — 384с., Ил. Ляшенко И. Н. Линейное и нелинейное программирование. — М.: Высшая школа., 1975. Степанюк В. В. Методы математического программирования. — М.: Высшая школа., 1984. Кузнецов Ю. Н., Кудрявцев В. И. Математическое программирование. — М., 1980. Франс Дж. и др. Математические модели в сельском хозяйстве. М.: Агропромиздат, 1987 Кравченко Р. Г. Математическое моделирование в сельском хозяйстве. М.: Колос, 1978. Кузнецов Ю. Н. Математические модели в с / х. М.: Высшая школа, 1981 Карпенко А. ф. Практикум по математическому моделированию экономических агропромышленных процессов в сельском хозяйстве. М.: Финансы и статистика, 1985.

Tagged with: , , , , ,
Posted in Математические модели в расчетах на эвм
No Comments » for Графический метод и симплекс метод решения задач
6 Pings/Trackbacks for "Графический метод и симплекс метод решения задач"
  1. […] правило прямоугольника в симплекс методе примеры реше… […]

  2. […] экономико-математическое моделирование примеры решен… […]

  3. […] экономико-математическое моделирование графический м… […]

Добавить комментарий

Ваш e-mail не будет опубликован.

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Перечень предметов
  1. Бухучет в ресторанном хозяйстве
  2. Введение в специальность 4к.2с
  3. Высшая математика 3к.1с
  4. Делопроизводство
  5. Информационные технологии в области
  6. Информационные технологии в системах качества стандартизаціісертифікаціі
  7. История украинской культуры
  8. Математические модели в расчетах на эвм
  9. Методы контроля пищевых производств
  10. Микробиология молока и молочных продуктов 3к.1с
  11. Микропроцессорные системы управления технологическими процессами
  12. Научно-практические основы технологии молока и молочных продуктов
  13. Научно-практические основы технологии мяса и мясных продуктов
  14. Общая технология пищевых производств 4к.2с
  15. Общие технологии пищевых производств
  16. Организация обслуживания в предприятиях ресторанного хозяйства
  17. Основы научных исследований и техничнои творчества
  18. Основы охраны труда
  19. Основы пидприемницькои деятельности и агробизнеса
  20. Основы физиологии и гигиены питания 3к.1с
  21. Пищевые и диетические добавки
  22. Политология
  23. Получения доброкачественного молока 3к.1с
  24. Прикладная механика
  25. Прикладная механика 4к.2с
  26. Теоретические основы технологии пищевых производств
  27. Технологический семинар
  28. Технологическое оборудование для молочной промышленности
  29. Технологическое оборудование для мьяснои промышленности
  30. Технология продукции предприятий ресторанного хозяйства
  31. Технология хранения консервирования и переработки молока
  32. Технология хранения, консервирования и переработки мяса
  33. Технохимическому контроль
  34. Управление качеством продукции ресторанного хозяйства
  35. Физика
  36. Физическое воспитание 3к.1с
Возможно Вы искали: