Элементы математических методов и моделей

Размещено на http://www.allbest.ru/

Содержание

Введение

Введение в линейное программирование

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

Двойственность линейного программирования

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

Задания для самостоятельной работы

Литература



Введение

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

Современная экономическая теория как на макро-, так и на микроуровне включает в себя в качестве необходимого элемента математические методы и модели. Использование математики в экономике позволяет, во-первых, выделить и формально описать наиболее важные и существенные связи экономических переменных и объектов. Во-вторых, из четко сформулированных исходных данных и соотношений методами дедукции можно получать выводы, адекватные изучаемому объекту в той же мере, что и сделанные предпосылки. В-третьих, использование языка математики позволяет точно и компактно излагать положения экономической теории, формулировать ее понятия и выводы.

Как выработать наилучшее решение в сложной экономической ситуации, рассчитать возможную прибыль и убытки, найти, какие условия кредита сегодня самые выгодные, определить, сколько будут стоить через год-два деньги? Ответы на эти вопросы можно найти на стыке экономики и математики с помощью особых приемов, называемых «экономико-математическое моделирование».



Введение в линейное программирование

Справочный материал.

1. Общая задача линейного программирования формулируется следующим образом:

Найти набор (наборы) действительных чисел , доставляющий экстремум (максимум или минимум) линейной целевой функции

и удовлетворяющий системе ограничений

(*)

Условия (*) означает неотрицательность k компонент вектора X. Запись означает неотрицательность всех компонент X, т.е. или .

2. Допустимым решением (планом) задачи линейного программирования называется n-мерный вектор , удовлетворяющий системе ограничений и условиям неотрицательности. Множество всех допустимых решений задачи образуют область допустимых решений (ОДР).

3. Решение (план) называется оптимальным, если оно допустимое и доставляет экстремум целевой функции.

4. Задача линейного программирования называется канонической, если ограничения задачи состоят из системы уравнений и условий неотрицательности всех n переменных. Каноническая задача записывается в виде

,

(Условие будем записывать иногда так: .)

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

a) Неравенство Равносильно равенству и простейшему неравенству .

b) Неравенство Равносильно равенству и простейшему неравенству .

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

c) Каждую переменную, на которую не наложено условие неотрицательности, можно представить в виде разности двух неотрицательных переменных:

При необходимости можно использовать следующие равносильные соотношения:



,

.

6. Для составления модели задачи линейного программирования, заданной в текстовой форме, необходимо:

1) ввести обозначения для неизвестных задачи;

2) проанализировать и зафиксировать ограничения для них (например, неотрицательность);

3) составить систему ограничений задачи;

4) составить целевую функцию и установить вид экстремума.

Вопросы

1. Может ли система ограничений общей задачи ЛП включать строгие неравенства?

2. Может ли целевая функция задачи ЛП содержать нелинейные выражения из переменных?

3. Может ли допустимое решение задачи ЛП содержать отрицательную компоненту?

4. Чем отличается оптимальное решение задачи ЛП от допустимого?

5. Чем отличается канонический вид задачи ЛП от общего?

6. Являются ли следующие задачи задачами линейного программирования? Ответ обосновать.

1)

2)

3)

7. В чем состоит схема построения математической модели задачи с экономическим содержанием?

8. В чем состоит смысл неотрицательности переменных задачи ЛП?

9. Есть ли какая-либо связь между числом переменных и числом ограничений задачи с экономическим содержанием?

10. В чем состоит экономический смысл: а) целевой функции? б) системы ограничений?

Содержание занятий.

Следующие задачи (1-4) привести к каноническому виду.

1.

2.

3.

4.

5. Магазин планирует реализовать четыре вида товаров Т1 ,Т2 , Т3 , Т4. Известны затраты на реализацию единицы товара, оплата продавцов, ограничения на торговые площади и складские помещения, а также прибыль от реализации единицы того или иного товара. Требуется определить плановый объем и структуру товарооборота, при котором прибыль магазина оказалась бы максимальной. Цифровые данные приведены в таблице.

Виды ресурсов	Стоимость единицы товара	Суммарный объём
	Т1	Т2	Т3	Т4
Рабочее время продавцов (человеко-дни)	2	5	3	6	50
Торговая площадь (м2)	6	2	9	8	200
Складские помещения (м2)	4	8	6	5	40
Прибыль (руб.)	6	7	9	3	max

6. (задача о рационе питания). Животные должны получать ежедневно определенный набор из m питательных веществ в количествах не менее соответственно b1, b2, b3,…bm единиц. Животные питаются кормами n видов K1, K2, K3,…Kn. Известно количество aij питательного вещества с номером i (i = 1, 2,..., m) в единице корма Kj (j = 1, 2,..., n), а также стоимость cij (j = 1, 2,..., n) единицы корма Kj. Необходимо составить суточный рацион кормления животных при минимальных затратах на покупку кормов.

