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

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

Задача 801

Решение основной задачи линейного программирования симплексным методом

Постановка задачи

Найти неотрицательное решение ( все , j = 1,2, ..., n ) системы из уравнений :

( i = 1,2, ... ,m ), m > n (1)

образующее в максимум линейную целевую функцию :

(2)

Последовательность вычислений

1. Условия задачи записать в виде симплекс-таблицы размером (m+1) строка и (n+1) столбец:

(3)

Для размещения информации рекомендуется использовать массивы:
МАТР [ 1:(m+1)], 1:(n+1)] - для исходной матрицы ( симплекс-таблицы ),
X [1:n] - ( первоначально : -1, -2, ... , -n ),
Y[1:m] - ( первоначально : 1, 2, ... , m).

1. Алгоритм симплекс-метода состоит из двух основных этапов. На первом этапе отыскивается решение системы уравнений (1) и оно преобразуется в опорное решение, а далее на втором этапе целенаправленным переходом от одного опорного решения к другому получаем оптимальное решение, при этом в основе каждого из указанных этапов лежат модифицированные жордановы исключения ( МЖИ ). Суть их в следующем. Если мы имеем матрицу:

(4)

то один шаг МЖИ с разрешающим элементом означает переход к новой матрице :

(5)

где каждый элемент определяется:

Рекомендуется МЖИ оформить в виде процедуры. На каждом шаге МЖИ соответствующий элемент массива X меняется местом с соответствующим элементом массива Y.

1. Получение опорного решения.

1. Если все ( не считая строки z ), то опорное решение найдено. В этом случае все , а каждый ; идем на п.4. Если есть отрицательные свободные члены, переходим к п.3.2.

2. В строке с отрицательным свободным членом ищем отрицательный элемент . Если такого элемента нет, то система уравнений (1) несовместна и задача решения не имеет. Если отрицательный элемент есть, то выбираем столбец , в котором он находится, в качестве разрешающего.

3. Для каждого ( i = 1,2,... ) находим неотрицательные отношения и выбираем среди них наименьшее :
   ,
   таким образом получаем разрешающую строку r.

4. Осуществляем шаг МЖИ и возвращаемся к пункту 3.1.

1. Нахождение оптимального решения.

1. Проверка условия : решение оптимально. Если все , не считая , то получено оптимальное решение, в противном случае переходим к п.4.2.

2. Если < 0, то s-ый столбец берем в качестве разрешающего.

3. Проверка условия: задача имеет конечное решение. Если все , то линейная форма не ограничена снизу, задача не имеет конечного решения. В противном случае переходим к п.4.4.

4. Находим отношение свободных членов к положительным коэффициентам S-ого столбца и находим среди них наименьшее
   ,
   r-ую строку берем в качестве разрешающей, элемент будет разрешающим.

5. Осуществляем шаг МЖИ и возвращаемся к пункту 4.1.

1. После получения оптимального решения значения определяются с использованием массивов МАТР, X, Y.

Пример для отладки

Найти числа , максимизирующие функцию :

при ограничениях :

;

;

;

;

;

.

Решение.

Получено оптимальное решение . Max z = 36 при = 10, = 0. т

Исходные данные для основного счёта

Найти max линейной формы :

,

при следующих ограничениях :

;

;

;

Результаты счета

1. Выдать на печать исходные данные, оптимальный план ( , , .... , )и значение линейной формы z.

2. Проанализировать полученный результат.

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

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

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

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

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

Список файлов лабораторной работы