bannerka.ua

Целочисленные задачи линейного программирования

Целочисленные задачи линейного программирования

1. Обзор темы

Целочисленного программирования

1.1. Математическая постановка задачи целочисленного программирования.

1.2. Алгоритм решения задачи целочисленного программирования графическим методом.

1.3. Алгоритм метода Гомори.

1.1 Математическая постановка задачи целочисленного программирования

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

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

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

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

Целочисленные задачи линейного программирования (1.1)

При условиях

Целочисленные задачи линейного программирования (1.2)

Целочисленные задачи линейного программирования, (1.3)

Целочисленные задачи линейного программирования — цели Целочисленные задачи линейного программирования (1.4)

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

1.2 Алгоритм решения задачи целочисленного программирования графическим методом

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

Рассмотрим Алгоритм данного Метода на примере:

В цехе предприятия решили установить дополнительное оборудование, для размещения которого выделено 19/3 м2 площади. На приобретение оборудования предприятие может израсходовать 10000 грн., При этом оно может закупить оборудование двух видов. Комплект оборудования и вида стоит 1000 грн., А II вида — 3000 грн. Приобретение одного комплекта оборудования и вида позволит увеличить выпуск продукции в смену на 2 ед., А одного комплекта оборудования ИИ вида — на 4 ед. Для установки одного комплекта оборудования и вида требуется 2 м2 площади, а для оборудования ИИ вида — 1 м2 площади. Определить такой набор дополнительного оборудования, который позволит максимально увеличить выпуск продукции.

Решения. Пусть х1 — количество комплектов оборудования и вида, приобретающий предприятие, а х2 — количество комплектов оборудования ИИ вида. Тогда математическая модель задачи имеет вид:

Целочисленные задачи линейного программирования

1) Решить задачу графическим методом [см.. Часть 1, с. 19-20]. При получении целочисленный решение, то задача решена. В противном случае перейти к п.2.

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

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

4) Через точку (0; 0) проводят перпендикулярную вектору Целочисленные задачи линейного программирования прямую А.

5) Переcуваючы прямую А в направлении вектора Целочисленные задачи линейного программирования, определяют первую и последнюю точки пересечения прямой с многоугольником решений. Первая точка — точка минимума, последняя — точка максимума.

6) Определяют координаты точки максимума (минимума).

7) Определяют значение целевой функции в точке максимума (минимума), подставляя в целевую функцию координаты точки максимума (минимума) Целочисленные задачи линейного программированияРис. 1.1

Решением приведенного примера является т. E (1, 3), в которой Целевая функция принимает максимальное значение Целочисленные задачи линейного программирования. То есть предприятие должно приобрести 1 комплект оборудования первого вида и 3 комплекта оборудования второго вида. Это обеспечит предприятию максимальное увеличение выпуска продукции составляет 14 единиц в смену.

1.3 Алгоритм метода Гомори.

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

1) Находят решение задачи целочисленного программирования симплексным методом, несмотря на условие целочисленности переменных.

2) Анализируют найденное решение. Если среди Компонентов Нету дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования. В противном случае составляют дополнительное ограничение для переменной, в оптимальном плане задачи (1.1) — (1.3) имеет максимальное дробное значение, а в оптимальном плане задачи (1.1) — (1.4) должна быть целочисленной.

Целочисленные задачи линейного программирования (1.5)

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

Дробной частью числа называется разность между этим числом и его целой частью.

Целой частью числа называется наибольшее целое число, не превышающее данное.

3) С помощью двойственного симплексного метода находят решение задачи, которую получили из задачи (1.1) — (1.4) путем введения дополнительного ограничения.

4) В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (1.1) — (1.4) или до установления невозможности ее решения.

Пример. Предприятие выпускает два вида продукции — А и В. Для этого использует два вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице 1. В ней также указано прибыль от реализации единицы продукции каждого вида и общее количество сырья по видам.

Вид сырья

Нормы расхода сырья (кг) на единицу продукции вида

Общее количество сырья (кг)

А

В

И

2

1

Целочисленные задачи линейного программирования

ИИ

1

3

4

Прибыль от реализации одного изделия

1

4

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

Пусть Целочисленные задачи линейного программирования — количество изделий вида А, Целочисленные задачи линейного программирования — количество изделий вида В. Тогда прибыль предприятия составляет

Целочисленные задачи линейного программирования

При условиях