7. Для изготовления изделий А, В и С в качестве сырья используется сталь, алюминий и цветные металлы, объемы которых ограничены. Изделия производятся на токарных, фрезерных и шлифовальных станках. Требуется составить план выпуска продукции, при котором будет достигнута максимальная прибыль от реализации всей продукции. Составить математическую модель задачи при данных, приведенных в таблице.



Вид ресурса	Объем ресурса	Норма расхода на единицу ресурса
		А	В	С
Сталь (кг)	800	15	20	40
Алюминий (кг)	600	8	15	10
Цветные металлы (кг)	300	3	6	4
Станко-токарные (ч)	4800	60	80	120
Станко-фрезерные (ч)	5600	80	70	28
Станко-шлифовальные (ч)	600	6	10	12
Прибыль (ден. ед.)	30	40	60

8. Предприятие для выпуска данной продукции применяет три технологии (способа производства) и использует три вида ресурсов. Известно: bi ед. (i = 1,2,3) - запасы ресурсов; aij ед./ч (i = 1,2,3; j = 1,2,3) - затраты i-ro вида ресурса на 1 ч работы с использованием j-й технологии; cj руб./ч (j = 1,2,3) - прибыль предприятия от реализации продукции, выпускаемой за 1 ч работы с использованием j-й технологии; Т (ч) -- общее время работы предприятия по всем технологиям.

9. Требуется найти время работы предприятия, необходимое по каждой технологии, чтобы обеспечить максимальную прибыль от реализации выпускаемой продукции. Составить математическую модель задачи при Т= 300 ч по исходным данным, приведенным в таблице.

Вид ресурса	Запасы ресурса bj	Затраты работы aij за 1 ч работы по технологии
		№1	№2	№3
1	800	8	5	10
2	1800	12	10	9
3	1100	12	11	5
Прибыль cj (руб./ч)	600	800	750

10. При откорме каждое животное должно получать не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице:



Питательные вещества	Количество единиц питательных веществ на 1 кг
	Корм 1	Корм 2
Белки	3	1
Углеводы	1	2
Протеин	1	6

Стоимость 1 кг корма первого вида - 4 д.е., второго - 6 д.е.

Составьте дневной рацион питательности, имеющий минимальную стоимость.

11. Хозяйство располагает следующими ресурсами: площадь - 100 ед., труд - 120 ед., тяга - 80 ед. Хозяйство производит четыре вида продукции П1, П2, П3, П4. Организация производства характеризуется следующей таблицей:

Продукция	Затраты на 1 ед. продукции	Доход от единицы продукции
	Площадь	Труд	тяга
П1	2	2	2	1
П2	3	1	3	4
П3	4	2	1	3
П4	5	4	1	5

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

12. Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа - 3 т, проволоки - 18 т. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д. е., второго - 4 д. е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль.

13. Совхоз отвел три земельных массива размером 5000, 8000, 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей таблице:

Посевы	Массивы
	I	II	III
Рожь	15	14	15
Пшеница	14	14	22
Кукуруза	30	35	25

За 1 ц. ржи совхоз получает 2 д. е., за 1 ц. пшеницы - 2,8 д. е., за 1 ц. кукурузы - 1,4 д. е.

Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1900 т ржи, 158 000 т пшеницы и 30 000 т кукурузы?

14. Три типа самолетов следует распределить между четырьмя авиалиниями. Данные об организации процесса перевозок приведены в следующей таблице:

Тип самолёта	Число самолётов	Месячный объём перевозок одним самолётом по авиалинии, ед.	Эксплуатационные расходы на один самолёт по авиалинии, д.е.
		I	II	III	IV	I	II	III	IV
1	50	15	10	20	50	15	20	25	40
2	20	20	25	10	10	70	28	15	45
3	30	35	50	30	45	40	70	50	65

Распределите самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных затратах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000, 500 ед. груза.



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

Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными.

Справочный материал.

1. Уравнение вида при произвольных коэффициентах (и не равны нулю одновременно) определяет некоторую прямую в прямоугольной системе координат.

Уравнение вида - общее уравнение прямой.

2. Множество решение неравенства с двумя переменными

Является одной из двух полуплоскостей, на которые вся плоскость делится прямой , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравенства .

3. Множество решений совместной системы m линейных неравенств с двумя переменными

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

4. Решением каждого неравенства системы ограничений задачи ЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений или областью определения. Координаты любой точки, принадлежащей области определения являются допустимым решением задачи.

5. Алгоритм графического метода решения задач ЛП:

