Поиск по базе сайта:
Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування» icon

Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування»




НазваМетодичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування»
Сторінка5/8
Дата конвертації02.08.2013
Розмір1.22 Mb.
ТипМетодичні вказівки
1   2   3   4   5   6   7   8

^ Завдання до лабораторної роботи

Розв’язати задачу лінійного програмування з використанням штучного базису за варіантами, поданими далі.

№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = –x1 + x2 – x3 – x5  min





Z = x1 – x2 – x3 + x4  min





Z = –2x1 + x2 + 5x3  min





Z = 4x1 + 4x2 + 10x3  min





Z = 2x1 + x2  max





Z = –4x1 + x2  max





Z = x1 – 2x2 + x3 – x4  min





Z = 3x1 + 2x2 + x3  max





Z = x1 + 2x2 + 3x3   min





Z = x1 + 2x2 + 2x3   min






№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = 3x1 – x2 – x3  max





Z = 4x1 + 6x2   min




Z = 5x1 + 4x2   max





Z = 6x1 + 4x2   min





Z = 3x1 – 3x2   max





Z = x1 + 3x2   max






Z = x1 + 3x2   max





Z = 5x1 + x2   max





Z = 2x1 + 3x2   min




Z = -x1 + 2x2   min



Лабораторна робота №5

^ РОЗВ’ЯЗАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ ДВОЇСТИМ МЕТОДОМ


Мета роботи – навчитися розв’язувати задачі лінійного програмування з використанням двоїстого методу.

У результаті виконання роботи студент повинен:

ЗНАТИ умови допустимості та оптимальності під час розв’язання задачі двоїстим методом;

УМІТИ здійснювати перехід від одного плану до іншого;

МАТИ УЯВЛЕННЯ про виконання критеріїв оптимальності.


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

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

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

^ Двоїста умова оптимальності. Змінна, що вводиться до базису, визначається як змінна, на якій досягається наступний мінімум:



min

небазисні j


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


Приклад

Мінімізувати .



Розв’язання

Система обмежень переводиться до канонічного вигляду:









Початкова симплекс-таблиця має вигляд:

Б.З.

В.ч.

Х1

Х2

Х3

Х4

Х5

X3

-3

-3

-1

1

0

За умовою допустимості, з базису виключається Х4

0

X4

-6

-4

-3

0

1

0

X5

3

1

1

0

0

1



0

-3

-2

0

0

0




3/4

2/3


Серед небазисних змінних обирається для введення в базис змінна Х2, що має найменше відношення


Виводиться з базису Х3, так як має від’ємне значення


Б.З.

В.ч.

Х1

Х2

Х3

Х4

Х5

Х3

-1

-5/3

0

1

-1/3

0

Х2

2

4/3

1

0

-1/3

0

Х5

1

-1/3

0

0

1/3

1



4

-1/3

0

0

-2/3

0




















До базису вводиться змінна Х1, що має найменше відношення.


Б.З.

В.ч.

Х1

Х2

Х3

Х4

Х5

Х1

3/5

1

0

-3/5

1/5

0

Х2

6/5

0

1

4/5

-3/5

0

Х5

6/5

0

0

-1/5

2/5

1



21/5

0

0

-1/5

-3/5

0


Розв’язок, поданий в останній таблиці, є припустимим (і оптимальним), тому обчислення припиняються.

,

На рис. 2 зображена послідовність кроків двоїстого сиплекс-методу.


Рисунок 2 – Ілюстрація кроків з розв’язку ЗЛП двоїстим симплекс-методом


Алгоритм починається в крайній точці А (якій відповідає неприпустимий, але «кращий, ніж оптимальний» розв’язок), потім він переходить до точки В (якій також відповідає неприпустимий, але «кращий, ніж оптимальний» розв’язок) і закінчується в точці С, що належить області припустимих розв’язків.

^ Завдання до лабораторної роботи

Розв’язати задачу лінійного програмування двоїстим методом за варіантами, поданими далі.

№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = –x1 + x2 – x3 + x4   min





Z = x1 – x2 – x3 + x5   max





Z = –2x1 + x2 + 5x3   min





Z = 2x1 + x3 + x4   max





Z = x1 + 2x2 + x4 + х6  max





Z = –x1 – 2x2   min





Z = 2x1 + 3x2   max





Z = –4x1 – x2   max





Z = 4x1 + x2 + 3x3   min





Z = 2x1 + x2 + 5x3  min

№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = 4x1 + 5x2 + 6x3  min





Z = –4x1 – 7x2 – 8x3 – 5x4   max





Z = 4x1 + 3x2 – 30x3  min





Z = 6x1 + 8x2 + x3   max





Z = 2x1 –x2 – x3– 2x4x6  min





Z = 6x1 + 4x2   min





Z = x1 + 2x2 + 2x3   min





Z = 5x1 + x2   max





Z = 4x1 + 6x2   min




Z = x1 + 3x2   max





Лабораторна робота №6

^ ЦІЛОЧИСЛОВЕ МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ


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

У результаті виконання роботи студент повинен:

ЗНАТИ алгоритм методу Гоморі;

УМІТИ здійснювати перехід під одного плану до іншого;

МАТИ УЯВЛЕННЯ про правила побудови правильних відтинань.


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

Задача цілочислового програмування (ЦП) формулюється так:

(1)


(2)

(3)

(4)



Для розв’язання таких задач можуть бути застосовані методи відтинання (одним з яких є метод Гоморі), сутність яких полягає в тому, що спочатку задача розв’язується без умови цілочисловості. Якщо одержаний результат є цілочисловим, то задача є розв’язаною. У протилежному випадку до обмежень задачі додається нове обмеження, яке має такі властивості:

  1. повинне бути лінійним;

  2. повинне відтинати знайдений оптимальний нецілочисловий розв’язок;

  3. не повинне відтинати жодного цілочислового розв’язку.

Додаткове обмеження, яке має вказані властивості, називається правильним відтинанням.

Далі задача розв’язується з урахуванням нового обмеження.

Нехай на останньому кроці розв’язання задачі симплекс-методом одержали - виражені через неосновні :



Нехай є нецілочисловим. Тоді можна довести, що обмеження

(5)

має властивості правильного відтинання.

{ }- дробова частина числа.

Цілою частиною [a] числа а називається найближче ціле число до даного числа а, яке не перевищує а.

Дробовою частиною {a}числа а називається {a}=a-[a].

завжди.


Алгоритм методу Гоморі:

1 Симплекс-методом розв’язують задачу (1)-(3) без урахування цілочисловості. Якщо всі компоненти оптимального розв’язку – цілі числа, то цей розв’язок є оптимальним і для задачі (1)-(4).

Якщо перша задача не має розв’язку, то і цілочислова задача не має розв’язку.

2 Якщо серед компонент оптимального розв’язку є нецілі, то обирається компонента з найбільшою дробовою частиною і за відповідним рівнянням формується правильне відтинання (5).

3 Нерівність (5) введенням невід’ємної додаткової змінної перетворюється на рівносильне рівняння і включається до вихідних обмежень (1).

4 Одержану розширену задачу розв’язують симплекс-методом. Якщо розв’язок буде цілочисловим, то задача ЦП є розв’язаною. Якщо ж ні, то повертаються до пункту 2.

Якщо задача ЦП має розв’язок, то за скінчене число кроків знаходиться оптимальний розв’язок задачі.

1   2   3   4   5   6   7   8



Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації