Задача цілочислового програмування та її особливості

unit mmm;

interface

procedure str(var a:array of integer);

procedure sts(var a:array of integer);

procedure bub(var a:array of integer);

procedure qui(var a:array of integer);

implementation

procedure str;

var

x,i,j:integer;

n1,n:integer;

begin

n:=high(a);

n1:=low(a);

for i:=n1 to n do

begin

x:=a[i];

j:=i-1;

while (j>=n1) and (a[j]>x) do

begin

a[j+1]:=a[j];

j:=j-1;

end;

a[j+1]:=x;

end;

end;

procedure sts;

var

x,k,i,j:integer;

n1,n:integer;

begin

n:=high(a);

n1:=low(a);

for i:=n1 to n-1 do

begin

k:=i;

for j:=i+1 to n do

if a[k]>a[j] then k:=j;

if k<>i then

begin

x:=a[i];a[i]:=a[k];a[k]:=x;

end;

end;

end;

procedure bub;

var

x,i,j:integer;

n1,n:integer;

begin

n:=high(a);

n1:=low(a);

for i:=n1 to n-1 do

for j:=n downto i+1 do

if a[j-1]>a[j] then

begin

x:=a[j];a[j]:=a[j-1];

a[j-1]:=x;

end;

end;

procedure qui;

var n1,n:integer;

procedure sort(l,r:integer);

var

x,w,i,j:integer;

begin

i:=l;j:=r;

x:=a[(i+j) div 2];

repeat

while a[i]<x do i:=i+1;

while a[i]>x do j:=j-1;

if i<=j then

begin

w:=a[i];

a[i]:=a[j];

a[j]:=w;

i:=i+1;

j:=j-1;

end;

until i>j;

if i<r then sort(i,r);

if j>l then sort(l,j)

end;

begin

n:=high(a);

n1:=low(a);

sort(n1,n);

end;

end.

program test;

uses mmm;

const n=100;

var a:array[1..n] of integer;

i:integer;

begin randomize;

for i:=1 to n do

a[i]:=random(100);

writeln('неупорядкований масив:');

for i:=1 to n do

write(a[i]:4);

writeln;

sts(a);

writeln('упорядкований масив :');

for i:=1 to n do

write(a[i]:4);

writeln;

end.

Список рекомендованої літератури

1. Сердюченко В.Я. Розробка алгоритмів та програмування мовою Turbo Pascal,- Харків: Паритет, 1995. - 352 с.

2. Фаронов В. В. Турбо Паскаль 7.0. Начальный курс. - М.: Нолидж,1997. - 616 с.

3. Марченко А.И. Программирование в среде Borland Pascal v 7.0.-К.: Век, 1997. - 480 с.

4. Епанешников AM, Епанешников В.А. Программирование в среде Turbo Pascal 7.0. - М.: Диалог -МИФИ , 1993. - 228 с.

5. Бородин Ю.С, Вальвачев А.Н. и др. Паскаль для персональных компьютеров.- Минск: Высш. шк„ 1991. - 364 с.

6. Поляков Д.Б. , Круглов И.Ю. Программирование в среде Турбо-Паскаль. -М.: МАИ , 1992. - 576 с.

7. Довгаль С.И. и др. Персональные ЭВМ: Турбо-Паскаль v 6.0. Объектное программирование и локальные сети,- К.: Информсистема сервис, 1993. - 440 с.

8. Абрамов С.А. и др. Задачи по программированию.-М.: Наука, 1988. - 280 с.

Додаток 1 Процедури та функції модуля GRAPH

План теми

5.1. Задача цілочислового програмування та її особливості.

5.2. Геометрична інтерпретація задачі цілочислового програмування.

5.3. Методи розв’язання цілочислових задач лінійного програмування.

5.3.1. Загальна характеристика методів розв’язання цілочислових задач лінійного програмування.

5.3.2. Методи відтинання. Метод Гоморі.

5.3.3. Комбінаторні методи. Метод гілок та меж.

5.4. Розв’язання задач цілочислового програмування на ПЕОМ.

задача цілочислового програмування та її особливості

Існує доволі широке коло задач математичного програмування, в економіко-математичних моделях яких одна або кілька змінних за своїм економічним змістом мають набувати тільки цілих значень. До таких задач відносяться, наприклад, задачі, у яких змінні означають кількість одиниць неподільної продукції (плити, шафи, столи і т.і.), кількість станків при оптимальному завантаженні обладнання для виконання деяких видів робіт, кількість тролейбусів при оптимальному розподілі їх за різними маршрутами, кількість стандартних листів фанери, яку потрібно розпиляти на деякі стандартні заготовки і багато інших подібних задач.

a Задача математичного програмування, змінні якої мають набувати тільки цілих значень, називається задачею цілочислового програмування. У тому разі, коли цілочислових значень мають набувати не всі, а одна чи кілька змінних, задача називається частково цілочисловою.

До цілочислового програмування належать також ті задачі математичного програмування, в яких змінні набувають лише двох значень: 0 або 1 – це так звані задачі цілочислового програмування з бінарними (або альтернативними) змінними.

Слід зазначити, що умова цілочисельності є по суті нелінійною і може зустрічатися в задачах, що містять як лінійні, так і нелінійні функції стосовно змінних задачі. В подальшому будемо розглядати тільки такі задачі математичного програмування, в яких крім умови цілочисельності всі обмеження та цільова функція є лінійними. Такі задачі мають назву цілочислових задач лінійного програмування.

Загальна цілочислова задача лінійного програмування записується наступним чином:

, ( 5.1 )

, ( 5.2 )

, , ( 5.3 )

— цілі числа, . ( 5.4 )

Слід зазначити, що у розглянутій у попередній темі класичній транспортній задачі та інших задачах транспортного типу з цілочисловими параметрами початкових умов забезпечується цілочисловий розв’язок без застосування спеціальних методів, однак у загальному випадку вимога цілочисельності змінних значно ускладнює розв’язування задач математичного програмування і вимагає застосування спеціальних методів для їх розв’язання.