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

 

 

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

Вінницький національний технічний університет

 

 

В. М. Михалевич, О. І. Тютюнник

 

МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ В MAPLE

Частина ІІ

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

 

Навчальний посібник

 

Вінниця

ВНТУ

УДК 519.85+681.3.05(075)

ББК 22.18+32.973.26-018.2я73

М69

 

Рекомендовано до друку Вченою радою Вінницького національного технічного університету Міністерства освіти і науки, молоді та спорту України (протокол №10 від 30.05.2012 р.)

 

 

Рецензенти:

Ф. М. Сохацький, доктор фізико-математичних наук, професор

В. І. Клочко, доктор педагогічних наук, професор

О. М. Роїк, доктор технічних наук, професор

О. В. Мороз, доктор економічних наук, професор

 

Михалевич, В. М.

М69 Вища математика. Математичне програмування в Maple. Частина IІ. Двоїсті та цілочислові задачі лінійного програмування: навчальний посібник. – Вінниця: ВНТУ, 2012. – 79 с.

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

Розрахований на студентів технічних та економічних ВНЗ усіх форм навчання та спеціальностей.

УДК 519.85+681.3.05(075)

ББК 22.18+32.973.26-018.2я73

 

 

© В. Михалевич, О.Тютюнник, 2012

ЗМІСТ

ЗМІСТ. 3

ПЕРЕДМОВА.. 4

1 ЗАГАЛЬНА ПОСТАНОВКА ТА ФОРМИ ЗАПИСУ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 6

2 ДВОЇСТІСТЬ У ЗАДАЧАХ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 11

2.1 Двоїсті задачі в симетричній формі 13

2.2 Загальні правила складання двоїстих задач. 15

2.3 Основні властивості та теореми двоїстості 18

2.4 Геометрична інтерпретація двоїстих задач. 20

2.5 Зв’язок між розв’язками прямої і двоїстої задач лінійного програмування 22

3 ДВОЇСТИЙ СИМПЛЕКС-МЕТОД.. 29

4 ЦІЛОЧИСЛОВІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 39

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

4.2 Графічний метод розв’язання задач цілочислового програмування 42

4.3 Метод Гоморі розв’язування задач цілочислового програмування 47

5 СТИСЛИЙ ОПИС ПАКЕТІВ РОЗШИРЕННЯ СИСТЕМИ MAPLE ДЛЯ РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ.. 68

ЛІТЕРАТУРА.. 73

 

 

ПЕРЕДМОВА

Навчальний посібник складено за програмою курсу “Вища математика” для студентів усіх форм навчання та спеціальностей вищих технічних та економічних навчальних закладів освіти на основі багаторічного досвіду викладання у Вінницькому національному технічному університеті.

Головна особливість посібника полягає у викладенні математичного програмування із застосуванням інформаційних технологій. Для цього пропонується використовувати середовище математичного пакету Maple. Авторами розроблено свій оригінальний підхід, в якому система Maple використовується для розкриття основних ідей, що містяться в теоремах двоїстості та покладені в основу двоїстого симплекс-методу розв’язання задач лінійного програмування, а також цілочислових задач лінійного програмування. В посібнику зроблено спробу висвітлення ключових етапів двоїстого симплекс-методу з наочною геометричною інтерпретацією. Цим посібник відрізняється як від багатьох відомих підручників, в яких пропонується формалізований перелік інструкцій для реалізації двоїстого симплекс-алгоритму, так і від інших відомих спроб викладення математичного програмування, в яких застосування інформаційних технологій зводиться до переліку інструкцій для одержання в певному додатку або остаточної відповіді, або, в кращому разі, послідовності симплекс-подібних таблиць.

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

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

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

Даний посібник, який є продовженням “Математичного програмування разом з Maple. Частина I. Методи розв’язування задач лінійного програмування”, містить у собі відомості з тем: “Загальна постановка та форми запису задач лінійного програмування”, “Двоїстість у задачах лінійного програмування”, “Двоїстий симплекс-метод”, “Цілочислові задачі лінійного програмування” та стислий опис пакетів розширення системи Maple для розв’язування задач лінійного програмування. Висвітлені в посібнику теоретичні відомості можна вважати скороченим курсом лекцій. Ці відомості демонструються прикладами.

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

Посібник розрахований на студентів економічних та технічних ВНЗ усіх форм навчання та спеціальностей.