1) Строится многоугольная область допустимых решений задачи ЛП - ОДР.

2) Строится вектор-градиент целевой функции .

3) Строится линия уровня (а-постоянная величина) - прямая, перпендикулярная вектору-градиенту .

4) Линия уровня передвигается в направлении вектора в случае максимизации (при минимизации функции линия уровня перемещается в направлении, противоположном вектору-градиенту) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума . Для нахождения ее координат достаточно решить систему двух уравнений прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение найденное в получаемой точке, является максимальным. Если линия уровня при своем движении не покидает ОДР, то соответствующий максимум или минимум не существует.

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

Вопросы

1. Какое максимальное число неравенств может содержать задача ЛП с двумя переменными?

2. Как строится ОДР задача ЛП с двумя переменными?

3. Может ли ОДР быть невыпуклым многоугольником?

4. Может ли ОДР быть открытым множеством? пустым?

5. Может ли линия уровня целевой функции быть параллельной вектору целевой функции?

6. Может ли задача ЛП с двумя переменными иметь два и только два оптимальных решения?

7. В каком случае задача ЛП с двумя переменными не имеет решения?

8. Каков геометрический смысл коэффициентов при неравен-

9. неравенствах в системе ограничений? Каков смысл коэффициентов целевой функции?

10. Какой вывод можно делать из того, что ОДР не ограничена по направлению, противоположному вектору целевой функции?

11. Сколько переменных может содержать задача линейного программирования, которую можно решить графически?

12. Можно ли решить графически задачу линейного программирования, если на некоторые ее переменные не наложены условия неотрицательности?

Содержание занятия.

1. Построить множество решений неравенства:

a)	b)

2. Построить множество решений системы неравенств:

a)	b)



3. Задача о костюмах.

Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского - 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

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

Введем следующие обозначения: - число женских костюмов; - число мужских костюмов.

Прибыль от реализации женских костюмов составляет , а от реализации мужских , т.е. необходимо максимизировать целевую функцию

Ограничения задачи имеют вид:

1) Первое ограничение по труду

.



Прямая (1) проходит через точки (150, 0) и (0, 150).

Контрольная точка (0;0) - верное неравенство.

2) Второе ограничение по лавсану

Прямая (2) проходит через точки (120, 0) и (0, 480).

Контрольная точка (0;0) - верное неравенство.

3) Третье ограничение по шерсти

Прямая (3) проходит через точки (0;100) и (350;0).

Контрольная точка (0;0) - верное неравенство.

4) Четвертое ограничение по количеству мужских костюмов

Прямая (4) - горизонтальная прямая, проходит через точку (0;60).

Контрольная точка (0;0) - неверное неравенство.

5)

Прямая - ось Ox1.

6)

Прямая - ось Ox2.

Область допустимых решений задачи ЛП многоугольник ABCD (рис 1).

Для определения направления движения к оп-тимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е. .

Что бы построить этот вектор, нужно соединить точку (10;20) с началом координат. При макси-мизации целевой функции необходимо двигаться в направ-лении вектора-градиента.



Размещено на http://www.allbest.ru/

Рис 1.

В нашем случае движение линии уровня будем осущест-влять до ее выхода из области допустимых решений. в крайней, угловой точке C достигается максимум целевой функции. Тоска C - точка пересечения двух прямых(1) и (3). Для нахождения координат этой точки достаточно решить систему двух уравнений прямых, получаемых из соответствующих ограничений.

Решая систему, получим координаты точки C(70,80), в которой и будет оптимальное решение, т.е.

Таким образом, чтобы получить максимальную прибыль в 2300 руб., предприятие должно выпускать 70 женских и 80 мужских костюмов.

4. Для изготовления двух видов продукции А1 и А2 используют три вида ресурсов S1, S2, S3, запасы которых составляют 18,16 и 5 усл.ед. Расход ресурсов на 1 ед. продукции приведен в таблице:

Вид ресурса	Запасы ресурсов	Расходы ресурсов на 1 изделие
		A1	A2
S1	18	1	3
S2	16	2	1
S3	5	-	1
Прибыль	2 руб.	3 руб.

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

5. В рационе животных используется два вида корма. Животные должны получать четыре вида питательных веществ. Составить рацион питания животных, обеспечивающий минимальные затраты, при исходных данных, заданных таблицей.

Необходимое количество питательных веществ	Норма (ед. массы)	Содержание питательных веществ в единице корма
		Корм 1	Корм 2
Пит. вещ. №1	20	1	5
Пит. вещ. №2	24	3	2
Пит. вещ. №3	32	2	4
Пит. вещ. №4	2	1	0
Стоимость единице корма (ден. ед.)	4	6



