Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Чернігівський державний технологічний університет

Кафедра вищої математики

Контрольна робота

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

Варіант 06

Чернігів 2009

Зміст

Завдання №1

Завдання №2

Завдання №3

Завдання №4

Завдання №5

Список використаних джерел

Завдання №1

Звести до канонічної форми задачу лінійного програмування:

Дана задача лінійного програмування задана в симетричній формі запису: умови, при яких функція F буде максимальною, задані у вигляді нерівностей. Для того, щоб отримати канонічну форму задачі лінійного програмування необхідно нерівності перетворити у рівності, використовуючи теорему, за якою нерівність

еквівалентна рівнянню

і нерівності

а нерівність вигляду

еквівалентна рівнянню

, в якому

Враховуючи наведене вище дану задачу запишемо у наступній канонічній формі:

Завдання №2

Визначити оптимальний план задачі лінійного програмування графічним методом (знайти максимум і мінімум функції):

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

Потім знаходимо напівплощини, в яких виконуються задані нерівності (рисунок1).

Рисунок1– Графічне визначення максимального і мінімального значення функції

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

не співпадає з площиною, утвореною обмеженнями

.

Завдання №3

Побудувати двоїсту задачу. Симплексним методом знайти оптимальний план початкової задачі. Використовуючи першу теорему двоїстості, визначити план другої задачі.

Для перетворення нерівностей в рівності вводимо змінні одиничні матриці х₃, х₄ і х₅. Для розв’язку задачі симплексним методом необхідно мати три одиничних матриці при невід’ємних правих частинах рівнянь. Для отримання одиничної матриці в першій і третій нерівностях вводимо введемо штучні змінну х₆ і х₇ та отримаємо одиничні матриці А₆ і А₇. Де

і

В результаті наведених перетворень отримаємо наступну задачу:

У виразі функції величину М вважаємо достатньо великим додатнім числом, оскільки задача розв’язується на знаходження мінімального значення функції.

Запишемо задачу у векторній формі:

де

В якості базису вибираємо одиничні вектори А₆, А₄, А₇. Вільні невідомі прирівнюємо нулю . В результаті отримаємо початковий опорний план розширеної задачі

,

якому відповідає розкладення

Для перевірки початкового опорного плану складаємо першу симплексну таблицю (таблиця1) і підраховуємо значення функції і оцінок Маємо:

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

Таблиця1– Перша симплексна таблиця

Базис	С базису	А0
			х1	х2	х3	х4	х5	х6	х7
х6	М	8	1		-1	0	0	1	0
х4	0	20	3	4	0	1	0	0	0
х7	М	6	3	1	0	0	-1	0	1
F-C	–	0	-5	-2	0	0	0	0	0
М	–	14	4	4	-1	0	-1	0	0

В (М) рядку є додатні оцінки, тому опорний план Х₀ не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає . Оскільки у нас максимальне значення 4 належить двом векторам, то в базис включаємо вектор, якому відповідає мінімальне С_j. Розв’язувальним рядком вибирається той, в якому найменше відношення Серед коефіцієнтів розкладання векторів А₁ і А₂ по базису є додатні, тому хоча б один з векторів існує.. Знайдемо ці значення:

;

Таким чином підтвердилося, що розв’язувальним стовпчиком буде другий, і визначилося, що розв’язувальним рядком буде перший. Тобто розв’язувальний елемент – число 3. Тоді вектор А₂ включаємо в базис, а вектор А₆ виключаємо з нього.

Складаємо другу симплексну таблицю (таблиця2). При цьому елементи першого (розв’язувального) рядка ділимо на 3. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.

Таблиця2– Друга симплексна таблиця

Базис	С базису	А0
			х1	х2	х3	х4	х5	х6	х7
х2	2	2,67	0,33	1	-0,33	0	0	0,33	0
х4	0	9,33	1,67	0	1,33	1	0	-1,33	0
х7	М	3,33		0	0,33	0	-1	-0,33	1
F-C	–	5,33	-4,33	0	-0,67	0	0	0,67	0
М	–	3,33	2,67	0	0,33	0	-1	-1,33	0

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

тому розв’язувальним рядком є третій. Таким чином розв’язувальний елемент – число 2,67. Тоді вектор А₁ включаємо в базис, а вектор А₇ виключаємо з нього.

Складаємо другу симплексну таблицю (таблиця3). При цьому елементи третього (розв’язувального) рядка ділимо на 2,67. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.

Таблиця3– Третя симплексна таблиця

Базис	С базису	А0
			х1	х2	х3	х4	х5	х6	х7
х2	2	2,25	0	1	-0,375	0	0,125	0,375	-0,125
х4	0	7,25	0	0	1,125	1	0,625	-1,125	-0,625
х1	5	1,25	1	0	0,125	0	-0,375	-0,125	0,375
F-C	–	10,75	0	0	-0,125	0	-1,625	0,125	1,625
М	–	0	0	0	0	0	0	-1	-1

В результаті проведеної ітерації з базису виключено штучні елементи, тому в рядку (М) всі оцінки, крім оцінки штучного вектору, перетворилися на нуль. Оскільки в рядках (F-C) і (М) не має додатних значень, то знайдене рішення

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)