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

Киреева Наталья Владимировна

Рабочая тетрадь к уроку математики на тему «Задачи линейного программирования» разработана мною для одноимённого урока математики (повышенный уровень). может быть использована как на уроке, семинарском занятии, так и для самостоятельной работы студента по теме "Линейное программирование", так как включает в себя историческую справку, описание основных видов задач ЛП, составление математической модели для каждого вида, моделирование задач ЛП, содержит алгоритм решения транспортной задачи и глоссарий, таким образом позволяет систематизировать зания по данной теме и проконтролировать степень  усвоения материала. 

Скачать:

ВложениеРазмер
Microsoft Office document icon rabochaya_tetrad.doc325.5 КБ

Предварительный просмотр:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

КРАСНОДАРСКОГО КРАЯ

ГБПОУ КК «Колледж Ейский»

РАБОЧАЯ ТЕТРАДЬ

по дисциплине  «МАТЕМАТИКА»

к уроку по теме: «Задачи линейного программирования»

студент__  группы №______

отделения ___________________________________


План семинарского занятия:

  1. Историческая справка по теории возникновения линейного программирования
  2. Типы задач линейного программирования:
  1. Задача планирования производства
  2. Задача составления рациона (задача о диете, задача о смесях)
  3. Задача об использовании мощностей (задача о загрузке оборудования)
  4. Задача о раскрое материалов
  5. Транспортная задача
  1. Общая постановка задачи линейного программирования

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

  1. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем -М.: "Финансы и статистика". - 2001. -с. 368
  2. Борисова С.А., Математические методы исследования экономики. – М.; Современный Гуманитарный Университет, 2002г.
  3. Замков О.О. и др. Математические методы в экономике -М.: ДИС. - 1999.
  4. Куликов Ю.Г. и др. Экономико-математические методы и модели - М.: "МПСИ". - 2000.
  5. Минюк С.А. и др. Математические методы и модели в экономике - М.: "ТетраСистемс". - 2002.
  6. Монахов А.В. Математические методы анализа экономики - СПб.: "Питер". - 2001.
  7. Пинегина М.В. Математические методы и модели в экономике - М.: "Экзамен". - 2002.
  8. Федосеев В.В. и др. Экономико-математические методы и прикладные модели - М.: "ЮНИТИ". - 1999.
  9. Филимонова Е.В.Математика. – Ростов-на-Дону; Феникс, 2004г.


  1.  Краткая историческая справка по теории возникновения линейного программирования

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”.

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ.

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”, в которой закладывались основания того, что ныне называется математической экономикой.

Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования. Одновременно с Данцигом, но, не зная его работ, Л.В.Канторович, продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве и тоже разрабатывает метод, позже названный симплекс-методом.

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

Начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и Нобелевской премией в 1975 году.


  1. Типы задач линейного программирования:
  1. Задача планирования производства

Для изготовления двух видов продукции Р1 и Р2 используют четыре вида ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице (цифры условные). Прибыль, получаемая от единицы продукции Р1 и Р2 – соответственно 2 и 3 усл. ден. ед.

вид ресурса

запас ресурса

число единиц ресурсов, затрачиваемых на изготовление единицы продукции

Р1

Р2

S1

18

1

3

S2

16

2

1

S3

5

-

1

S4

21

3

-

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

Математическая модель:

  1. Задача составления рациона (задача о диете, задача о смесях)

Имеются два вида корма I и II, содержащиеся питательные вещества (витамины) S1 S2 и S3. содержание числа единиц питательных веществ в 1 кг. Каждого вида корма и необходимый минимум питательных веществ приведены в таблице (цифры условные). Стоимость 1 кг корма I и II соответственно равна 4 и 6 усл. ден. ед.

питательное вещество (витамин)

необходимый минимум питательных веществ

число единиц ресурсов, затрачиваемых на изготовление единицы продукции

I

II

S1

9

3

1

S2

8

1

2

S3

12

1

6

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

Математическая модель:

  1. Задача об использовании мощностей

(задача о загрузке оборудования)

