Целочисленное и бинарное программирование - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Тематика курсовых работ по математическим методам кибернетики 1 16.4kb.
Целочисленное программирование. Метод ветвей и границ 1 92.03kb.
Целочисленное программирование 6 475.77kb.
7. целочисленное программирование 10 870.02kb.
Тема Целочисленное программирование 3 269.32kb.
Целочисленное программирование 1 46.81kb.
Методические указания к лабораторным работам и домашним заданиям... 6 327.14kb.
Программа вступительного экзамена по специальности 05. 13. 18 Математическое... 1 112.81kb.
Тема технология программирование 1 70.3kb.
Варианты заданий к контрольной работе 1 22.41kb.
Средства программирования 10 829.64kb.
Рабочая программа учебной дисциплины «Дискретная оптимизация» 1 132.03kb.
Направления изучения представлений о справедливости 1 202.17kb.

Целочисленное и бинарное программирование - страница №1/1

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

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

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

Задача 1

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




 

 

 

 

 Тип станков

Цена обслуживания

Цена единицы продукции

Производительность в день

Наличие станков




 

Alpha-1000

$200

$1,50

40

8




 

Alpha-2000

$275

$1,80

60

5




 

Alpha-3000

$325

$1,90

85

3

 

 






















План в день 700.

Математическая модель.

  1. Что нам нужно найти?

Количество станков каждого типа xi, чтобы выполнить план в день и чтобы стоимость выпуска была минимальной.

  1. Построение математической модели.

Введем переменные:

piцена обслуживания станка i –го типа

ci – себестоимость единицы продукции на станке i –го типа

oi – производительность в день станка i –го типа

ai – наличие станка i –го типа

Plan – план производства в день

Целевая функция = полная стоимость производства = Стоимость обслуживания станков + Себестоимость продукции

Стоимость обслуживания станков =

Себестоимость продукции=

Целевая функция = +-> minimum

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

xi>=0 – условие неотрицательности искомых величин

xi – целые, количество станков может быть только целым

Условие выполнение плана >= Plan

Условие ограничения наличия станков Xi<=Ai

Задача 2.

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

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

Расписание.

Выходные

Количество рабочих по данному расписанию

 

Sun

Mon

Tue

Wed

Thu

Fri

Sat

A

Воскр, Понед

3




0

0

1

1

1

1

1

B

Понед, Вторник

5




1

0

0

1

1

1

1

C

Вторник, Среда.

6




1

1

0

0

1

1

1

D

Среда., Четверг

4




1

1

1

0

0

1

1

E

Четверг, Пятница

6




1

1

1

1

0

0

1

F

Пятница, Суббота

1




1

1

1

1

1

0

0

G

Суббота, Воскресенье

0

 

0

1

1

1

1

1

0











































Всего рабочих по дням недели:

25




22

17

14

15

15

18

24











































Потребность рабочих по дням недели:







22

17

13

14

15

18

24








































Цена рабочего в день:

$40

























Математическая модель.

  1. Что нам нужно найти?

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

  1. Построение математической модели.

Введем переменные:

Xi- количество рабочих по i-му расписанию.

Aijматрица расписаний I строка указывает номер расписания j столбец день недели

Если aij=1 то это значит что для I –го расписания j –ый день недели рабочий.

Если aij=1 то это значит что для I –го расписания j –ый день недели выходной.

Dj – потребность в рабочих в j день недели.

Pj- цена рабочей смены в j- ый день

Целевая функция = Стоимость рабочих за все дни =



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

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

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

xi>=0 – условие неотрицательности искомых величин

xi – целые, количество рабочих может быть только целым

Условия выполнения потребности в рабочих на каждый день : >=Dj

Бинарное программирование

Бинарное программирование это отдельный класс задач. Переменные в бинарном программировании могут принимать только два значения 0 или 1.

Бинарное программирование используется в задачах , где нужно получить ответ открывать (1) или закрывать предприятие (0). Рассмотрим пример такой задачи.

Задача 3.

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

Информация о карьерах

 

 

 

 

Наличие кальция в руде карьера % на тонну

Наличие магния в руде карьера % на тонну

Максимальная производительность в год (тоннах)

Цена содержания карьера в год ($Million)

Использовать карьер или нет (1=да, 0=нет)

Карьер 1

1

2,3

2000

3,5

1

Карьер 2

0,7

1,6

2500

4

1

Карьер 3

1,5

1,2

1300

4

1

Карьер 4

0,7

4,1

3000

2

1

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

Математическая модель.

  1. Что нам нужно найти?

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

Для этого введем переменную Ai = 1 если I – карьер будет использован и Ai= 0 если I –ый карьер не будет использоваться.

Xi – количество руды сколько нужно добыть на I –ом карьере.

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

  1. Построение математической модели.

Введем переменные:

Ci – наличие кальция в тонне руды i-го карьера

Mi – наличие магния в тонне руды i-го карьера

Pi – максимальная производительность i-го карьера в год

Hi- цена добычи тонны руды на i-ом карьере

Ki- цена содержания i-го карьера в год

Dm - годовая потребность магния в тоннах в год

Dc - годовая потребность кальция в тоннах в год

Целевая функция = Полная стоимость содержания карьеров и добычи руды =

Стоимость содержания карьеров + Стоимость добычи руды =+

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

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

xi>=0 – условие неотрицательности искомых величин

Ai – бинарные значения, т.е. эти переменные могут принимать значения либо о, либо 1

Условие выполнения потребности в кальции : >=Dс

Условия выполнения потребности в магнии : >=Dm

Условие ограничения мощности карьеров: Ai*Xi<=Pi




Чем больше у человека того, чего он стыдится, тем он почтеннее. Джордж Бернард Шоу
ещё >>