Целочисленные задачи линейного программирования.

Запишем задачу в форме основной задачи ЛП:

Целочисленные задачи линейного программирования

Целочисленные задачи линейного программирования

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

Применим алгоритм розвьзання целочисленных задач ЛП методом Гомори.

1) Решим задачу симплексным методом без учета условия целочисленности переменных Целочисленные задачи линейного программирования и Целочисленные задачи линейного программирования.

Базис

Сб

План

1

4

0

0

Оценочные отношения

Х1

Х2

Х3

Х4

1

Х3

0

Целочисленные задачи линейного программирования

2

1

1

0

Целочисленные задачи линейного программирования

2

Х4

0

4

1

3

0

1

Целочисленные задачи линейного программирования® min

M +1

0

-1

-4

0

0

1

Х3

0

5

5/3

0

1

-1/3

2

Х2

4

4/3

1/3

1

0

1/3

M +1

16/3

1/3

0

0

4/3

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

Целочисленные задачи линейного программирования.

Находим значение функции Целочисленные задачи линейного программирования как дробной части указанных аргументов:

Целочисленные задачи линейного программирования

Или

Целочисленные задачи линейного программирования

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

Целочисленные задачи линейного программирования

Базис

Сб

План

1

4

0

0

0

Х1

Х2

Х3

Х4

Х5

1

Х3

0

5

5/3

0

1

-1/3

0

2

Х2

4

4/3

1/3

1

0

1/3

0

3

Х5

0

-1

-1

0

0

-1

1

M +1

16/3

1/3

0

0

4/3

0

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

Базис

Сб

План

1

4

0

0

0

Х1

Х2

Х3

Х4

Х5

1

Х3

0

5

5/3

0

1

-1/3

0

2

Х2

4

4/3

1/3

1

0

1/3

0

3

Х5

0

-1

-1

0

0

-1

1

M +1

16/3

1/3

0

0

4/3

0

1

Х3

0

10/3

0

0

1

-2

5/3

2

Х2

4

1

0

1

0

0

1/3

3

Х1

1

1

1

0

0

1

-1

M +1

5

0

0

0

1

1/3

Получили целочисленный решение: Целочисленные задачи линейного программирования. Следовательно, предприятие должно производить 1 шт. изделий вида А и 1 шт. изделий вида В. При этом его доход составит 5 гр. ед.

3. Рекомендуемая литература

1. Исследование операций в экономике: Учебн. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин. М. Н. Фридман; Под ред. проф. Н. Ш. Кремера. — М.: Банки и биржи, ЮНИТИ, 1997.

2. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.

Tagged with: , , , , ,
Posted in Математические модели в расчетах на эвм
Перечень предметов
  1. Бухучет в ресторанном хозяйстве
  2. Введение в специальность 4к.2с
  3. Высшая математика 3к.1с
  4. Делопроизводство
  5. Информационные технологии в области
  6. Информационные технологии в системах качества стандартизаціісертифікаціі
  7. История украинской культуры
  8. Математические модели в расчетах на эвм
  9. Методы контроля пищевых производств
  10. Микробиология молока и молочных продуктов 3к.1с
  11. Микропроцессорные системы управления технологическими процессами
  12. Научно-практические основы технологии молока и молочных продуктов
  13. Научно-практические основы технологии мяса и мясных продуктов
  14. Общая технология пищевых производств 4к.2с
  15. Общие технологии пищевых производств
  16. Организация обслуживания в предприятиях ресторанного хозяйства
  17. Основы научных исследований и техничнои творчества
  18. Основы охраны труда
  19. Основы пидприемницькои деятельности и агробизнеса
  20. Основы физиологии и гигиены питания 3к.1с
  21. Пищевые и диетические добавки
  22. Политология
  23. Получения доброкачественного молока 3к.1с
  24. Прикладная механика
  25. Прикладная механика 4к.2с
  26. Теоретические основы технологии пищевых производств
  27. Технологический семинар
  28. Технологическое оборудование для молочной промышленности
  29. Технологическое оборудование для мьяснои промышленности
  30. Технология продукции предприятий ресторанного хозяйства
  31. Технология хранения консервирования и переработки молока
  32. Технология хранения, консервирования и переработки мяса
  33. Технохимическому контроль
  34. Управление качеством продукции ресторанного хозяйства
  35. Физика
  36. Физическое воспитание 3к.1с
Возможно Вы искали: