bannerka.ua

Пример выполнена контрольная работа… — Часть 1

Пример

Выполнена контрольная работа + Комментарий к выполненной работы

Задача 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

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

Пример выполнена контрольная работа... - Часть 1

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

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

Рис. 1.

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

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

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

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

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

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

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

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

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

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

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

Пример выполнена контрольная работа... - Часть 1

Из первого уравнения выражение Х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, в которой значение целевой функции равно:

Пример выполнена контрольная работа... - Часть 1

Чтобы хозяйству получить максимальную прибыль в размере 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).

Пример выполнена контрольная работа... - Часть 1

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

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

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

Пример выполнена контрольная работа... - Часть 1; Пример выполнена контрольная работа... - Часть 1; Пример выполнена контрольная работа... - Часть 1; Пример выполнена контрольная работа... - Часть 1; Пример выполнена контрольная работа... - Часть 1; Пример выполнена контрольная работа... - Часть 1; Пример выполнена контрольная работа... - Часть 1; Пример выполнена контрольная работа... - Часть 1

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

Пример выполнена контрольная работа... - Часть 1

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)

Пример выполнена контрольная работа... - Часть 1

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

Пример выполнена контрольная работа... - Часть 1

* 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) — Правые части уравнений.

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

Например:

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

Пример выполнена контрольная работа... - Часть 1

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

Пример выполнена контрольная работа... - Часть 1

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

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

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

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

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

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

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

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

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

Пример выполнена контрольная работа... - Часть 1

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

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

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

1) Пример выполнена контрольная работа... - Часть 1 2) Пример выполнена контрольная работа... - Часть 1

3) Пример выполнена контрольная работа... - Часть 1 4) Пример выполнена контрольная работа... - Часть 1

Итерация 2

Базис

C (j)

X1

X2

X3

X4

S1

S2

Y1

S3

Y2

B (i)

Пример выполнена контрольная работа... - Часть 1

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

Пример выполнена контрольная работа... - Часть 1

* 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)

Пример выполнена контрольная работа... - Часть 1

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

Пример выполнена контрольная работа... - Часть 1

-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)

Пример выполнена контрольная работа... - Часть 1

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

Пример выполнена контрольная работа... - Часть 1

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.

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

Условие задачи.

В пунктах отправления А1, А2, А3, …. находится однородный груз в количестве a1, а2, а3, …. соответственно, который необходимо перевезти в пункты назначения В1, В2, В3, …. , Потребность каждого из которых составляет b1, b2, b3, …. . Известно расстояние между пунктами перевозок (оценки).

Есть три поставщика с такими запасами груза:

А1 = 26 т, А2 = 33 т, А3 = 45 т;

И четыре потребителя с потребностью на этот груз:

В1 = 14 т, В2 = 19 т, В3 = 20 т, В4 = 5 т.

Известно расстояние между пунктами перевозок.

Расстояние между пунктами перевозок, км (Сij).

Поставщики

Потребители

B1

B2

B3

B4

A1

6

4

15

19

A2

13

17

28

3

A3

5

20

6

10

Необходимо найти количество груза, который должен получить каждый потребитель от того или иного поставщика, чтобы общее количество тонно-километров была минимальной.

Решения.

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

метод северо-западного угла, метод наименьшей стоимости, метод двойного преимущества.

Задача, в которой общие запасы равны общим потребностям называется закрытой транспортной задачей:

- общие запасы = 26 +33 +45 = 104 т;

- общие потребности = 14 +19 +20 +5 = 58 т.

Итак задача открыта, поэтому необходимо ввести фиктивного потребителя, которому следует перевезти Вфикт = 104-58 = 46 т.

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

Первую транспортную таблицу заполним методом северо-западного угла: первой заполняется верхняя левая клетка Х11, в которую заносится или все запасы А1, или вся потребность В1 в зависимости от того, что меньше. На каждом следующем шаге рассматривается первый из оставшихся пункт и пункт отправления:

-если это пункт назначения, то потребность его определяется по правилу: Хij = ai — вывезен груз из Ai;

-если это пункт отправления, то запасы его определяется по правилу: Хij = bj — завезен груз в Bj.

Так заполняются все клетки таблицы с Х11 по ХMh (это заполнение имеет вид лестницы по диагонали таблицы).

В клетку Х11 записываем 14 и соответственно покрывается вся потребность первых потребителей за счет первого поставщика, у которого остается груз в количестве 26-14 = 12тон, который можно увезти в другой пункт назначения. Временно не рассматривается столбец В1. Потребность второго пункта потребления В2 составляет 19тон, а за счет первого поставщика А1 можно завезти только 12тон, 7тон завозится второго пункта отправления. Временно не рассматривается строка А1. В поставщика А2 было 33тоны, из которых 7тон груза в пункт потребления В2, 20тон в пункт потребления В3 и 1тонна в фиктивный пункт потребления ВФикт. Потребность фиктивного пункта потребления покрывается за счет второго и третьего поставщика.

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

Fmin = 14 * 6 +12 * 4 +7 * 17 +20 * 28 +5 * 3 +1 * 0 +45 * 0 = 826 т-км.

С помощью метода потенциалов можно определить оптимальный план транспортной задачи. Задача имеет оптимальное значение, когда сумма потенциалов во всех клетках таблицы не превышает оценок, т. е. при решении задачи на минимум план считается оптимальным в том случае, если для всех свободных ячеек соблюдается требование: Ui + Vj £Cij, а для занятых Ui + Vj = Cij.

Tagged with: , , , , , , ,
Posted in Математические модели в расчетах на эвм

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

Ваш 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с
Возможно Вы искали: