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

Автор: Пользователь скрыл имя, 25 Октября 2013 в 18:25, курсовая работа

Краткое описание

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

Оглавление

Введение 3
1 Линейное программирование 4
1.1 Задачи линейного программирования 4
1.2 Решение задач линейного программирования симплекс – методом 5
1.3 Решение задач линейного программирования графическим методом 10
2 Реализация методов линейного программирования на практическом применении 11
2.1 Пример решения задачи линейного программирования симплекс-методом 11
2.2 Пример решения задачи линейного программирования графическим способом 14
2.3 Пример решения задачи линейного программирования с помощью MS EXCEL 16
3 Решение задач линейного программирования 20
3.1 Решение задачи линейного программирования графическим методом 20
3.2 Решение задачи линейного программирования симплекс-методом 27
3.3 Решение транспортной задачи 31
Заключение 36
Список использованной литературы 37

Файлы: 1 файл

КУРСОВАЯ РАБОТА.doc

— 570.00 Кб (Скачать)

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

г) переменную вводим в базис вместо переменной .

д) элементы новой симплекс-таблицы  пересчитываем по следующим формулам:

 

разрешающий элемент  ,

элементы разрешающего столбца  ,

элементы разрешающей  строки ,

 

остальные элементы симплекс-таблицы  по правилу прямоугольника:

 

 

  1. Вновь полученный план проверяем на оптимальность. [2]

 

 

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

 

Алгоритм решения:

  1. Используя систему ограничений и условия неотрицательности, строим область допустимых решений.
  2. Строим линию уровня . Линией уровня функции двух переменных называется линия, вдоль которой функция сохраняет свое постояное значение.
  3. Строим градиент целевой функции. Градиент функции – это вектор, имеющий своими координатами частные производные функции и показывающий направление наискорейшего роста значения функции. Так как целевая функция ЗЛП линейная, то линии уровня целевой функции – прямые и , п – вектор нормали к этим прямым.
  4. Перемещаем линию уровня F=0 вдоль градиента функции. Если ЗЛП на минимум, то оптимальное решение находится в первой точке, принадлежащей ОДР; если ЗЛП на максимум, то оптимальное решения находится в последней точке, принадлежащей ОДР.

 

 

 

 

 

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

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

 

Трикотажная фабрика  использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.

 

Таблица 1.

Сорт материала

Свитер

Кофта

Запасы сырья

Шерсть

9

27

606

Силон

15

15

802

Нитрон

15

3

840

Прибыль (у. е.)

11

6

0


 

Математическая постановка задачи

Общая модель:

P1 и P2 – виды продукции: свитера и кофты.

s1, s2, s3 – запасы сырья: шерсть, силон, нитрон.

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

β – прибыль от реализации единицы готовой продукции кофт.

Решение задачи

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

Пусть х1 – единица готовой продукции вида P1,

x2 – единица готовой продукции вида P2,

Цель фабрики получить максимальную прибыль от реализации всей продукции  видов P1 и P2, тогда:

F=11x1 +6x2 → max

Система ограничений:


9x1 + 27x2 ≤ 606

15x1 + 15x2 ≤ 802

15x1 + 3x2 ≤ 840

x1 ≥ 0, x2 ≥ 0 условие неотрицательности.

  1. Задачу приводим к каноническому виду:

F=11x1 +6x2 → max

9x1 + 27x2+x3= 606


15x1 + 15x2 +x4= 802

15x1 + 3x2+x5 = 840

x1 ≥ 0, x2 ≥ 0, x3≥0, x4≥0, x5≥0

  1. Базисные переменные выражаем через свободные:

x3=606 – 9x1 - 27x2


x4=802 – 15x1 - 15x2

x5=840 – 15x1 - 3x2

  1. Записываем начальный план: X0=(0; 0; 606; 802; 840)
  2. Строим первую симплекс-таблицу:

 

 

 

 

 

 

 

 

 

Таблица 2.

Своб. перем.

Базис. перем.

-x1

-x2

Свободные члены

Симплексные отношения

x3

9

27

606

≈-0,75

x4

15

15

802

≈0,030

x5

15

3

840

≈-0,090

F-строка

-11

-6

0

 

  

Начальный план не оптимален, так как в F-строке есть отрицательные элементы.

  1. Улучшение плана. Строим вторую симплекс-таблицу, элементы которой пересчитываем по соответствующим формулам.

 

Таблица 3.

