Линейное программирование

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

Содержание

Допустимое и оптимальное решения

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

Задача 1

Задача 2



Допустимое и оптимальное решения

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

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

- задача об оптимальном использовании ресурсов при производственном планировании;

- задача о смесях (планирование состава продукции);

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

- транспортные задачи (анализ размещения предприятия, перемещение грузов). Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

- математические модели большого числа экономических задач линейны относительно искомых переменных;

- данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;

- многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

- целевая функция:

= c1x1 + c2x2 + ... + cnxn > max(min);- ограничения:

a11x1 + a12x2 + ... + a1nxn {? = ?} b1,

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

a21x1 + a22x2 + ... + a2nxn {? = ?} b2

am1x1 + am2x2 + ... + amnxn {? = ?} bm;

- требование неотрицательности:

xj ? 0, 

При этом aij, bi, cj ( ) - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

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

1. Задача об оптимальном использовании ресурсов при производственном планировании. Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида ( ). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей. Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

Производственные участки	затраты времени на единицу продукции, н-час	доступный фонд времени, н-час
	клюшки	наборы шахмат
А	4	6	120
В	2	6	72
С	-	1	10
прибыль на единицу продукции, $	2	4

По данному условию сформулируем задачу линейного программирования. Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 - количество выпускаемых ежедневно шахматных наборов. Формулировка ЗЛП:

= 2x1 + 4x2 > max; Размещено на http://www.allbest.ru/

4x1 + 6x2 ? 120,

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

2x1 + 6x2 ? 72,

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

x2 ? 10;

x1 ? 0, x2 ? 0

Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

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

Постановка задачи

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

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

максимум валовой продукции,

товарной продукции,

прибыли,

минимум материально-денежных затрат.

Группы переменных:

площади севооборотов

площади внесевооборотных участков

площади культур в севооборотах

площади культур на внесевооборотных участках

среднегодовое поголовье животных по видам и половозрастным группам;

прирост кормов в рационе кормления животных сверх минимальной потребности.

Группы ограничений:

по использованию площади пашни;

по культурам в севообороте;

культурам вне севооборота;

по использованию лимитированных производственных ресурсов;

по производству и потреблению кормов;

по оптимизации среднегодовых рационов кормления животных;

по реализации продукции;

дополнительные.

Исходная информация:

виды сельскохозяйственных культур и схемы севооборотов;

видовой состав поголовья животных;

урожайность сельскохозяйственных культур и продуктивность животных;

затраты труда и материальных ресурсов на единицу продукции растениеводства и животноводства;

объёмы лимитированных производственных ресурсов;

зоотехнические требования к уровню кормления животных;

объёмы реализации продукции;

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

Структурная экономико-математическая модель

Условные обозначения:

Xs - площадь s-го севооборота

Xk - площадь k-го внесевооборотного участка

Xjs - площадь j-й культуры в s-м севообороте

Xjk - площадь j-й культуры на k-м внесевооборотном участке

Xl - поголовье животных l-й половозрастной группы

Яjs - удельный вес посевов j-й культуры в s-м севообороте

aijs - затраты i-го ресурса на 1 га посева j-й культуры в s севообороте

aijk - затраты i-го ресурса на 1 га посева j-й культуры на k-м внесевооборотном участке

ail - затраты i-го ресурса на 1 голову животных l-й половозрастной группы

dijs - выход корма в пересчёте на i-й элемент питания с 1 га посева j-й культуры в s-м севообороте

dijk - выход корма в пересчёте на i-й элемент питания с 1 га посева j-й культуры на k-м внесевооборотном участке

vil - общая потребность в кормах в пересчёте на i-й элемент питания для 1 головы животных l-й половозрастной группы

vjl - потребность в j-м виде корма для 1 головы животных l-й половозрастной группы, ц корм.ед.

qjs - выход товарной продукции с 1 га посева j-й культуры в s-м севообороте

qjk - выход товарной продукции с 1 га посева j-й культуры на k-м внесевооборотном участке

ql - выход товарной продукции от 1 головы животных l-й половозрастной группы

S - общая площадь пашни

bi - объем производственных ресурсов i-го вида, выделяемых для производства продукции растениеводства и животноводства

Di - выход корма с естественных кормовых угодий в пересчёте на i-й элемент питания

Qj - гарантированный объем производства j-го вида товарной продукции растениеводства