6. Для изготовления изделий двух типов А и Б имеется 200 кг металла. На изготовление одного изделия типа А расходуется 2 кг металла, а одного изделия типа Б -- 4 кг. Составить план производства, обеспечивающий получение наибольшей выручки от продажи изготовленных изделий, если одно изделие типа А стоит 50 руб., а одно изделие типа Б стоит 70 руб., причем изделий типа А можно изготовить не более 60, и изделий типа Б -- не более 30.

7. Из пункта А в пункт Б ежедневно отправляются пассажирские и скорые поезда. В таблице указаны наличный парк вагонов разных типов, из которых ежедневно можно комплектовать данные поезда, и количество пассажиров, вмещающихся в каждом из вагонов

Поезда	Количество вагонов в поезде
	Багаж.	Почтов.	Плацк.	Купейн.	Мягкий
Скорый	1	1	5	6	3
Пассажирский	1	-	8	4	1
Число пассажиров	-	-	58	40	32
Парк вагонов	12	8	81	70	26

а) Определить оптимальные количества скорых и пассажирских поездов, при которых число перевозимых пассажиров достигает максимума.

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

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

Справочный материал.

1. Симплексный метод применяется при решении задач линейного программирования, заданных в канонической форме. Симплексный метод основан на том факте, что целевая функция достигает экстремума на допустимом базисном решении. Таким образом, дело сводится к перебору базисных допустимых решений системы ограничений-равенств задачи. Симплексный метод позволяет переходить от одного допустимого базисного решения к другому так, чтобы значение целевой функции уменьшалось (увеличивалось) в задаче на минимум (максимум).

2. Симплексный метод состоит из трех основных элементов:

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

2) правила перехода к лучшему решению;

3) проверки оптимальности допустимого решения.

3. Алгоритм симплекс-метода:

Для определённости считаем, что решается задача на отыскание максимума, если необходимо отыскать минимум F, то решается задача максимизации функции -F, и это решение принимается за решение исходной задачи.

1) После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены.

2) Для нахождения первоначального базисного решения разобьем переменные на две группы: основные (базисные) и неосновные (свободные). В качестве основных переменных на первом шаге следует выбрать (если это возможно) такие m переменных, каждая из которых входит только в одно из m уравнений системы ограничений. При этом нет таких уравнений системы, в которые не входит ни одна из этих переменных.

базисные неизвестные -

свободные неизвестные -

3) По расширенной системе строим симплекс-таблицу

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
				…			…
				…		1	…	0
…	…	…	…	…	…	…	…	…
				…		0	…	1
F	0			…		0	0	0

4) Проверяем критерий оптимальности при решении задач на максимум. Если в последней строке F симплекс-таблице нет отрицательных коэффициентов, то решение оптимально. Максимальное значение функции равно свободному члену в строке целевой функции (строке F), а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю.

5) Если критерий оптимальности не выполнен, то в последней строке симплекс-таблицы находим наименьший отрицательный элемент, не считая свободного члена. Столбец, соответствующий этому элементу, считается разрешающим. Если имеется несколько одинаковых наименьших элементов, то выбираем любой из них.

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

Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

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

8) После нахождения разрешающего элемента переходим к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняем местами. При этом базисная переменная становится свободной переменной, и наоборот. Симплекс-таблицу преобразуем следующим образом:

§ Все элементы разрешающей строки делим на разрешающий элемент. Полученную строку обозначаем *.

§ Вычисление элементов остальных строк, включая F-строку.

Новая строка = текущая строка её коэффициент в разрешающем столбце строку *

9) См. п 4.

Вопросы.

1. Какую роль играет в симплексном методе разрешающий (ведущий) элемент?

2. При каких условиях допустимое базисное решение является оптимальным?

3. В чем состоит симплексный метод решения задач ЛП?

4. Каким образом следует выбирать разрешающий столбец при переходе от одного к другому базису?

5. Каким образом следует выбирать разрешающую строку?

6. Какие последствия влечет отрицательность коэффициентов разрешающего столбца?

7. Можно ли симплексным методом решить задачу линейного программирования, если на некоторые ее переменные не наложены условия неотрицательности?

Содержание занятий.

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

1.

3.

Решение:

Расширенная система задачи имеет вид:

Базисные неизвестные --

Свободные неизвестные --

Заполняем первую симплекс-таблицу

Проверяем критерий оптимальности. В последней строке имеется отрицательные коэффициенты. Выбираем из наименьший (-3); второй столбец разрешающий, переменная перейдет в базисные переменные.

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

Таблица №1

	Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
№1		18	1	3	1	0	0	0
№2		16	2	1	0	1	0	0	16
№3		5	0	1	0	0	1	0	5
№4		21	3	0	0	0	0	1	-
№5	F	0	-2	-3	0	0	0	0