Предприятию задан план производства продукции по времени и номенклатуре: требуется за время Т выпустить n1, n2,…, nk, единиц продукции Р1, Р2,…, Рk. Продукция производится на станках S1, S2, …,Sm. Для каждого станка известны производительность аij (т.е. число единиц продукции Pj, которое можно произвести на станке Si) и затраты bij на изготовление продукции Pj на станке Si в единицу времени.

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

Математическая модель:

  1. Задача о раскрое материалов

На раскрой (распил, обработку) поступает материал одного образца в количестве а единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональным числам b1, b2, bl  (условия комплектности). Каждая единица материала может быть раскроена n различными способами, причём использование i-го способа (i=1,2,…,n) даёт aik единиц k-го изделия (k=1,2,…,l).

Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.

Математическая модель:

  1. Транспортная задача

Имеется 3 поставщика и 4 потребителя. Мощность поставщиков и спрос потребителей, а так же затраты на перевозку единицы груза для каждой пары «поставщик-потребитель» сведены в таблицу поставок

поставщики

потребители

мощности поставщиков

1

2

3

4

1

1

х11

2

х12

5

х13

3

х14

60

2

1

х21

6

х22

5

х23

2

х24

120

3

6

х31

3

х32

7

х33

4

х34

100

спрос

20

110

40

110

280

В правом верхнем углу произвольной (i,j) клетки стоит так называемый коэффициент затрат – затраты на перевозку единицы груза от i-го поставщика к j-му потребителю.

Найти объёмы перевозок для каждой пары «поставщик – потребитель» так, чтобы :

  1. мощности всех поставщиков были реализованы;
  2. спросы всех потребителей были удовлетворены;
  3. суммарные затраты на перевозку были минимальными.

Математическая модель:


3. Общая постановка задачи линейного программирования.

Рассмотренные выше примеры задач линейного программирования позволяют сформулировать общую задачу линейного программирования.

Математическая модель:

Стандартной задача линейного программирования называется, если:

Канонической задача линейного программирования называется, если:


КОНТРОЛЬНОЕ ЗАДАНИЕ 1

расставьте соответствия

Классы задач

Содержание задач

1.Задачи управления запасами

А) сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а так же моментов замены оборудования модернизированным

2.Задачи ремонта и замены оборудования

Б) посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик

3.Задачи распределения ресурсов

В) состоят в определении оптимальной очередности выполнения операций на различных видах оборудования

4.Задачи сетевого планирования и управления

Г) состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой

5.Задачи массового обслуживания

Д) состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа

6.Задачи планировки и размещения

Е) рассматривают соотношение между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса

7.Задачи составления расписания (календарного планирования)

Ж) встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов

8.Задачи выбора маршрута

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


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

Составление опорного плана:

  1. Метод «Северо-западного угла»

В таблице всегда заполняется левый верхний (северо-западный) угол таблицы, после чего из расчетов выбывает либо строка (так как запас груза полностью исчерпаны), либо столбец (так как полностью удовлетворены потребности)

  1. Метод «Наименьшего элемента»

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

Проверка на оптимальность

Матрица состоит из элементов dij вычисляемых по формуле

Составление цикла перераспределения

(d12; d31; d32)=0 –вершины цикла

Вывод оптимального решения

S вычисляемое по формуле

является оптимальным решением задачи, т.е.

минимальной стоимостью плана перевозок.


ЗАДАНИЕ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

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

с/х

предприятия

молочный комбинат и его филиалы

мощности

потребителей

В1

В2

В3

В4

А1

А2

А3

мощности поставщиков

Молочный комбинат может принять на переработку молоко от сельскохозяйственных предприятий в количестве 240 ц., его филиалы 80 ц.. л и 120 ц. В крае производством молока занимаются сельхозпредприятия мощность которых составляет соответственно 144, 106, 56, 134 ц. Стоимости перевозки молока заданы таблицей:

3

7

5

6

7

3

8

2

7

11

8

6

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


Заполните таблицу, опираясь на конспект

ГЛОССАРИЙ

п/п

Новые понятия

Содержание

1

Л.В. Канторович

2

Задача линейного программирования

3

Математическая модель задачи

4

Допустимое базисное решение

5

Оптимальное решение

6

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

7

Задача об использовании ресурсов (задача планирования производства)

8

Задача об использовании мощностей (задача о загрузке оборудования)

9

