Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

LPZad

.doc
Скачиваний:
7
Добавлен:
13.02.2018
Размер:
109.57 Кб
Скачать

Типовые оптимизационные задачи

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

1. Задача о диете (пищевом рационе). Имеется N видов продуктов питания pi . Известна стоимость единицы каждого продукта ci. Из этих продуктов необходимо составить пищевой рацион, который должен содержать белков не менее B единиц, углеводов не менее U единиц, жиров не менее G единиц. Для каждой единицы i-го продукта известно содержание единиц белков-bi , углеводов- ui и жиров- gi. Требуется так составить пищевой рацион, чтобы обеспечить заданные условия при минимальной стоимости рациона.

Модель. Пусть xi – количества продуктов i-го вида. Тогда

. Задача ЛП с размерностью 3хN.

2. Задача о ранце. Имеется N видов предметов, которые турист хочет взять с собою в поход. Известны вес bi каждого предмета и его эффективность ei для туристов. Составить список предметов, помещаемых в рюкзак, учитывая, что предельный вес рюкзака не более заданной величины B. Необходимо, чтобы суммарный эффект был максимальным.

Эту задачу можно рассмотреть в двух вариантах:

  1. решение в виде брать предмет или не брать;

  2. сколько взять предметов каждого вида.

Пусть xi – количество предметов каждого вида.

Модель задачи для первого варианта:

, xi={0,1}.

Это булевская задача с размерностью 1хN.

Можно свести к задаче ЦЛП: , xi- целые. Тогда размерность задачи (N+1)хN.

Модель задачи для второго варианта:

,, целое.

Это задача ЦЛП с размерностью 1хN.

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

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

Имеется m – пунктов производства (складов) некоторого одного продукта, ai - объем производства в i-м пункте производства, .

n пунктов потребления, bj - объем потребления (поданные заявки на поставку продукта) в j-м пункте потребления, .

Пункты производства связаны с пунктами потребления сетью дорог с определенными тарифами на перевозки. Стоимость перевозки одной единицы товара с производства i в пункт j равна Cij. Необходимо найти оптимальный план перевозок продукции, при котором транспортные издержки минимальны, продукция полностью вывозится из пунктов производства и полностью удовлетворяет потребность.

Модель.

xij – количество продукта, вывозимого из i-го пункта производства в j-й пункт потребления.

,

Размерность задачи (m+n) x mn

Методы решения:

1. симплекс метод

2. специальные методы: для нахождения опорного плана: метод северо-западного угла, метод минимального элемента; для нахождения оптимального плана - метод потенциалов.

3. обобщенный венгерский метод и др.

ТЗ может рассматриваться в 2-х вариантах: открытая ТЗ и закрытая ТЗ.

ТЗ закрытая, если выполняется условие баланса производство равно потреблению:

О ткрытая ТЗ может быть в 2-х вариантах:

1)

Вводим фиктивный пункт потребления n+1, объем потребления которого равен:

2 )

Вводим фиктивный пункт производства m+1, объем производства которого равен:

4. Задача о назначении.

Имеется p исполнителей и p работ. Известна эффективность применения каждого исполнителя на каждой работе Cij. Необходимо расставить исполнителей по работам, чтобы суммарный эффект от работы был максимальным. Каждый работник может выполнять только одну работу, и каждая работа может выполняться только одним исполнителем.

Модель.

xij – факт применения i-го работника на j-й работе.

. 1- назначается на работу, 0- нет.

Это задача булевского программирования с размерностью (p+q) x pq.

Сводится к задаче ЦЛП с размерностью (p+q+pq) x pq. Для этого вводим дополнительные ограничения:

от переходим к

В таком виде задача решается следующими методами:

  1. методы ЛП (например симплекс-метод) в силу специфики модели;

  2. методы ЦЛП (неэффективны) – метод Гомори, ветвей и границ для ЦЛП;

  3. как частный случай транспортной задачи (объемы поставок и потребления равны 1);

  4. венгерский метод.

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

5. Задача о коммивояжере.

Есть n городов. Затраты (стоимостные, временные, расстояния) на переезд между i-м и j-м городом заданы в виде матрицы Cij , ,. Коммивояжер, выехав из исходного города должен объехать все города, посетив каждый однажды, и вернуться в исходный. Определить в каком порядке нужно объезжать города, чтобы суммарные затраты были минимальными.

Модель.

Пусть

Задача ЦЛП. Размерность (2n+n2) x n2

Результат решения задачи может быть представлен в виде матрицы вида: или в виде маршрута: 1-2-3-5-4-1.

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

Методы решения:

  1. метод ветвей и границ для з-чи о коммивояжере – в этом методе уже заложено условие связанности циклов.

  2. венгерский метод с модификацией, отвергающей решения с неполными замкнутыми циклами

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

На раскрой поступает s различных материалов, требуется изготовить n различных видов изделий, причем продукция выпускается комплектами и в комплект входит bk изделий k-го вида. Каждая единица j-го материала может быть раскроена p различными способами так, что при использовании i-го способа получается aijk единиц изделий k-го вида. Известно, что материала j-го вида имеется cj единиц. Найти план раскроя, обеспечивающий максимальное число комплектов при заданных ограничениях на материал.

Модель. Пусть xij – число заготовок j-го материала, раскроенных i-м способом.

, , целые

Задача НЛП. Размерность задачи: s x p*s

Эту задачу можно привести к линейному виду. Введем еще одну переменную y – количество комплектов. Тогда получим модель:

, , целые

Задача ЦЛП. Размерность задачи (s+n) x (p*s+1)

Подготовил

Сергей Чекрыжов

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]