Строим таблицу №2

Новые базисные неизвестные --

Свободные неизвестные --

Коэффициенты таблицы №2 вычисляем следующим образом:

Новая строка №3 = строка №3/1 -- обозначим результат *

Новая строка №1 = строка №1 - 3Чстрока *,

Новая строка №2 = строка №2 - 1Чстрока *,

Новая строка №4 = строка №4 - 0Чстрока *,

Новая строка №5 = строка №5 - (-3)Чстрока *,

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

Таблица №2

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
	3	1	0	1	0	-3	0	3
	11	2	0	0	1	-1	0
	5	0	1	0	0	1	0	-
	21	3	0	0	0	0	1	7
F	15	-2	0	0	0	3	0

Критерий оптимальности в таблице №2 снова не выполнен.

Таблица №3

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
	3	1	0	1	0	-3	0	-
	5	0	0	-2	1	5	0
	5	0	1	0	0	1	0	5
	12	0	0	-3	0	9	1
F	21	0	0	2	0	-3	0



Таблица №4

Базисные неизвестные	Свободный член	Неизвестные	Оценочное отношение
	6	1	0			0	0
	1	0	0			1	0
	4	0	1			0	0
	3	0	0			0	1
F	24	0	0			0	0

Критерий оптимальности таблицы №4 выполнен, значит

4.

5.

6.

7.

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

Вид ресурса	Вид товара	Объём ресурса
	1	2	3	4
Сырьё (кг)	3	5	2	4	60
Рабочая сила (ч)	22	14	18	30	400
Оборудование (станко-часы)	10	14	8	16	130
Прибыль на ед. товара (ден. ед.)	30	24	56	48	max

По этим исходным данным решить следующие задачи:

а) выяснить, какой ассортимент товара надо выпускать, чтобы прибыль была максимальной;

б) определить оптимальный ассортимент при дополнительном условии: первого товара выпустить не более 7 ед., второго -- не менее 8 ед., а третьего и четвертого -- в отношении 1:2.

9. Для изготовления изделий № 1 и № 2 имеется 180 кг металла. На изготовление одного изделия № 1 расходуется 2 кг металла, а изделия № 2 - 3 кг. Составить план производства, обеспечивающий получение наибольшей выручки от продажи изделий, если отпускная цена одного изделия № 1 равна 13 руб., а изделия № 2 -- 17 руб., причем изделий № 1 требуется изготовить не более 60, а изделий № 2 -- не более 40.

10. Для изготовления трех видов продукции П1, П2, П3 используются три вида сырья S1, S2, S3, запасы которых указаны в таблице. Известны количества единиц сырья S1, S2, S3, необходимые для производства единиц продукции П1, П2, П3 соответственно, и стоимость реализации каждой единицы готовой продукции.



Вид сырья	Запасы (ед. объёма)	Вид продукции
		П1	П2	П3
S1	2106	3	3	9
S2	2340	10	9	15
S3	650	5	5	1
Стоимость продукции (ден. ед.)	80	60	50

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

Двойственность линейного программирования

Справочный материал.

1. Задача I и II называются симметричными взаимно двойственными задачами

Задача I	Задача II

2. Особенности пары взаимно двойственных задач.

1) В одной задаче ищут максимум линейной функции, в другой - минимум.

2) Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.

3) Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида "", а в задаче минимизации - все неравенства вида "".

4) Матрицы коэффициентов при переменных, в системах ограничений обеих задач являются транспонированными друг к другу:

5) Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6) Условия неотрицательности переменных имеются в обеих задачах.

3. Алгоритм составления двойственной задачи.

1) Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду "", а если минимум - к виду "". Для этого неравенства, в которых данное требование не выполняется, умножить на -1.

2) Составить расширенную матрицу системы , в которую включить матрицу коэффициентов при переменных , столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3) Найти матрицу , транспонированную к матрице .

4) Сформулировать двойственную задачу на основании полученной матрицы и условия неотрицательности переменных:

· Если в системе ограничений основной задачи имеется равенство (уравнение), то та переменная , которая соответствует этому i-му ограничению-равенству, может быть произвольного знака. Запишем это соответствие так:

· Если на некоторую переменную основной задачи не наложено условие неотрицательности, то соответствующее ей ограничение двойственной задачи является равенством:



4. Для основной задачи линейного программирования и двойственной к ней задачи справедливы следующие теоремы.

Теорема 1. Если одна из пары двойственных задач линейного программирования имеет решение, то и другая задача имеет решение, и при этом значения целевых функций этих задач равны:

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

Теорема 3. Если целевая функция одной из пары двойственных задач неограничена снизу (сверху), то система ограничений другой задачи этой пары несовместна.

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

5. Существует соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи

Переменные исходной задачи I
Первоначальные	Дополнительные
Дополнительные	Первоначальные
Переменные исходной задачи II



6. Метод, при котором вначале симплексным методом решается двойственная задача, а затем оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплексным методом. Этот метод бывает выгодно применять, когда первое базисное решение исходной задачи недопустимое или, например, когда число ее ограничений m больше числа переменных n.

Вопросы

1. Можно ли для задачи ЛП, содержащей в системе ограничений неравенства разных направлений, построить двойственную задачу?

2. Если в основной задаче отсутствуют условия неотрицательности переменных, то какие последствия это влечет в сопряженной задаче?

3. Чем отличаются матрицы систем ограничений в паре двойственных задач?

4. Какова связь между экстремальными значениями пары двойственных задач ЛП?

5. Что можно сказать о решении двойственной задачи, если решение основной задачи не существует по причине несовместимости ее системы ограничений?

6. Могут ли обе двойственные задачи быть задачами на максимум?

Содержание занятий

Построить двойственные задачи (1-4).

1.

2.

3.

4.

Для каждой из следующих задач составить двойственную и, решая одну из них, найти решение обеих задач (5-12).

5.

6.

7.

8.

9.

10. Производственная мощность сборочного цеха составляет 60 изделий типа А и 180 изделий типа Б в сутки. Технический контроль пропускает в сутки 100 изделий того или другого типа (безразлично). Изделия типа А вчетверо дороже изделий типа Б. Требуется спланировать выпуск готовой продукции так, чтобы предприятию была обеспечена наибольшая прибыль.

11. Для изготовления изделий двух видов склад может отпустить металла не более 150 кг, причем на изделие 1-го вида расходуется 5 кг, а на изделие 2-го вида -- 3 кг металла. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий 1-го вида требуется изготовить не более 20 штук, а изделий 2-го вида -- не более 25 штук, причем одно изделие 1-го вида стоит 7 руб., а 2-го вида -- 8 руб.

12. Для откорма животных употребляют два вида кормов. Стоимость 1 кг корма 1-го вида -- 20 руб., а корма 2-го вида -- 25 руб. В каждом килограмме корма 1-го вида содержится 5 единиц питательного вещества А и 4 единицы питательного вещества Б, а в каждом килограмме корма 2-го вида -- соответственно 3 и 12 единиц. Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты на откорм были минимальными, если суточный рацион предусматривает не менее 150 единиц питательного вещества типа А и не менее 180 единиц питательного вещества типа Б?

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

Справочный материал.

1. Имеются m пунктов отправления однородного груза и n пунктов назначения того же груза . Предполагается, что из любого пункта груз может быть доставлен в любой пункт Обозначения:

-- объем (запас) груза в пункте .

-- объем груза, необходимого в пункте .

-- стоимость (тариф) перевозки единицы груза из . в .

Требуется определить план перевозок груза из пунктов из . в .так, чтобы:

1) вывезти весь груз от отправителей .

2) удовлетворить потребность в грузе (спрос) каждого потребителя

3) транспортные расходы были минимальными.

Под планом задачи подразумевается матрица

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

2. Для разрешимости транспортной задачи необходимо и достаточно, чтобы имело место условие баланса



В этом случае транспортная задача называется закрытой.

Если условие баланса нарушено, то транспортная задача называется открытой.

3. Если задача с неправильным балансом (открытая), то:

При (спрос меньше предложения) необходимо ввести «фиктивного» потребителя груза: .

При (спрос больше предложения) необходимо ввести «фиктивного» поставщика груза: .

Стоимости перевозок от «фиктивного» поставщика до всех потребителей и от любого поставщика до «фиктивного» потребителя принимаются равными нулю.

4. Неотрицательная матрица X, удовлетворяющая условиям задачи называется планом (или допустимым планом) задачи. Допустимый план называется оптимальным, если он доставляет минимум целевой функции. Допустимый план, имеющий не более отличных от нуля компонентов , называется базисным, или опорным. Опорный план, имеющий ровно отличных от нуля компонент, называется невырожденным, а если число отличных от нуля компонент меньше, чем , то план называется вырожденным.

5. Алгоритм решения транспортной задачи (для закрытой транспортной задачи):

1) Строим начальный опорный план. Одним из возможных методов нахождения первоначального опорного плана является

метод "северо-западного "угла,

метод минимальных тарифов.

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

Запас Спрос			…
			…
				…
				…
…	…	…	…	…	…
				…

2) Проверяем опорный план на оптимальность методом потенциалов.

· Находим потенциалы строк и потенциалы столбцов по формуле:

для занятых клеток. - тариф.