Ql - гарантированный объем производства l-го вида товарной продукции животноводства

cjs - оценка критерия оптимальности в расчёте на 1 га посева j-й культуры в s-м севообороте

cjk - оценка критерия оптимальности в расчёте на 1 га посева j-й культуры на k-м внесевооборотном участке

cl - оценка критерия оптимальности в расчёте на 1 голову животных l-й половозрастной группы

Требуется найти оптимальный план, т.е. набор значений {Xs Xk Xjs Xjk Xl Xjl } ? 0, при которых достигается максимальное значение функции F(x)

при условиях:

1. Использование площади пашни

2. По структуре севооборотов

Xjs = Яjs Xs

3. По площади культур вне севооборота

4. Использование производственных ресурсов i-го вида

5. Производство и потребление кормов - всего

6. Производство и потребление кормов по видам и группам

7. Ограничения по гарантированному производству продукции растениеводства



8. Ограничения по гарантированному производству продукции животноводства

Пример

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

В хозяйстве имеется 4500 га пашни, на которой может быть освоено 2 севооборота:

1 севооборот 2 севооборот

1. Пар + корнеплоды 1. Кукуруза

2. Пшеница 2. Пшеница

3. Пшеница 3. Зернобобовые

4. Кукуруза 4. Пшеница

5. Ячмень 5. Однолетние травы

6. Однолетние травы

Кукуруза используется на силос, однолетние травы - на сено, сенаж и зелёный корм. Имеется 650 га сенокосов, урожайность которых составляет 5 ц/га и 1520 га пастбищ с урожайностью 10 ц/га. Коэффициент перевода в корм. ед. сена естественных сенокосов - 0,45, зелёной массы пастбищ - 0,18.

Выход кормов с 1 га посева культур в севооборотах (в среднем), ц корм. ед.

Корнеплоды - 22

Пшеница:

зерно - 21,6

солома - 2,2

Кукуруза на силос - 25

Ячмень:

зерно - 22,8

солома - 2,5

Зернобобовые:

зерно - 18,7

солома - 2,0

Однолетние травы:

сено - 12

сенаж - 18

зелёный корм - 20

Выход товарного зерна с 1 га посевов, ц: пшеница -18, ячмень и зернобобовые используются только на корм. Зерна для реализации должно быть произведено не менее 30 тыс. ц. Надой молока от 1 коровы - 26 ц, объём реализации молока - не менее 20 тыс. ц. Затраты кормов на 1 корову в год - 36 ц корм. ед., на 1 голову молодняка - 18 ц корм. ед. Удельный вес коров в стаде - 35% .

Таблица 1- Структура рационов кормления животных, %

Виды и группы кормов	Коровы	Молодняк
Концентраты	18	16
Грубые	25	32
Сочные	21	14
Зелёные	36	38

Прибыль с 1 га посева пшеницы - 1200р., от 1 коровы - 3500р., от 1 головы молодняка - 2300 р. Цель задачи - максимум прибыли.

Объекты планирования

1-я группа - площади севооборотов, га

Х1 - площадь 1-го севооборота

Х2 - площадь 1-го севооборота

2-я группа - площади посева культур в севооборотах, га

в 1-м севообороте Х3 - пар Х4 - корнеплоды Х5 - пшеница товарная Х6 - пшеница фуражная Х7 - кукуруза Х8 - ячмень Х9 - однолетние травы на сено Х10 - однолетние травы на сенаж Х11 - однолетние травы на зел. корм	во 2-м севообороте Х12 - кукуруза Х13 - пшеница товарная Х14 - пшеница фуражная Х15 - зернобобове Х16 - однолетние травы на сено Х17 - однолетние травы на сенаж Х18 - однолетние травы на зел. корм

3-я группа - поголовье животных, гол.

Х19 - поголовье коров

Х20 - поголовье молодняка кр. рог. скота

4-я группа - вспомогательные переменные

Х21 - солома на корм скоту, ц корм. ед.

Подготовка исходной информации

Таблица 2 - Удельный вес посевов культур в севооборотах