Задача составления рациона (задача о диете, задача о смесях)

10

Задача о раскрое материалов

11

Транспортная задача

12

Метод «северо-западного угла»

13

Открытая модель транспортной задачи

14

Общая задача линейного программирования


РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

  1. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем -М.: "Финансы и статистика". - 2001. -с. 368
  2. Борисова С.А., Математические методы исследования экономики. – М.; Современный Гуманитарный Университет, 2002г.
  3. Замков О.О. и др. Математические методы в экономике -М.: ДИС. - 1999.
  4. Куликов Ю.Г. и др. Экономико-математические методы и модели - М.: "МПСИ". - 2000.
  5. Минюк С.А. и др. Математические методы и модели в экономике - М.: "ТетраСистемс". - 2002.
  6. Монахов А.В. Математические методы анализа экономики - СПб.: "Питер". - 2001.
  7. Пинегина М.В. Математические методы и модели в экономике - М.: "Экзамен". - 2002.
  8. Федосеев В.В. и др. Экономико-математические методы и прикладные модели - М.: "ЮНИТИ". - 1999.
  9. Филимонова Е.В.Математика. – Ростов-на-Дону; Феникс, 2004г.

Ресурсы 

http://www.cs.msiu.ru/projects/kurs/1999/9311/AI_CURSOVIK/gorj-va/kurs.html

http://imcs.dvgu.ru/lib/nurmi/linpro/buka/node7.html

http://www.dvgu.ru/pin/imcs/lib/nurmi/linpro/zads/transport.html

http://www.de.nwpi.ru/courses/man/theory/go_transport.htm

http://www.dvo.ru/studio/linpro/buka/node3.html

http://www.math.dcn-asu.ru/rus/stud/oper/zadach/trans_1.htm

http://mathematics.superreferat.ru/view/detail6008.html

http://ega-math.narod.ru/Quant/Reitman.htm

http://unicyb.kiev.ua/~sharapov/Ukr/UG/TZ/trzd.html

http://ecomadelling.superreferat.ru/view/detail14875.html

http://fmi.asf.ru/vavilov/Gloss.htm

http://www.krgtu.ru/WD/TUTOR/lp/lp05.html

http://www.tsure.ru/University/Faculties/Femp/KGIMU/ucheba/Literature/Rur/rur.htm

http://www.ngasu.nsk.su/prikl/mat_prog.html

http://programming.superreferat.ru/view/detail17658.html

http://builder.ngasu.nsk.su/prikl/study.html

http://netsun.ru/alex/education/oio-toc-2.shtml

http://www.matlab.ru/optimiz/book1/3_2.asp

http://eup.kulichki.net/pages/R06/Referats/2002-05-25/B2E2.htm

http://transport.superreferat.ru/view/detail14211.html

http://www.univer.omsk.su/pages/econometrics/excel/lesson2.htm

http://www.citforum.dgrad.ru/book/putprogr/putprogr_cc.shtml

 


По теме: методические разработки, презентации и конспекты

Конспект урока математики на тему: «Задачи на нахождение суммы и остатка».

Урок математики для 9 класса коррекционной школы VIII вида...

Рабочие тетради к уроку по литературе "Тема Родины в лирике С. Есенина"

В содержании "Рабочих тетрадей" освещается теоретический материал урока, анализ стихотворения "Гой ты, Русь, моя родная..." и вариативные задания для самостоятельной работы....

Конспект урока математики о теме: "Задачи на проценты" для 7 класса

Конспект разработан для урока систематизации знаний по теме: "Задачи на проценты". После урока предусмотренна домашняя работа в виде исследования....

Урок математики по теме: "Задачи на части" для 5 класса (ФГОС)

Цели урока как планируемые результаты обучения, планируемый уровень достижения целей:Вид планируемых учебных действийУчебные действияПланируемый уровень достижения результатов обученияПредметные...

КОНСПЕКТ урока математики по теме: «Задачи на совместную работу»

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

Конспект урока математики по теме: "Задачи на проценты" 6 класс

Конспект урока математики по теме: "Задачи на проценты"...

Рабочая тетрадь к уроку ОРКСЭ по теме "Милосердие"

Рабочая тетрадь к уроку ОРКСЭ по теме "Милосердие"...