Количество потенциалов -- , а количество занятых клеток равно . Т.е. однозначно потенциалы не находятся. Обычно полагают, что , тогда остальные потенциалы вычисляются однозначно.

· Находим оценки свободных клеток. .

Критерий оптимальности

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

Если хотя бы одна из оценок , то опорный план допускает улучшения.

3) Среди свободных клеток с отрицательными оценками находим клетку с наименьшей оценкой и обозначаем ее .

4) Строим означенный цикл с начальной вершиной в этой клетке.

Циклом с начальной вершиной в данной клетке называется замкнутая ломаная, обладающая следующими свойствами:

· все ее вершины, кроме начальной, расположены в занятых клетках;

· звенья (стороны) цикла расположены в строках и столбцах таблицы;

· в каждой вершине звенья соединяются под прямым углом;

· на звеньях цикла могут быть занятые клетки, но они не являются вершинами цикла;

· два звена могут пересекаться в какой-либо клетке, но эта клетка не должна быть занятой (иначе она является вершиной).

Цикл называется означенным, если в его вершинах расставлены знаки "+" и "-" так, что в свободной клетке стоит знак "+", а соседние вершины имеют противоположные знаки.

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

5) Выбираем минимальную поставку среди поставок в клетках со знаком "-". Найденная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком "+" увеличивается на , а в клетках со знаком "-" уменьшается на . Клетка с выбранной поставкой , после перераспределения поставок по циклу считаться свободной остальные клетки цикла -- заполненными. Таким образом, получен новоый опорный план.

6) См. п.2 алгоритма.

Вопросы

1. Чем отличаются друг от друга транспортные задачи с правильным и с неправильным балансом?

2. В чем состоит метод наименьших тарифов построения начального решения (плана)?

3. Чем отличается вырожденное решение от невырожденного? Когда появляется то или другое?

4. Можно ли проверять на оптимальность вырожденное решение?

5. Каким образом получить невырожденное опорное решение?

6. Как строится цикл? В чем состоит его математический смысл?

7. Как проверить на оптимальность полученное опорное решение?

8. Как улучшить неоптимальное решение транспортной задачи?

9. Может ли транспортная задача иметь два решения? бесконечно много решений?

10. Каким образом решить открытую транспортную задачу?

Содержание занятий

Решить транспортные задачи, заданные таблицами (1-6)

	40	60	80	60
60	1	3	4	2
80	4	5	8	3
100	2	3	6	1

	150	140	190
200	3	7	2
150	9	2	1
130	1	5	7
170	6	4	8

	100	70	35	45	50
54	12	14	26	16	3
32	8	11	11	22	10
85	6	10	10	21	15
162	10	4	4	8	9

	20	10	60	30	70
60	18	2	8	3	2
36	8	2	3	12	4
90	4	3	5	7	14
84	9	4	16	5	8



	125	75	200	380	220
222	20	18	11	8	3
188	10	10	5	2	4
210	2	17	8	4	3
300	3	9	17	8	4

	100	130	150	60	60
180	3	8	5	6	7
160	5	3	6	8	7
120	6	5	7	3	4
40	12	9	10	8	12

1. На четырех складах А, В, С, D находится соответственно 32, 30, 18, 20 т горючего, а в пунктах 1, 2, 3, 4, 5, 6 потребляют это горючее в количествах 9, 10, 14, 20, 21, 26 т соответственно. Перевозка 1 т горючего со складов А, В, С, D в пункты 1, 2, 3, 4, 5, 6 задается тарифной матрицей

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

2. В резерве трех железнодорожных станций А, В, С находятся соответственно 90, 40, 30 вагонов. Составить оптимальный план перегона части этих вагонов к четырем пунктам погрузки хлеба, если пункту № 1 необходимо 60 вагонов, №2 -- 40 вагонов, №3 -- 30 вагонов, №4 -- 20 вагонов. Стоимости перегонов одного вагона со станции А в указанные пункты соответственно равны 200, 300, 100, 400 руб.; со станции В - 400, 300, 300, 200 руб. и со станции С - 200, 300, 100, 400 руб. В ответе указать стоимость перегона вагонов.

3. На четырех складах находится сортовое зерно, соответственно 30, 20, 10, 10 т, которое надо доставить в шесть пунктов: пункту №1 - 20 т, №2 - 10 т, №3 - 10 т, №4 - 10 т, №5 - 10 т, №6 - 10 т. Стоимость доставки одной тонны зерна с данных складов в указанные пункты задается тарифной матрицей

Составить план перевозок зерна со складов во все шесть пунктов, минимизирующий стоимость перевозок, и указать эту стоимость.

4. На четырех базах имеется товар в количествах соответственно 72, 72, 68, 60 единиц. Пять магазинов могут реализовать ежедневно соответственно 30, 10, 80, 40, 100 единиц. Стоимость перевозки одной единицы товара от каждой базы до всех магазинов задается матрицей