1 севооборот - Х1	2 севооборот - Х2
Культуры	Уд. вес	Переменная	Культуры	Уд. вес	Переменная
Пар + корнеплоды	0,167	Х3, Х4	Кукуруза	0,2	Х12
Пшеница - 2 поля	0,332		Пшеница - 2 поля	0,4
в т.ч.: товарная		Х5	в т.ч.: товарная		Х13
фуражная		Х6	фуражная		Х14
Кукуруза	0,167	Х7	Зернобобовые	0,2	Х15
Ячмень	0,167	Х8	Однол. травы	0,2
Однол. травы	0,167		в т.ч. на сено		Х16
в т.ч. на сено		Х9	сенаж		Х17
сенаж		Х10	зел. корм		Х18
зел. корм		Х11
Итого	1		Итого	1



Таблица 3 - Выход продукции с 1гектара посева культур в севооборотах

1 севооборот - Х1	2 севооборот - Х2
Культуры	Переменная	Выход корма, ц корм. ед.	Культуры	Переменная	Выход корма, ц корм. ед.
Корнеплоды	Х4	22	Кукуруза	Х12	25
Пшеница товарная	Х5	- / 2,2	Пшеница товарная	Х13	- / 2,2
фуражная	Х6	21,6 / 2,2	фуражная	Х14	21,6 / 2,2
Кукуруза	Х7	25	Зернобобовые	Х15	18,7 / 2
Ячмень	Х8	22,8 / 2,5	Однол. травы на сено	Х16	12
Однол. травы на сено	Х9	12	сенаж	Х17	18
сенаж	Х10	18	зел. корм	Х18	20
зел. корм	Х11	20

Таблица 4 - Выход кормов с естественных угодий

Вид угодий	Площадь, га	Урожайность, ц/га	Валовой сбор, ц	Выход кормовых единиц, ц
Сенокосы	650	5	3250	1462
Пастбища	1520	10	15200	2432
Итого	х	х	х	3894

Таблица 5 - Рационы кормления крупного рогатого скота, ц корм. ед.

Виды и группы кормов	Коровы - Х19	Молодняк - Х20
	%	ц корм.ед.	%	ц корм.ед.
Концентраты	18	6,48	16	2,88
Грубые	25	9,00	32	5,76
Сочные	21	7,56	14	2,52
Зелёные	36	12,96	38	6,84
Итого	100	36	100	18

Развёрнутая экономико-математическая модель задачи

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

F(x) = 1200X5 + 1200X14 + 3500X19 + 2300X20 > max



Ограничения

1. По площади пашни, га Х1 + Х2 <= 4500

По посевам культур в первом севообороте, га:

2. Пар + корнеплоды	Х3 + Х4 = 0,167 Х1
3. Пшеница	Х5 + Х6 = 0,332 Х1
4. Кукуруза	Х7 = 0,167 Х1
5. Ячмень	Х8 = 0,167 Х1
6. Однолетние травы	Х9 + Х10 + Х11 = 0,167 Х1

По посевам культур во втором севообороте, га:

7. Кукуруза	Х12 = 0,2 Х2
8. Пшеница	Х13 + Х14 = 0,4 Х2
9. Зернобобовые	Х15 = 0,2 Х2
10.Однолетние травы	Х16 + Х17 + Х18 = 0,2 Х2

11. Производство соломы на корм скоту, ц корм. ед.

2,2Х5 + 2,2Х6 + 2,5Х8 + 2,2Х13 + 2,2Х14 + 2Х15 >= X21

12. Производство и потребление кормов - всего, ц корм. ед.

-22Х4 -21,6Х6 -25Х7 -22,8Х8 -12Х9 -18Х10 -20Х11 -25Х12

-21,6Х14 -18,7Х15 -12Х16 -18Х17 -20Х18 + 36Х19 + 18Х20 -Х21 <= 4198

Производство и потребление кормов по видам, ц корм. ед.

13. Концентраты

-

21,6Х6 -22,8Х8 -21,6Х14 -18,7Х15 + 6,48Х19 + 2,88Х20 <= 0

14. Грубые



-12Х9 -18Х10 -12Х16 -18Х17 + 9Х19 + 5,76 Х20 - Х21 <= 1462

15. Сочные

-22Х4 -25Х7 -25Х12 + 7,56Х19 + 2,52Х20 <= 0

16. Зелёные

-20Х11 -20Х18 + 12,96Х19 + 6,84Х20 <= 2736

17. Соотношение между поголовьем коров и молодняка

