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

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

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

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

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

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

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

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

отделения ___________________________________

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

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

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

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

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

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 году.

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

1. Задача планирования производства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ГЛОССАРИЙ

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

10. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем -М.: "Финансы и статистика". - 2001. -с. 368
11. Борисова С.А., Математические методы исследования экономики. – М.; Современный Гуманитарный Университет, 2002г.
12. Замков О.О. и др. Математические методы в экономике -М.: ДИС. - 1999.
13. Куликов Ю.Г. и др. Экономико-математические методы и модели - М.: "МПСИ". - 2000.
14. Минюк С.А. и др. Математические методы и модели в экономике - М.: "ТетраСистемс". - 2002.
15. Монахов А.В. Математические методы анализа экономики - СПб.: "Питер". - 2001.
16. Пинегина М.В. Математические методы и модели в экономике - М.: "Экзамен". - 2002.
17. Федосеев В.В. и др. Экономико-математические методы и прикладные модели - М.: "ЮНИТИ". - 1999.
18. Филимонова Е.В.Математика. – Ростов-на-Дону; Феникс, 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