Указать оптимальный план перевозок товаров от баз в магазины, который минимизировал бы транспортные расходы, и указать эти расходы.

Задания для самостоятельной работы

Содержание заданий:

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

б) для каждой из данных задач составить двойственную и решить обе задачи симплексным методом (2-3);

в) найти оптимальный план транспортной задачи с правильным или неправильным балансом (4-5).

Вариант 1

1.

2.

3.

	90	100	150	200	250
250	4	8	10	14	15
150	7	11	9	12	13
100	6	3	2	1	4
290	1	4	7	9	3

	25	25	25	15	30
30	4	6	3	4	1
30	3	5	2	5	3
40	2	4	1	6	2
50	3	2	1	4	3

Вариант 2 

1.

2.

3.

	100	140	260	90	210	200
180	2	6	4	12	7	11
200	3	5	6	9	3	10
300	9	7	3	2	5	2
320	4	8	5	5	2	9

	20	20	20	35	15
25	3	3	4	2	3
35	4	2	2	1	4
40	1	4	1	3	2
50	1	2	3	1	5

Вариант 3

1.

2.

3.

	100	30	70	30	50
50	3	1	2	4	3
90	5	1	3	2	6
65	2	3	4	1	1
75	6	2	5	3	2

	40	40	20	10	30
23	4	2	2	3	1
27	1	1	5	4	2
25	3	4	3	5	3
95	4	5	3	3	2

Вариант 4

1.

2.

3.

	40	100	120	150	70
140	2	1	4	3	5
160	8	7	5	1	3
100	4	6	2	7	1
80	1	5	3	4	6

	300	300	100	250	200
150	3	1	4	2	1
250	3	2	2	1	3
200	4	1	5	3	2
300	2	2	3	1	4

Вариант 5

1.

2.

3.

	100	100	200	120	80
100	1	3	5	6	8
200	3	4	3	7	3
150	5	2	1	8	2
150	1	3	2	5	4

	33	37	30	20	3
26	1	4	2	2	4
24	2	3	1	5	1
25	4	2	3	4	3
35	2	3	1	3	2



Литература

1. Акулич И. Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986. 320 с.

2. Барсов А. С. Линейное программирование в технико-экономических задачах. -- М.: Наука, 1964. -- 278 с.

3. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. -- 2-е изд., перераб. и доп. -- М.: Финансы и статистика, 2006. - 432 с.

4. Буров, А. В. Моделирование экономических процессов и систем: учебное пособие / А. В. Буров, С. Л. Миньков, В. М. Ушаков. - Томск: Изд-во ТГПУ, 2001. - 158 с.

5. Горчаков, А. А. Компьютерные экономико-математические модели / А. А. Горчаков, И. В. Орлова. - М.: ЮНИТИ, 1995. - 136 с.

6. Данко, П. Е. Высшая математика в упражнениях и задачах: учебное пособие / П. Е. Данко. - М.: Оникс, 2008. - 816 с.

7. Замков, О. О. Математические методы в экономике: учебник / О. О. Замков, А. В. Толстопятенко, Ю. Н. Черемных; под ред. А. В. Сидоровича. - Изд. 4-е, испр. и доп. - М.: Дело и Сервис, 2004. - 365 с.

8. Карпелевич Ф. И, Садовский Л. Е. Элементы линейной алгебры и линейного программирования. -- М.: Наука, 1967. -- 312 с.

9. Конюховский П.В. Математические методы исследования операций в экономике: Учебное пособие. - СПб.: "Питер", 2000

10. Кремер, Н. Ш. Исследование операций в экономике: учебное пособие / Н. Ш. Кремер, Б. А. Путко. - М.: ЮНИТИ, 2006. - 407 с.

11. Лунгу К. В., Макаров Е. В. Высшая математика. Руководство к решению задач. -- М.: Физматлит, 2004. -- 212 с.

12. Математика в экономике: учебник для вузов / А. С. Солодовников [и др.]. - Изд. 2-е, испр. и доп. - М.: Финансы и статистика, 2003. - 555 с.

13. Математика в экономике: Учебно-методическое пособие для вузов./ Под ред. Н.Ш. Кремера. - М.: "Финстатинформ", 1999.

14. Пивоварчик А. А. Математическое программирование. -- М.: Издательство МГОУ, 1997. - 300 с.

15. Сборник задач по высшей математике для экономистов. Учебное пособие / Под ред. В.И.Ермакова. - М.: ИНФРА-М, 2002.

16. Юдин Д. Б., Голъдштейн Е. Г. Линейное программирование. -- М.: Наука, 1969.

Размещено на Allbest.ru