Расчет сетевого графа на основе линейного программирования

Пусть t_i - время начала i-ой работы, тогда система ограничений примет следующий вид:

t₂ - t₁≥70

t₃ – t₂≥120

t₄ – t₃≥60

t₅ – t₄≥40

t₆ – t₅≥20

t₇ – t₆≥30

t₈ – t₇≥15

F_{min =} t₈

Решая данную систему ограничений в Excel, считая, что все t_i целочисленные и положительные, получаются следующие значения времени t_i.

Рис.3

Минимизация булевых функций.

Дизъюнкция

X	Y	XvY

Конъюнкция

X	Y	X^Y

ДСНФ

f=(x₁ x₂ x₃) v (x₁ x₂ x₃) v (x₁ x₂ x₃) v (x₁ x₂ x₃)

В функции будет столько двойных скобок, сколько функция принимает значение единицу. Внутри скобок ставится конъюнкция исходных переменных. Если переменные входят в набор с единицей,то она ставится без инверсии, если с «0» - то с «-». Между скобками ставится знак дизъюнкции.

О минимизации булевых функций в классе ДНФ

Операция склеивания: (A*x_i)V(A* x _i)=A;

Операция поглощения: (A)V(A*x_k)=A.

Функция представлена таблично

x₁ x₂ x₃ x₄ f x₁ x₂ x₃ x₄ f

0 0 0 0 0 0 1 1 1 0

0 0 0 1 1 1 0 0 0 0

0 0 1 0 1 1 0 0 1 1

0 0 1 1 0 1 0 1 0 1

0 1 0 0 0 1 1 0 0 0

0 1 0 1 1 1 1 0 1 1

0 1 1 0 1 1 1 1 0 1

1 1 1 1 1

Все наборы, где f=1 разбиваются на группы, включающие одну 1, 2-ая – 2 единицы, 3-я – 3 единицы и т.д.Склеиваться могут только наборы из соседних групп. Если произошла операция склеивания, то выписывается набор в склеенном виде. Если набор не участвует в склеивании, то остается несклеенным.

* * *

* * *

* *

* *

* *

* *

* *

* *

1) 0 0 0 1

0 0 1 0

2) 0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

3) 1 1 0 1

1 1 1 0

4) 1 1 1 1

0 – 0 1

- 0 0 1

0 – 1 0

- 0 1 0

- 1 0 1

- 1 1 0 Формируем группы, в которых прочерк находится в одном и том же месте

1 – 0 1

1 – 1 0

1 1 – 1

1 1 1 –

1) – 0 0 1 *

- 0 1 0 *

Прочерк на 1-м месте

- 1 1 0 *

3) --------

В результате склеивания: - - 0 1

- - 1 0

1) 0 - 0 1 *

0 - 1 0 *

Прочерк на 2-м месте

1 - 1 0 *

3) --------

В результате склеивания: - - 0 1

- - 1 0

1)

Прочерк на 3-м месте

3) 1 1 - 1

1)

Прочерк на 4-м месте

3) 1 1 1 –

После вторичной операции склеивания:

- - 0 1 1 1 – 1

- - 1 0 1 1 1 –

Набор соответствующей конъюнкции

- - 0 1: x ₃ * x₄

- - 1 0: x₃ * x ₄

1 1 – 1: x₁ * x₂ * x₄

1 1 1 -: x₁ * x₂ * x₃

Таблица реализации

Исходные наборы конъюнкций	Покрывающие конъюнкции (импликанты)
x 3 x4	x3 x 4	x1 x2 x4	x1 x2 x3
x1 x2 x 3 x4 x1 x2 x3 x 4 x1 x2 x3 x4

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

f=(x ₃ x₄) v (x₃ x ₄) v (x₁ x₂ x₄)

Или

f=(x ₃ x₄) v (x₃ x ₄) v (x₁ x₂ x₃)

Дата добавления: 2015-08-21