Своб. Перем

Базис. перем.

Х4

X5

Свободные члены

Симплексные отношения

X3

-0,6

18

124,8

 

X1

0,07

1

46,5

 

X2

-1

-12

6,9

 

F-строка

0,73

5

552,9

 

 

  1. План, соответствующий таблице 3, X1=(46,5; 6,9; 124,8; 0; 0) оптимален, так как в F-строке нет отрицательных элементов.

Ответ: если предприятие  будет выпускать продукцию вида P1 и P2, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.

Максимальная прибыль  для x1=46 и x2=6 находится по формуле:

F max=11*46+6*6=542 единицы.

 

 

2.2 Решение задачи линейного  программирования графическим способом

 

Трикотажная фабрика  использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.

 

Таблица 4.

Сорт материала

Свитер

Кофта

Запасы сырья

Шерсть

9

27

606

Силон

15

15

802

Нитрон

15

3

840

Прибыль (у. е.)

11

6

0


 

Решение задачи

Составим математическую модель задачи:

Пусть х1 – единица готовой продукции вида P1,

x2 – единица готовой продукции вида P2,

Цель фабрики получить максимальную прибыль от реализации всей продукции видов P1 и P2, тогда:

F=11x1 + 6x2 → max

Система ограничений:

9x1 + 27x2 ≤ 606


15x1 + 15x2 ≤ 802

15x1 + 3x2 ≤ 840

x1 ≥ 0, x2 ≥ 0 условие неотрицательности.

Используя алгоритм решения и систему ограничений и условия неотрицательности, построим ОДР. Для этого во всех неравенствах системы ограничений и условия неотрицательности знак неравенства заменим на знак равенства. В результате будем иметь уравнения прямых:

F1: 9x1+27x2=606

F2: 15x1+15x2=802

F3: 15x1+3x2=840

x1=0, x2=0

В системе координат  построим эти прямые. В результате будем иметь ОДР. В этой же системе координат строим линию уровня и вектор

 

Рис. 1. Система координат

 

Так как задача на максимум, будем  перемещать линию уровня F=0 вдоль вектора n до тех пор, пока она не пересечет ОДР в самом крайнем своем положении, т.е. при дальнейшем перемещении она не будет с ОДР иметь общие точки. Такой точкой оказалась точка пересечения прямых F1.

Вычислим ее координаты.

9x1+27x2=606


15x1+15x2=802

x1=46,5; x2=6,9; F max=11*46,5+6*6,9=552,9

Таким образом, если предприятие  будет выпускать продукцию вида P1 и P2, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.

Максимальная прибыль  для x1=46 и x2=6 находится по формуле:

F max=11*46+6*6=542 единицы.

 

 

2.3 Решение задачи линейного  программирования с помощью MS EXCEL

 

Трикотажная фабрика  использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.

 

Таблица 5.

Сорт материала

Свитер

Кофта

Запасы сырья

Шерсть

9

27

606

Силон

15

15

802

Нитрон

15

3

840

Прибыль (у. е.)

11

6

0


 

Решение задачи

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

Пусть х1 – единица готовой продукции вида P1,

x2 – единица готовой продукции вида P2,

Цель фабрики получить максимальную прибыль от реализации всей продукции видов

P1 и P2, тогда:

F=11x1 +6x2 → max

Система ограничений:

9x1 + 27x2 ≤ 606

15x1 + 15x2 ≤ 802

15x1 + 3x2 ≤ 840

x1 ≥ 0, x2 ≥ 0 условие неотрицательности.

2. Подготовка листа  рабочей книги MS Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 2. Переменные задачи находятся, соответственно, в ячейках С3 и С4. Целевая функция находится в ячейке С6 и содержит формулу: =11*С3+6*С4.

Ограничения на задачу учтены в ячейках С8:D10.

Рис. 2. Рабочий лист MS Excel для решения задачи

 

3. Работа с надстройкой  Поиск решения – воспользовавшись  командой Сервис → Поиск решения,  вводим необходимые данные для  рассматриваемой задачи (установка  данных в окне Поиск решения  приведена на рис. 3)

Рис. 3. Установка необходимых параметров задачи в окне Поиск решения

 

Результат работы по поиску решения помещен на рис 4.

 

Рис. 4. Результат расчета надстройки Поиск решения

 

Если предприятие будет  выпускать продукцию вида P1 и P2, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.

Информация о работе Задачи линейного программирования