Х19=0,35(Х19 + Х20) или 0,65Х19 - 0,35Х20 = 0

18. Производство пшеницы на реализацию, ц

18 Х5 + 18 Х13 >= 30000

19. Производство молока на реализацию, ц

26 Х19 - Х31 >= 20000

Задача 1

Фирма производит два широко популярных безалкогольных напитка - «Лимонад» и «Тоник». Фирма может продать всю продукцию, которая будет произведена. Однако объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования. Для производства 1 л «Лимонада» требуется 0,02 ч работы оборудования, а для производства 1 л «Тоника» - 0,04 ч. Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л «Лимонада» и «Тоника» соответственно. Ежедневно в распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента. Прибыль фирмы составляет 0,10 ден. ед. за 1 л «Лимонада» и 0,30 ден. ед. за 1 л «Тоника». Требуется определить, сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневной прибыли.

Решение:

Составим ЭММ задачи:

В рамках заданных ограничений фирма должна принять решение о том, какое количество каждого вида напитков следует выпускать. Пусть x1 -- число литров Лимонада, производимое за день. Пусть x2 -- число литров Тоника, производимое за день.

Определение цели и ограничений. Цель состоит в максимизации ежедневного дохода. Пусть F(x) = 0,1x1 + 0,3x2 (max) -- ежедневный доход, ден. ед. Он максимизируется в рамках ограничений на количество часов работы оборудования и наличие специального ингредиента. Это целевая функция задачи -- количественное соотношение, которое подлежит оптимизации.

Существуют следующие ограничения на производственный процесс:

Время работы оборудования. Для производства х1 литров Лимонада и х2 литров Тоника требуется: (0,02 х1 + 0,04 х2) часов работы оборудования ежедневно. Максимальное время работы оборудования в день составляет 24 ч, следовательно, объем производства должен быть таким, чтобы число затраченных часов работы оборудования было меньше либо равно 24 ч ежедневно. Таким образом,

0,02 х1 + 0,04 х2Ј 24 ч/день.

Специальный ингредиент. Производство х1 литров Лимонада и х2 литров Тоника требует (0,01 х1 + 0,04 х2) кг ингредиента ежедневно. Максимальный расход ингредиента составляет 16 кг в день, следовательно, объем производства должен быть таким, чтобы требуемое количество специального ингредиента составляло не более 16 кг в день. Таким образом,

0,01 х1 + 0,04 х2 Ј 16 кг/день.

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

F(x) = 0,1x1 + 0,3x2 (max)

0,02 х1 + 0,04 х2 ? 24

0,01 х1 + 0,04 х2 ? 16

х1, х2 ? 0

Время работы оборудования:

0,02 х1 + 0,04 х2 ? 24 ч/день.

Проведем прямую

0,02 х1 + 0,04 х2 = 24

Простейшим способом нанесения прямой на график является нахождение точек пересечения данной прямой с осями координат х1 и х2. Подставив х1 = 0 в уравнение и рассчитав значение х1, получим, что при х1 = 0, х2 = 600. Подставив х2= 0 в уравнение и рассчитав значение х1, получим, что при х2 = 0 х1 = 1200. Нанесем эти две точки на график и соединим их прямой. Для определения области, которую следует заштриховать, подставим х1= 0 и х2 = 0 в неравенство: 0,02 х1 + 0,04 х2 ? 24

Специальный ингредиент: 0,01 х1 + 0,04 х2 ? 16

Проведем прямую: 0,01 х1 + 0,04 х2 = 16

Таким же образом, подставив х1 = 0 в уравнение и рассчитав значение х1, получим, что при х1 = 0, х2 = 400. Подставив х2= 0 в уравнение и рассчитав значение х1, получим, что при х2 = 0 х1 = 1600. Нанесем эти две точки на график и соединим их прямой. Для определения области, которую следует заштриховать, подставим х1= 0 и х2 = 0 в неравенство: 0,01 х1 + 0,04 х2 ? 16

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

Решим систему уравнений

0,02х1 + 0,04 х2 = 24 (1)

0,01х1 + 0,04 х2 = 16 (2)

Вычтем уравнение (2) из уравнения (1): 0,01 х1 = 8.

Тогда х1 = 800 л в день. Подставив найденное значение х1 в уравнение (2), найдем х2:

0,01 * 800 + 0,04 х2 = 16.

х2 = 200 л в день.

Следовательно,

max F(х1,х2) = 0,1* 800 + 0,3 * 200 = 140 (ден. ед.)

Ответ: Максимальная ежедневная прибыль от реализации продукции составит 140 ден.ед. при производстве 800 л "Лимонада" и 200 л "Тоника". Если решать задачу на минимум, то компания прибыли не получит и при производстве продукции понесет убытки.

Задача 2

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

Таблица 1 - Исходные данные к задаче

Склад	Магазин	Запасы продукции на складе, ед.
	«Сокол»	«Рижский»	«ВДНХ»	«Киевский»
Пражская	5	2	1	1	100
Волжская	3	7	5	5	110
Курская	9	6	4	4	90
Объём заказа продукции, ед.	25	135	40	100	300

Решение:

Обозначим через Xij - количество груза, которое необходимо перевезти от i-го поставщика (склада) к j-му потребителю

i = 1, 2, 3

j = 1, 2, 3, 4

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

Переменные:

X11 - объем груза, перевозимого c пражского склада в магазин «Сокол», т;

Х12 - объем груза, перевозимого c пражского склада в магазин «Рижский», т;

Х13 - объем груза, перевозимого c пражского склада в магазин «ВДНХ», т;

Х14 - объем груза, перевозимого c пражского склада в магазин «Киевский», т;

Х21 - объем груза, перевозимого c волжского склада в магазин «Сокол», т;

Х22 - объем груза, перевозимого c волжского склада в магазин «Рижский», т;

Х23 - объем груза, перевозимого c волжского склада в магазин «ВДНХ», т;

Х24 - объем груза, перевозимого c волжского склада в магазин «Киевский», т;

X31 - объем груза, перевозимого c курского склада в магазин «Сокол», т;

Х32 - объем груза, перевозимого c курского склада в магазин «Рижский», т;

Х33 - объем груза, перевозимого c курского склада в магазин «ВДНХ», т;

Х34 - объем груза, перевозимого c курского склада в магазин «Киевский», т;

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

1)по возможности с пражского склада, т х11 + х12 + х13 + х14= 100

2) по возможности с волжского склада, т х21 + х22 + х23 + х24= 110

3) по возможности с курского склада, т х31 + х32 + х33 + х34 = 90

по потребности магазина «Сокол», т х11 + х21 + х31= 25

по потребности магазина «Рижский», т х12 + х22 + х32= 135

по потребности магазина «ВДНХ», т х13 + х23 + х33= 40

по потребности магазина «Киевский», х14 + х24 + х34=100

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

F(x) = 5х11 + 2х12 + 1х13 + 1х14 +3х21 + 7х22 + 5х23 + 5х24+9х31 + 6х32 + 4х33 + 4х34>min

2. Получаем опорный план и определяем величину транспортных расходов по этому плану.

х11 = 25 т х21 = 25т х31=25

х12 = 25 т х22= 25 х32=20

х13=40 х23 = 40 х33=40

х14 =10 х24 = 20 т х134=15

F (x) = 1340т. р

3. Проверяем план на оптимальность.

По алгоритму решения следует каждую свободную клетку проверить на оптимальность.

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

Характеристика для клетки d= -1, следовательно, полученный план не является оптимальным. План улучшается за счет клетки с отрицательной характеристикой .

4. Строим цикл пересчёта и определяем объём перераспределяемого по нему груза.

Переход от одного опорного плана к другому осуществляют с помощью построения цепи и последовательного перераспределения поставок. Делается это следующим образом.

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

Для каждой свободной клетки существует только один цикл пересчёта.

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

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

- Просматриваем объемы в отрицательных вершинах и выбирают наименьший

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

5. Получаем следующий вариант плана и определяем величину транспортных расходов по нему.

В клетки, затронутые циклом пересчёта, заносим объёмы, полученные в предыдущем пункте. Объёмы распределения груза для клеток, не затронутых циклом пересчёта, переносим из предыдущего плана без изменения. Получим новый план грузоперевозок, с меньшим значением целевой функции.

х11 = 25 т х21 = 25т х31=25

х12 = 25 т х22= 25 х32=20

х13=40 х23 = 40 х33=40

х14 =10 х24 = 20 т х134=15

F (x) = 1340т. р

Затраты на перевозку составят 1340 тыс. р.

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